Complexity and approximation of edge-weightings in planar cubic graphs
Complexity, approximation, and extension of proper $\{a,b\}$-edge-weightings
Discrete MathematicsComputational Complexity
Summary
This paper studies how to assign one of two numbers to the edges of a graph so that connected points have different sums of these numbers. The authors show that deciding if such an assignment exists is a hard problem, even on simple structured graphs, and they provide limits on how fast algorithms can solve it. They also offer ways to approximate solutions efficiently and investigate the difficulty of extending partial assignments. The results clarify the computational boundaries and provide algorithms for certain graph types.
What this means in practice
- •For graph algorithm designers: Avoid spending time on fast exact algorithms for proper edge-weighting in planar cubic graphs due to provable complexity limits under ETH assumptions.
- •For approximation algorithm developers: Use the provided efficient polynomial-time approximation scheme to find near-optimal edge-weight assignments on planar multigraphs when exact solutions are too costly.
A theory result. No direct application yet.
Authors
Péter Madarasi, Máté Simon
Abstract
For distinct integers $a$ and $b$, an $\{a,b\}$-edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting is proper if adjacent vertices receive distinct labels. We prove that, for every fixed pair of distinct integers, deciding whether a proper weighting exists is NP-complete even for simple cubic planar graphs. On planar multigraphs with $m$ edges, we give an exact $2^{O(\sqrt m)}$-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude $2^{o(\sqrt m)}$-time algorithms even for simple cubic planar graphs. As a consequence, locally irregular $2$-edge-coloring is NP-complete on simple cubic planar graphs, admits a deterministic $2^{O(\sqrt n)}$-time algorithm on $n$-vertex graphs in this class, and admits no $2^{o(\sqrt n)}$-time algorithm under ETH. For maximizing the number of edges joining vertices with distinct labels, we give a deterministic efficient polynomial-time approximation scheme (EPTAS) on planar multigraphs, a polynomial-time $1/2$-approximation on multigraphs, and APX-completeness even on simple cubic graphs. Extending a partial $\{a,b\}$-edge-weighting to a proper one is NP-complete for every fixed pair even on simple cubic planar bipartite graphs, while it is polynomial-time solvable on trees. The hardness persists even when the prescribed edges form disjoint paths of length $6$ and all edges of each path have the same prescribed weight.