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 Matthew Johnson

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