Skip to main content

Research Repository

Advanced Search

The computational complexity of the parallel knock-out problem

Broersma, H.; Johnson, M.; Paulusma, D.; Stewart, I.A.

The computational complexity of the parallel knock-out problem Thumbnail


Authors

H. Broersma

M. Johnson



Contributors

J.R. Correa
Editor

A. Hevia
Editor

M. Kiwi
Editor

Abstract

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.

Citation

Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393(1-3), 182-195. https://doi.org/10.1016/j.tcs.2007.11.021

Journal Article Type Article
Publication Date Mar 1, 2008
Deposit Date Jun 18, 2008
Publicly Available Date Mar 28, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 393
Issue 1-3
Pages 182-195
DOI https://doi.org/10.1016/j.tcs.2007.11.021
Keywords Parallel knock-out schemes, Computational complexity, NP-completeness, Bounded tree-width, Monadic second-order logic.
Publisher URL http://www.dur.ac.uk/i.a.stewart/Papers/knockout.pdf

Files





You might also like



Downloadable Citations