Publication details for Professor Iain StewartBroersma, 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.
- Publication type: Journal Article
- ISSN/ISBN: 0304-3975
- DOI: 10.1016/j.tcs.2007.11.021
- Keywords: Parallel knock-out schemes, Computational complexity, NP-completeness, Bounded tree-width, Monadic second-order logic.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
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.