On Disconnected Cuts and Separators
On Disconnected Cuts and Separators
复制标题
关于断开的切口和分隔符
DOI：
10.1016/j.dam.2011.04.027
复制
发表时间：
2011
影响因子：
1.1
通讯作者：
Daniel Paulusma and Dimitrios M. Thilikos
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Marcin Kaminski;Daniel Paulusma and Dimitrios M. Thilikos
对于连通图G=(V，E)，如果U断开该图的连通，则称其子集U⊆V为不连通割，并且由U诱导的子图也是不连通的。一个自然的条件是对任意u∈U，由(V∖U)∪{u}诱导的子图是连通的。在这种情况下，U称为最小不连通割。我们证明了测试一个图是否有最小不连通割的问题是NP-完全的。我们还证明了检验一个图是否有分隔两个指定顶点S和t的不连通割的问题是NP-完全的。
For a connected graph G=(V, E), a subset U⊆ V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈ U, the subgraph induced by (V∖ U)∪{u} is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t, is NP-complete.