We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Iain Stewart

Broersma, H., Johnson, M., Paulusma, D. & Stewart, I.A. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science 393(1-3): 182-195.

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 bipartite graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers k ≥ 2, the problem of whether a given bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) k rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time. We also show that r-regular graphs with r ≥ 1, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.


An extended abstract of this paper appeared in Proc. LATIN
2006: Theoretical Informatics: 7th Latin American Symposium (ed. J.R.
Correa, A. Hevia and M. Kiwi), Lecture Notes in Computer Science Vol. 3887, Springer, Berlin (2006) 250-261.