The Computational Complexity of the Parallel Knock-Out Problem


Broersma, H.J. and Johnson, M. and Paulusma, D. and Stewart, I.A. (2006) The Computational Complexity of the Parallel Knock-Out Problem. In: Proceedings of the 7th Latin American Symposium (LATIN 2006), 20-24 March 2006, Valdivia, Chile (pp. pp. 250-261).

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 238711