Abstract
This paper investigates the computational complexity of determining whether a planar graph $G$ is a subgraph of a $k$-connected, 3-regular (cubic) planar graph $H$. This problem, known as the 3-augmentation problem, is central to understanding graph structure and has significant implications for the long-standing 3-edge-colorability problem. We show that while the problem is solvable in polynomial time for $k=1$ and $k=2$, it becomes NP-complete for $k=3$.
Introduction
A fundamental question in algorithmic graph theory is the "growth" potential of graphs: can a given simple planar graph $G$ be augmented into a more structured supergraph $H$? Specifically, this research focuses on subgraphs of $k$-connected, 3-regular planar graphs. The motivation is twofold: advancing the theory of graph augmentation and exploring the boundaries of the 3-edge-colorability problem for planar graphs.
The 3-Augmentation Problem
The core challenge is the 3-augmentation problem. Given a planar subcubic graph $G$ (maximum degree 3), the goal is to determine if edges and vertices can be added to form a supergraph $H$ that is planar, 3-regular, and $k$-connected. This problem is intrinsically linked to the 3-edge-colorability problem. According to the Four-Color Theorem and Tait's work, every 2-connected, 3-regular planar graph is 3-edge-colorable. Identifying subgraphs of such graphs provides a pathway toward solving the polynomial-time decidability of 3-edge-colorability for general planar subcubic graphs.
Methodology
The researchers categorized their approach based on the flexibility of the graph's embedding:
- Fixed Embedding: For a fixed planar embedding, the problem is reduced to the Generalized Factor problem. By constructing a bipartite graph mapping vertices to faces, the authors use "B-factors" to determine if valid edges can be added within faces to meet connectivity goals.
- Variable Embedding: When the embedding is not fixed, the search space grows exponentially. The authors employ SPQR-trees to decompose 2-connected graphs into triconnected components, applying dynamic programming to evaluate if any valid embedding supports a 2-connected 3-augmentation.
- NP-Hardness: To prove NP-completeness for the 3-connected case ($k=3$), a reduction from Planar-Monotone-3SAT was developed. This involved designing intricate gadgets (variable, splitter, and clause gadgets) that map boolean satisfiability to graph augmentation possibilities.
Results and Complexity Landscape
The study provides a comprehensive map of the complexity landscape for 3-augmentation. A significant "complexity jump" occurs at $k=3$. While 1- and 2-connectivity requirements allow for efficient polynomial-time algorithms, 3-connectivity introduces coordination constraints that render the problem NP-complete.
Key findings include:
- $k=1$ (Connected): Solvable in $O(n^2)$ (fixed) or $O(n)$ (variable) time.
- $k=2$ (2-Connected): Solvable in $O(n^4)$ (fixed) or $O(n^2)$ (variable) time.
- $k=3$ (3-Connected): NP-complete for variable embeddings, even if the input graph is already connected.
Conclusion
This work refines previous results by showing that the 3-connected case remains hard even when an arbitrary number of new vertices can be added. A remaining open problem is the complexity of the 3-connected case with a fixed embedding. Furthermore, while 2-connected 3-augmentation is sufficient for 3-edge-colorability, it is not necessary, leaving a gap for future research to bridge.
Summary updated