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.
|Title of host publication||Proceedings of the 7th Latin American Symposium (LATIN 2006)|
|Editors||J.R. Correa, A. Hevia, M. Kiwi|
|Place of Publication||Berlin|
|Number of pages||12|
|Publication status||Published - 2006|
|Name||Lecture Notes in Computer Science|
Broersma, H. J., Johnson, M., Paulusma, D., & Stewart, I. A. (2006). The Computational Complexity of the Parallel Knock-Out Problem. In J. R. Correa, A. Hevia, & M. Kiwi (Eds.), Proceedings of the 7th Latin American Symposium (LATIN 2006) (pp. 250-261). [10.1007/11682462_26] (Lecture Notes in Computer Science; Vol. 3887, No. 11). Berlin: Springer. https://doi.org/10.1007/11682462_26