The computational complexity of the parallel knock-out problem

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

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

Citation

Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006, March). The computational complexity of the parallel knock-out problem. Presented at 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Valdivia, Chile

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 7th Latin American Theoretical Informatics Symposium (LATIN 2006)
• Start Date: Mar 20, 2006
• End Date: Mar 24, 2006
• Publication Date: Feb 18, 2006
• Deposit Date: Oct 14, 2009
• Publicly Available Date: Dec 11, 2015
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Pages: 250-261
• Series Title: Lecture notes in computer science
• Series Number: 3887
• Book Title: LATIN 2006 : theoretical informatics: : 7th Latin American symposium, Valdivia, Chile, March 20-24, 2006 : proceedings.
• ISBN: 9783540327554
• DOI: https://doi.org/10.1007/11682462_26
• Keywords: Parallel knock-out, Graphs, Computational complexity.
• Public URL: https://durham-repository.worktribe.com/output/1162493