The computational complexity of the parallel knock-out problem

Haitze J. Broersma, M. Johnson, Daniël Paulusma, I.A. Stewart

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

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\ge 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\ge 1$, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.
Original languageUndefined
Article number10.1016/j.tcs.2007.11.021
Pages (from-to)182-195
Number of pages14
JournalTheoretical computer science
Volume393
Issue number1-3
DOIs
Publication statusPublished - Mar 2008

Keywords

  • IR-62554
  • EWI-14148
  • METIS-254919

Cite this

Broersma, H. J., 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. [10.1016/j.tcs.2007.11.021]. https://doi.org/10.1016/j.tcs.2007.11.021