Knocking Out P_k-free Graphs

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

doi:10.1007/978-3-662-44465-8_34

Knocking Out P_k-free Graphs

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

Authors

M. Johnson

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

A. Stewart

Contributors

Ersébet Csuhaj-Varjú
Editor

Martin Dietzfelbinger
Editor

Zoltán Ésik
Editor

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).

Citation

Johnson, M., Paulusma, D., & Stewart, A. (2014). Knocking Out P_k-free Graphs. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29August 2014 ; proceedings, Part II (396-407). https://doi.org/10.1007/978-3-662-44465-8_34

Conference Name	39th International Symposium, MFCS 2014
Conference Location	Budapest, Hungary
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