The Complexity of Contracting Bipartite Graphs into Small Cycles

R. Krithika, Roohani Sharma, Prafullkumar Tale

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.

Gadget construction for the reduction.

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.

Witness set analysis and bipartite transformation.

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

Abstract

For a positive integer \(\ell \ge 3\), the \(C_\ell \)-Contractibility problem takes as input an undirected simple graph G and determines whether G can be transformed into a graph isomorphic to \(C_\ell \) (the induced cycle on \(\ell \) vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed that \(C_4\)-Contractibility is \(\textsf{NP}\)-complete in general graphs. It is easy to verify that that \(C_3\)-Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that \(C_{\ell }\)-Contractibility is \(\textsf{NP}\)-complete on bipartite graphs for \(\ell = 6\) and posed as open problems the status of \(C_{\ell }\)-Contractibility when \(\ell \) is 4 or 5. In this paper, we show that both \(C_5\)-Contractibility and \(C_4\)-Contractibility are \(\textsf{NP}\)-complete on bipartite graphs.
BibTeX
@inproceedings{krithika2022complexity,
  author = {R. Krithika and Roohani Sharma and Prafullkumar Tale},
  title = {{The Complexity of Contracting Bipartite Graphs into Small Cycles}},
  booktitle = {Discret. Math. Theor. Comput. Sci},
  year = {2022},
}
Figure