The computational complexity of the parallel knock-out problem

Share/Save/Bookmark

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

[img] PDF
Restricted to UT campus only
: Request a copy
470kB
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:
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

 

Repository Staff Only: item control page

Metis ID: 254919