The Complexity of Contracting Bipartite Graphs into Small Cycles

Basic Information

• Paper ID: 2206.07358
• Title: The Complexity of Contracting Bipartite Graphs into Small Cycles
• Authors: R. Krithika, Roohani Sharma, Prafullkumar Tale
• Classification: cs.CC (Computational Complexity Theory)
• Publication Time/Conference: 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2022)
• Paper Link: https://arxiv.org/abs/2206.07358

Abstract

For a positive integer $\ell \geq 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$ (an induced cycle with $\ell$ vertices) through edge contraction operations. Brouwer and Veldman proved in 1987 that $C_4$-Contractibility is NP-complete on general graphs. $C_3$-Contractibility can be solved in polynomial time. Dabrowski and Paulusma proved in 2017 that $C_\ell$-Contractibility is NP-complete on bipartite graphs when $\ell = 6$, and posed open questions regarding the complexity when $\ell = 4$ or $5$. This paper proves that both $C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite graphs.

Research Background and Motivation

Problem Background

1. Graph Contraction Operations: Edge contraction is a fundamental operation in graph theory that simplifies graphs by removing the two endpoints of an edge and adding a new vertex connected to all neighbors of the original endpoints. This operation has important applications in clustering, compression, sparsification, and computer graphics.
2. Cycle Contraction Problem: The $C_\ell$-Contractibility problem asks whether a given graph can be transformed into an $\ell$-cycle through edge contraction operations. This problem is closely related to the "cyclicity" parameter of a graph, which is defined as the maximum length of a cycle to which the graph can be contracted.
3. Current State of Complexity Research:
   • $C_3$-Contractibility: Polynomial-time solvable
   • $C_4$-Contractibility: NP-complete on general graphs
   • $C_\ell$-Contractibility ($\ell \geq 5$): NP-complete on general graphs
   • $C_6$-Contractibility: NP-complete on bipartite graphs

Research Motivation

1. Theoretical Completeness: The complexity of $C_4$ and $C_5$ on bipartite graphs represents an important open problem in the field
2. Impact of Structural Restrictions: Investigating how graph structure restrictions (such as bipartiteness) affect computational complexity
3. Algorithm Design Guidance: Providing theoretical foundations for related algorithm design and optimization

Core Contributions

1. Main Theoretical Results: Proves that both $C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite graphs
2. Constructive Proofs: Provides constructive proofs through polynomial-time reductions from the Positive NAE-SAT problem
3. Technical Innovations:
   • For the $C_5$ problem, designs a two-step construction method: first constructing a non-bipartite graph $H$, then obtaining a bipartite graph $G$ through edge subdivision
   • For the $C_4$ problem, directly constructs a bipartite graph and proves its equivalence
4. Extended Results: Proves that $C_4$-Contractibility is NP-complete on $K_4$-free graphs with diameter 2

Methodology Details

Task Definition

Input: Bipartite graph $G = (V, E)$Output: Determine whether there exists a sequence of edge contractions transforming $G$ into $C_\ell$ ($\ell \in \{4,5\}$) Constraints: Only edge contraction operations are allowed; vertex deletion and edge addition are prohibited

Proof Strategy

Proof of $C_5$-Contractibility

Step One: Construction of Non-bipartite Graph $H$ Given a Positive NAE-SAT instance $\psi$ ($N$ variables, $M$ clauses):

1. Base Cycle: Add 5 vertices $V_\alpha = \{\alpha_0, \alpha_1, \alpha_2, \alpha_3, \alpha_4\}$ forming a 5-cycle
2. Variable Gadgets: For each variable $X_i$, add a 5-cycle $C_i = (x_0^i, x_1^i, x_2^i, x_3^i, x_4^i)$ and connect it to the base cycle
3. Clause Gadgets: For each clause $C_j$, add vertices $c_j, b_j$ and connect edges appropriately
4. Encoding Relations: Encode variable-clause relationships through edges $x_1^i c_j$ and $x_2^i b_j$

Step Two: Construction of Bipartite Graph $G$ Obtain bipartite graph $G$ by subdividing specific edge sets in $H$:

• Subdivide edge $\alpha_0\alpha_4$
• For each $i$, subdivide edges $x_0^i x_4^i, x_0^i \alpha_1, x_1^i \alpha_2, x_2^i \alpha_3, x_3^i \alpha_4$
• Subdivide certain variable-clause connection edges

Proof of $C_4$-Contractibility

Direct Construction of Bipartite Graph $G$:

1. Base Structure: Add vertices $t, f \in V$ and $t', f' \in V'$, with edges $tt', ff'$
2. Variable Gadgets: For each variable $X_i$, add vertex sets and establish appropriate connections
3. Clause Gadgets: For each clause $C_j$, add corresponding vertices and edges
4. Forcing Structure: Add auxiliary vertex sets $D$ and $D'$ to ensure specific positional relationships between vertex pairs in the witness structure

Technical Innovations

1. Two-Step Construction Method: For the $C_5$ problem, establishes equivalence on non-bipartite graphs first, then converts to bipartite graphs, avoiding the complexity of direct construction on bipartite graphs
2. Witness Structure Analysis: Introduces the concept of "nice witness structure" and systematically analyzes properties of $C_4$-witness structures
3. Reduction Correctness Proof:
   • Proves bipartiteness of the constructed graph
   • Proves equivalence between the original problem and the constructed graph
   • Establishes bijection between SAT problem solutions

Experimental Setup

This paper is purely theoretical research with no experimental validation. All results are obtained through mathematical proofs.

Experimental Results

Main Theoretical Results

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 diameter 2

Proof Highlights

1. NP Membership: Verification in polynomial time given a witness structure
2. NP-Hardness: Polynomial-time reduction from the known NP-complete problem Positive NAE-SAT
3. Construction Complexity: All constructions are completed in polynomial time

Related Work

Historical Development

1. Brouwer & Veldman (1987): Proved NP-completeness of $C_4$-Contractibility on general graphs
2. Hammack (1999, 2002): Studied cycle contraction problems on planar graphs
3. Dabrowski & Paulusma (2017): Proved NP-completeness of $C_6$-Contractibility on bipartite graphs

Related Problems

1. Path Contraction Problem: $P_\ell$-Contractibility is polynomial-time solvable on certain graph classes
2. General $H$-Contraction Problem: Complexity analysis on different graph classes
3. Parameterized Complexity: Study of contraction problems from a parameterized perspective

Conclusions and Discussion

Main Conclusions

1. Completely resolves the open problem posed by Dabrowski and Paulusma
2. Establishes a complete complexity landscape for small cycle contraction problems on bipartite graphs
3. Demonstrates the impact of graph structure restrictions on computational complexity

Limitations

1. Construction Complexity: The reduction constructs relatively large graphs, which may be inefficient in practical applications
2. Parameterized Analysis: Does not analyze the problem from a parameterized complexity perspective
3. Approximation Algorithms: Does not discuss the possibility of approximation algorithms

Future Directions

1. Other Graph Classes: Study complexity on other restricted graph classes
2. Parameterized Algorithms: Develop fixed-parameter tractable algorithms
3. Approximation Algorithms: Design algorithms with guaranteed approximation ratios
4. Longest Cycle Problem: Study the complexity of computing the cyclicity parameter of graphs

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Completely resolves an important open problem with high theoretical value
2. Technical Innovation: The two-step construction method and nice witness structure concept have methodological significance
3. Rigorous Proofs: All theorems have complete mathematical proofs with clear logic
4. Writing Quality: Well-structured paper with clear exposition and effective use of figures and tables

Weaknesses

1. Practical Limitations: Pure theoretical results lacking algorithm implementation and performance analysis
2. Construction Complexity: Relatively complex reduction constructions with high comprehension barriers
3. Extensibility: Insufficient discussion of implications for related problems

Impact

1. Academic Contribution: Fills an important gap in computational complexity theory
2. Methodological Value: Provides technical methods applicable to research on similar problems
3. Foundation for Future Research: Establishes foundation for further research in related fields

Applicable Scenarios

1. Theoretical Research: Graph theory and computational complexity theory research
2. Algorithm Design: Provides complexity-theoretic guidance for related algorithm design
3. Teaching Applications: Serves as a classical case study for NP-completeness proofs

References

The paper cites 29 related references, covering:

• Early work on graph contraction problems
• Foundations of computational complexity theory
• Related NP-completeness results
• Fundamental graph theory

Key references include Brouwer & Veldman (1987), Dabrowski & Paulusma (2017), Garey & Johnson (1979), and other classical works.