Metraipolis › archive › dc_3dbc13ee6093
Complexity, approximation, and extension of proper $\{a,b\}$-edge-weightings — arXiv:2609.31205
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.31205
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T02:59:25.675Z
- SHA-256 of the archived text
8b6393241e52b146a6b15b8b5e0ef3a23b1673d215d7864fe8feefaed1b82b7c- Stable URL of this page
https://metraipolis.com/documento/dc_3dbc13ee6093
How to cite
Complexity, approximation, and extension of proper $\{a,b\}$-edge-weightings — arXiv:2609.31205 — arXiv (en), https://arxiv.org/abs/2609.31205 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3dbc13ee6093 (Metraipolis archive dc_3dbc13ee6093, sha256 8b6393241e52b146a6b15b8b5e0ef3a23b1673d215d7864fe8feefaed1b82b7c)
BibTeX
@misc{dc3dbc13ee6093,
title = {Complexity, approximation, and extension of proper $a,b$-edge-weightings — arXiv:2609.31205},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.31205},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3dbc13ee6093; sha256 8b6393241e52b146a6b15b8b5e0ef3a23b1673d215d7864fe8feefaed1b82b7c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31205. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.CO).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Computational Complexity (cs.CC); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.31205 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T02:28:17.954Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).