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.

PDF
Restricted to UT campus only: Request a copy
459Kb

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
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/63665
Official URL:	http://dx.doi.org/10.1007/11682462_26
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 238711