Broersma, Hajo.,
Johnson, Matthew.,
Paulusma, Daniel. &
Stewart, Iain A. (2006).
The computational complexity of the parallel knock-out problem. 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Valdivia, Chile., Springer.
- Publication type: Edited works: conference proceedings
- ISSN/ISBN: 978-3-540-32755-4
- DOI: 10.1007/11682462_26
- Keywords: parallel knock-out, graphs, computational complexity
- View online: Online version
- Durham research online: DRO record
Author(s) from Durham
Abstract
We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for a given graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers
k > 1, the problem of whether a given graph admits a scheme in which all vertices are eliminated in at most
k rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time.
