Johnson, M. and Paulusma, D. and Stewart, A. (2014) 'Knocking out P_k-free graphs.', in 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29August 2014 ; proceedings, Part II. Berlin, Heidelberg: Springer, pp. 396-407. Lecture notes in computer science. (8635).
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).
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (331Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/978-3-662-44465-8_34 |
| Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-44465-8_34 |
| Date accepted: | No date available |
| Date deposited: | 15 January 2015 |
| Date of first online publication: | 2014 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
