{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.31205",
  "author_total": 2,
  "authors": [
    {
      "name": "Péter Madarasi"
    },
    {
      "name": "Máté Simon"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/1tfepexyj75y3.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.31205",
  "fulltext_url": null,
  "id": "1tfepexyj75y3",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.31205",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Graph Labeling and Dimension Problems"
    ]
  ],
  "openalex": "W7214674077",
  "pdf_url": "https://arxiv.org/pdf/2609.31205",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-25",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/1tfepexyj75y3.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:24:57Z",
      "native_id": "2609.31205",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.31205"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Complexity, approximation, and extension of proper $\\{a,b\\}$-edge-weightings",
  "title_text": "Complexity, approximation, and extension of proper {a,b}-edge-weightings",
  "type": "preprint",
  "updated_at": "2026-10-30T12:24:57Z",
  "url": "https://research.draconitic.com/paper/1tfepexyj75y3",
  "venue": "arXiv",
  "versions": []
}