Broersma, H. and Johnson, M. and Paulusma, Daniel and Stewart, I. A. (2008) 'The computational complexity of the parallel knock-out problem.', Theoretical computer science., 393 (1-3). pp. 182-195.
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≥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≥1, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.
|Keywords:||Parallel knock-out schemes, Computational complexity, NP-completeness, Bounded tree-width, Monadic second-order logic.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (247Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.tcs.2007.11.021|
|Date accepted:||No date available|
|Date deposited:||02 July 2009|
|Date of first online publication:||March 2008|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|