The computational complexity of the parallel knock-out problem

Broersma, H.J. and Johnson, M. and Paulusma, D. and Stewart, I.A. (2008) The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393 (1-3). pp. 182-195. ISSN 0304-3975

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 bipartite 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 bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) $k$ rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time. We also show that $r$ -regular graphs with $r\ge 1$ , factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.
Item Type:	Article
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/62554
Official URL:	http://dx.doi.org/10.1016/j.tcs.2007.11.021
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 254919