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