TY - JOUR
T1 - The computational complexity of the parallel knock-out problem
AU - Broersma, Hajo
AU - Johnson, Matthew
AU - Paulusma, Daniël
AU - Stewart, Iain A.
N1 - Conference code: 7
PY - 2008/3
Y1 - 2008/3
N2 - 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.
AB - 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.
U2 - 10.1016/j.tcs.2007.11.021
DO - 10.1016/j.tcs.2007.11.021
M3 - Article
SN - 0304-3975
VL - 393
SP - 182
EP - 195
JO - Theoretical computer science
JF - Theoretical computer science
IS - 1-3
T2 - 7th Latin American Symposium on Theoretical Informatics, LATIN 2006
Y2 - 20 March 2006 through 24 March 2006
ER -