Edge-Contraction Problems
Edge-Contraction Problems
复制标题
DOI：
10.1016/0022-0000(83)90012-0
复制
发表时间：
1983-04
期刊：
影响因子：
--
通讯作者：
Takao Asano;T. Hirata
中科院分区：
文献类型：
--
作者：
Takao Asano;T. Hirata
对于图上的属性 π，相应的边收缩问题PEC(π) 定义如下：给定一个图G，找到一组最小基数的边，其收缩导致图满足属性 π。在本文中，我们证明，如果 π 在收缩上是遗传的并且由双连通分量确定，则边缘收缩问题 PEC(π) 是 NP 困难的。此外，即使我们将自己限制在平面图类中，这个问题也是NP困难的。此外，如果我们添加一个条件，即 π 由 3 连通分量确定，则即使限制为 3 连通图和二分图，PEC(π) 也是 NP 困难的。
For a property π on graphs, the corresponding edge-contraction problemPEC(π) is defined as follows: Given a graphG, find a set of edges of minimum cardinality whose contraction results in a graph satisfying property π. In this paper we show that the edge-contraction problemPEC(π) isNP-hard if π is hereditary on contractions and is determined by the biconnected components. Moreover, this problem isNP-hard even if we restrict ourselves to the class of planar graphs. Furthermore, if we add a condition that π is determined by the 3-connected components, thenPEC(π) isNP-hard even if restricted to 3-connected graphs and to bipartite graphs.