@inproceedings{a9a15a15b53a4579942026b991605c9e,

title = "The Computational Complexity of the Parallel Knock-Out Problem",

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 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 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.",

keywords = "EWI-8091, IR-63665, METIS-238711",

author = "Broersma, {Haitze J.} and M. Johnson and Dani{\"e}l Paulusma and I.A. Stewart",

note = "10.1007/11682462_26 ",

year = "2006",

doi = "10.1007/11682462_26",

language = "Undefined",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "11",

pages = "250--261",

editor = "J.R. Correa and A. Hevia and M. Kiwi",

booktitle = "Proceedings of the 7th Latin American Symposium (LATIN 2006)",

}