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 GG is KO-reducible. This problem is known to be NP-complete and has been studied for several graph classes. We show that the problem is NP-complete even for split graphs, a subclass of P5P5-free graphs. In contrast, our main result is that it is linear-time solvable for P4P4-free graphs (cographs).

Citation

Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108. https://doi.org/10.1016/j.dam.2015.04.010

• Journal Article Type: Article
• Acceptance Date: Apr 17, 2015
• Publication Date: Aug 20, 2015
• Deposit Date: May 12, 2015
• Publicly Available Date: May 8, 2016
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 190-191
• Pages: 100-108
• DOI: https://doi.org/10.1016/j.dam.2015.04.010
• Keywords: Parallel knock-out schemes, Hamilton cycle, Cographs, Split graphs, Computational complexity.
• Public URL: https://durham-repository.worktribe.com/output/1408658