The computational complexity of the parallel knockout problem
Broersma, H.J. and Johnson, M. and Paulusma, D. and Stewart, I.A. (2008) The computational complexity of the parallel knockout problem. Theoretical Computer Science, 393 (13). pp. 182195. ISSN 03043975
PDF Restricted to UT campus only: Request a copy 459Kb 
Abstract:  We consider computational complexity questions related to parallel knockout 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 NPcomplete. Moreover, we show that, for all fixed positive integers , the problem of whether a given bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) rounds is NPcomplete. For graphs with bounded treewidth, however, both of these problems are shown to be solvable in polynomial time. We also show that regular graphs with , factorcritical graphs and 1tough 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