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.
|Number of pages||14|
|Journal||Theoretical computer science|
|Publication status||Published - Mar 2008|
|Event||7th Latin American Symposium on Theoretical Informatics, LATIN 2006 - Valdivia, Chile|
Duration: 20 Mar 2006 → 24 Mar 2006
Conference number: 7