The computational complexity of the parallel knock-out problem
- 作者：Hajo Broersma ; Matthew Johnson ; Danië ; l Paulusma ; Iain A. Stewart
- 关键词：Parallel knock-out ; Graphs ; Computational complexity
- 刊名：Theoretical Computer Science
- 出版年：2008
- 期刊代码：114_03043975
- 类别：cp
- 出版时间：20 March 2008
- 卷：393
- 期：1-3
- 页码：182-195
- 文件大小：459 K
摘要
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 class="sans-serif">NP-complete. Moreover, we show that, for all fixed positive integers coration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4RDR1HN-1&_mathId=mml1&_user=10&_cdi=5674&_rdoc=16&_acct=C000050221&_version=1&_userid=10&md5=5689e2aee8ce5d2ac8df8ab2597519b8" title="Click to view the MathML source">k≥2, the problem of whether a given bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) coration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4RDR1HN-1&_mathId=mml2&_user=10&_cdi=5674&_rdoc=16&_acct=C000050221&_version=1&_userid=10&md5=49f980acc4a1f5357daa5bdceb9f8e08" title="Click to view the MathML source">k rounds is class="sans-serif">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 coration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4RDR1HN-1&_mathId=mml3&_user=10&_cdi=5674&_rdoc=16&_acct=C000050221&_version=1&_userid=10&md5=7d86dddd96479fe36f8b76c063f5c581" title="Click to view the MathML source">r-regular graphs with coration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4RDR1HN-1&_mathId=mml4&_user=10&_cdi=5674&_rdoc=16&_acct=C000050221&_version=1&_userid=10&md5=d12f66842e49854b4f29b9cef5633507" title="Click to view the MathML source">r≥1, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.