Knocking Out P_k-free Graphs

Johnson, M.; Paulusma, D.; Stewart, A.

Abstract

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Parallel Knock-Out problem is to decide whether a graph G is KO-reducible. This problem is known to be NP-complete and has been studied for several graph classes since MFCS 2004. We show that the problem is NP-complete even for split graphs, a subclass of P 5-free graphs. In contrast, our main result is that it is linear-time solvable for P 4-free graphs (cographs).

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: 39th International Symposium, MFCS 2014
• Publication Date: Jan 1, 2014
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 15, 2015
• Pages: 396-407
• Series Title: Lecture notes in computer science
• Series Number: 8635
• Series ISSN: 0302-9743,1611-3349
• Book Title: 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29August 2014 ; proceedings, Part II.
• ISBN: 9783662444641
• DOI: https://doi.org/10.1007/978-3-662-44465-8_34
• Public URL: https://durham-repository.worktribe.com/output/1153089