Source-linked AI summary
Computational complexity of the $H$-coloring problem in cubic graphs
Vahan Mkrtchyan
TL;DR
The paper studies whether a fixed connected cubic graph H colors a given connected cubic graph G, against a conjecture predicting polynomial-time solvability for certain H. It proves S6-coloring NP-complete under P ≠ NP and presents an exponential-time algorithm for simple connected cubic H.
Problem
The paper asks whether a fixed connected cubic graph H colors an input connected cubic graph G, in light of a conjecture that the problem is polynomial-time solvable when H does not admit a P12-coloring.
Source: §1 · pp. 3–4Method
The paper establishes NP-completeness for S6-coloring and develops an exponential-time algorithm for H-coloring.
Source: §1 · p. 4, §4 · p. 10Results
S6-coloring is NP-complete under P ≠ NP, and the algorithm runs in O*(sqrt(8)^n) time for simple connected cubic H.
Source: §1 · p. 4, §4 · p. 10Takeaways & Limitations
The result disproves the conjecture that H-coloring is polynomial-time solvable whenever H does not admit a P12-coloring, assuming P ≠ NP.
Source: §1 · p. 4The stated algorithmic guarantee is for simple connected cubic H.
Source: §4 · pp. 10–11
Abstract
from arXiv · showhide
If $G$ and $H$ are two cubic graphs, then an $H$-coloring of $G$ is a mapping $f: E(G)\rightarrow E(H)$, such that for every $v\in V(G)$ there is a vertex $x\in V(H)$, such that $f(\partial_G(v))=\partial_H(x)$. If $G$ admits an $H$-coloring then it is common to write $H\prec G$. In this paper, for a fixed connected cubic graph $H$, we consider a decision problem, which we call $H$-coloring. In this problem, on the input one is given a connected cubic graph $G$. The goal is to decide whether $H\prec G$. A conjecture by Hakobyan and the author states that $H$-coloring is polynomial time solvable, if $H$ does not admit a $P_{12}$-coloring. Here $P_{12}$ is the unique cubic graph obtained from the Petersen graph by expanding one of its vertices into a triangle. In this paper, we disprove this conjecture under $P\neq NP$, by showing that $S_6$-coloring is NP-complete. Here $S_6$ is the unique cubic graph on six vertices having exactly one bridge. Our second result is an algorithm that solves $H$-coloring problem in time $O^*(c^n)$, where $H$ is a simple connected cubic graph, $n$ is the number of vertices of the input cubic graph $G$ and $c=\sqrt{8}\approx 2.8284$.
1. Introduction
The introduction defines H-coloring for cubic graphs and situates it among coloring conjectures and prior results. It announces that S6-coloring is NP-complete and gives an exponential-time algorithm for simple connected cubic H.
1. Introduction
- Earlier conjectures proposed universal S10-colorability for cubic graphs and universal S12-colorability when a perfect matching exists, but counterexamples disprove these claims.The introduction also recalls that the conjecture P12 ≺ G for bridgeless cubic graphs with k(G) ≤ 4 has counterexamples.Source: §1 · p. 3
- H-coloring asks whether a fixed connected cubic graph H colors an input connected cubic graph G, with edge images around each vertex matching the edges incident to some vertex of H.The relation is transitive: if H colors G and K colors H, then K colors G.Source: §1 · pp. 2–4
- The paper disproves under P ≠ NP the conjecture that H-coloring is polynomial-time solvable when H does not admit a P12-coloring.P12 is the cubic graph formed by expanding one Petersen-graph vertex into a triangle.Source: §1 · pp. 3–4
- S6-coloring is NP-complete, while prior work shows every bridgeless cubic graph admits an S6-coloring.S4-colorability and S6-colorability coincide because of S6's symmetry.Source: §1 · pp. 3–4
- The paper also announces an O*(sqrt(8)^n)-time algorithm for H-coloring when H is a simple connected cubic graph.Here n is the number of vertices of the input graph G.Source: §1 · p. 4
2. Computational complexity of S6-coloring
The section proves that S6-coloring is NP-complete by reducing from a constrained S4-coloring problem built from 3-edge-coloring. The reductions use gadgets to encode edge-coloring constraints and transfer them to S6-coloring.
2. Computational complexity of S6-coloring
- For every connected cubic graph H, H-coloring lies in NP because a proposed coloring can be checked in polynomial time.The verification checks whether the incident edge colors at each input vertex form the incident-edge set of a vertex in H.Source: §2 · p. 4
- The K and K′ gadgets preserve the specified color constraints through their marked edges and pendant edges.For K, fixing uv to a forces its two pendant edges to share a color in {a, a3, a4}; K′ extends and transfers this behavior using uv and one copy of bc.Source: §2 · pp. 5–6
- Problem 1 is NP-complete: it asks whether a bridgeless cubic graph has an S4-coloring assigning color a to every edge in a specified set E0.The reduction from 3-edge-coloring replaces each edge of the source graph with a copy of K′ and uses specified edges to encode the constraint.Source: §2 · pp. 7–8
- The first reduction encodes 3-edge-colorability through an S4-coloring with no edge colored a.The section uses the equivalence between such an S4-coloring and χ′(G)=3.Source: §2 · pp. 4, 8
- S6-coloring is NP-complete.Membership in NP follows because a proposed H-coloring can be verified in polynomial time; NP-hardness is established by reduction from Problem 1.Source: §2 · pp. 4, 8
- Replacing each edge in E0 with two copies of S4 yields an S6-coloring instance equivalent to the original Problem 1 instance.In one direction, the S4-coloring extends by coloring the new bridges a; in the other, each bridge maps to a bridge of S4, whose color is a, recovering the required constraint.Source: §2 · pp. 4, 8, 9
3. An exponential algorithm for H-coloring
The section improves the exponential-time approach to H-coloring when H is simple, using forced edge colors to reduce the search. It also describes a simpler O*(8^n) enumeration bound.
3. An exponential algorithm for H-coloring
- The simpler enumeration considers at most four color options per edge after the first, yielding an O*(8^n) running time.The input graph is connected, and its edges are ordered so each later edge has an earlier neighbor.Source: §3 · p. 9
- For simple connected cubic H, the algorithm improves the constant in the O*(8^n) bound for solving H-coloring.The supplied passages do not state the improved constant explicitly.Source: §3 · p. 9
- The algorithm seeks at least 3|V|/4 edges with one color option, reducing the number of options that must be considered.E1 is the set of edges with one option; the resulting option count gives the improved running time.Source: §3 · p. 9
- The forced-edge counting argument shows every component of G[E1] has at least four vertices, bounding the number of components.The proof rules out isolated edges and three-vertex components.Source: §3 · p. 10
- Because H is simple, fixing the colors of two adjacent edges uniquely determines the third, which can then be removed from further consideration.The edges are ordered so each edge after the first has an earlier neighbor.Source: §3 · p. 10
4. Conclusion and future work
The paper establishes S6-coloring as NP-complete and gives an exponential-time algorithm for H-coloring under a simplicity condition. It leaves several complexity questions open and conjectures that the algorithm's running-time constant can be improved.
4. Conclusion and future work
- The paper proves S6-coloring NP-complete and gives an O*(8^n)-time algorithm when H is a simple connected cubic graph.Here n is the number of vertices of the input cubic graph G.Source: §4 · p. 10
- Whether H-coloring is NP-complete for S10, S12, P10, or P12 remains an open question in the paper.The paper proposes that H-coloring may be NP-complete for every fixed connected cubic graph H.Source: §4 · p. 11
- The author says the algorithm's constant 8 may not be best and conjectures an O*(2^n)-time algorithm.Source: §4 · p. 11