Broersma, Hajo and Johnson, Matthew and Paulusma, Daniel and Stewart, Iain A. (2006) 'The computational complexity of the parallel knock-out problem.', in LATIN 2006 : theoretical informatics: : 7th Latin American symposium, Valdivia, Chile, March 20-24, 2006 : proceedings. Berlin: Springer, pp. 250-261. Lecture notes in computer science. (3887).
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 <i>k</i> > 1, the problem of whether a given graph admits a scheme in which all vertices are eliminated in at most <i>k</i> 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:||Book chapter|
|Keywords:||Parallel knock-out, Graphs, Computational complexity.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (218Kb)
|Publisher Web site:||https://doi.org/10.1007/11682462_26|
|Publisher statement:||The final publication is available at Springer via https://doi.org/10.1007/11682462_26|
|Date accepted:||No date available|
|Date deposited:||11 December 2015|
|Date of first online publication:||February 2006|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|