, Johnson, M.
, Paulusma, D.
& Stewart, I.A.
(2006), The computational complexity of the parallel knock-out problem, Lecture Notes in Computer Science 3887
: 7th Latin American Theoretical Informatics Symposium (LATIN 2006)
. Valdivia, Chile., Springer, Berlin, 250-261.
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.