Complexity of mapping edges in cubic graphs reveals new hardness result
Computational complexity of the $H$-coloring problem in cubic graphs
Computational Complexity
Summary
This paper looks at a puzzle about matching edges between certain 3-regular graphs, called cubic graphs. The authors study when it is easy or hard to decide if such a matching exists for a fixed small graph viewed as a pattern. They disprove a previous guess by showing a specific small case is actually hard to solve, meaning no quick method is likely. They also provide an algorithm that solves these problems somewhat faster than brute force for any fixed pattern. This helps understand which cases of the problem need lots of computing time and which might not.
What this means in practice
- •For graph algorithm designers: Avoid assuming polynomial-time algorithms exist for all fixed small pattern graphs when designing coloring tests with cubic graphs.
- •For complexity theorists: Use the new hardness result to refine classifications of graph homomorphism problems restricted to cubic graphs.
A theory result. No direct application yet.
Authors
Vahan Mkrtchyan
Abstract
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$.