Edge-contraction problems

摘要

For a property π on graphs, the corresponding edge-contraction problem PEC(π) is defined as follows: Given a graph G, 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 problem PEC(π) is NP-hard if π is hereditary on contractions and is determined by the biconnected components. Moreover, this problem is NP-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, then PEC(π) is NP-hard even if restricted to 3-connected graphs and to bipartite graphs.