Complexity, approximation, and extension of proper {a,b}-edge-weightings
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 2O(√m)-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude 2o(√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 2O(√n)-time algorithm on n-vertex graphs in this class, and admits no 2o(√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.
Related
- Hereditary Approximation under Hilbertian Extension
- Approximation and extension theorems for normal affine toric varieties
- Extension on the convergence rates of moment-SOS hierarchies via approximation of truncated moment sequences
- The best approximation tuple: an extension of the Cheney-Goldstein algorithm and results to the multiple sets case
- (Approximate) Symmetric Extension Complexity of the Spanning Tree Polytope
BibTeX
@misc{madarasi2026complexity,
title = {{Complexity, approximation, and extension of proper $\a,b\$-edge-weightings}},
author = {Péter Madarasi and Máté Simon},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31205},
eprint = {2609.31205},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31205},
}
RIS
TY - UNPB
TI - Complexity, approximation, and extension of proper {a,b}-edge-weightings
AU - Péter Madarasi
AU - Máté Simon
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31205
UR - https://arxiv.org/abs/2609.31205
AB - 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(√m)-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude 2^o(√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(√n)-time algorithm on n-vertex graphs in this class, and admits no 2^o(√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.
ER -