Abstract
This paper investigates the computational complexity of the $H$-CONTRACTIBILITY problem, specifically focusing on bipartite graphs and small target cycles. While contracting general graphs into a 4-cycle is known to be NP-complete, the status for bipartite graphs remained unresolved for $C_4$ and $C_5$. This work establishes that determining if a bipartite graph can be contracted into a 4-cycle or a 5-cycle is NP-complete, filling a significant gap in the literature of graph theory and computational complexity.
Introduction
Edge contraction is a fundamental graph operation where an edge is removed and its endpoints are merged. This process is central to graph minor theory and has practical applications in network analysis and data simplification. The $H$-CONTRACTIBILITY problem asks whether a given graph $G$ can be transformed into a target graph $H$ via a sequence of edge contractions.
Prior research established that contracting a bipartite graph into a 6-cycle ($C_6$) is NP-complete. However, the complexity for smaller cycles like $C_4$ and $C_5$ on bipartite graphs was previously unknown. This paper settles these cases, demonstrating that even for these minimal structures, the problem remains computationally intractable.
Methodology: Polynomial-time Reduction
The authors prove NP-completeness through a polynomial-time reduction from the POSITIVE NOT ALL EQUAL SAT (POSITIVE NAE-SAT) problem. In POSITIVE NAE-SAT, one must determine if a boolean formula with only positive literals has a satisfying assignment such that in every clause, the variables do not all have the same truth value.
Gadget Construction and Witness Sets
The reduction involves constructing a graph $G$ composed of "variable gadgets" and "clause gadgets." These gadgets are designed to mimic the logical constraints of the SAT instance. A key tool in the proof is the use of witness sets. A graph $G$ is $H$-contractible if and only if there exists a partition of its vertices into $|V(H)|$ connected subgraphs (witness sets), such that two witness sets are adjacent if and only if the corresponding vertices in $H$ are adjacent.
Ensuring Bipartiteness
A significant challenge was ensuring that the constructed graph $G$ is bipartite. The authors first develop a non-bipartite construction and then apply a "safe subdivision" strategy. By strategically adding vertices to edges, they transform the graph into a bipartite one without altering its fundamental contractibility to the target cycle. The authors also used specific vertex neighborhoods to "lock" certain parts of the graph, forcing any valid contraction to follow the intended logic of the SAT formula.
Key Results
The paper presents several major theorems that expand our understanding of graph contraction complexity:
- Theorem 1: $C_5$-CONTRACTIBILITY is NP-complete on bipartite graphs.
- Theorem 2: $C_4$-CONTRACTIBILITY is NP-complete on bipartite graphs.
- Theorem 3: $C_4$-CONTRACTIBILITY is NP-complete on $K_4$-free graphs with a diameter of 2.
Beyond bipartite graphs, the authors extended their findings to show that the problem remains hard when contracting to complete bipartite graphs ($K_{p,q}$) for $p, q \ge 2$ on $K_4$-free graphs of diameter 2.
Conclusion and Future Directions
By proving the NP-completeness of $C_4$ and $C_5$ contractibility on bipartite graphs, this work completes the complexity landscape for cycle contractions in this graph class. Interestingly, the sophistication of the required gadgets actually increases as the target cycle gets smaller, suggesting that smaller target structures are paradoxically harder to prove than larger ones.
Future research may explore the complexity of contracting to the longest possible cycle within specific graph families or investigate the relationship between cycle contraction and the DISCONNECTED CUT problem, which asks if a graph can be partitioned into two parts that are both disconnected.
Summary updated