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.
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≥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.
Item Type: | Article |
---|---|
Keywords: | Parallel knock-out schemes, Computational complexity, NP-completeness, Bounded tree-width, Monadic second-order logic. |
Full text: | (AM) Accepted Manuscript Download PDF (247Kb) |
Status: | Peer-reviewed |
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
Export: | |
Look up in GoogleScholar |