PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity, approximation, and extension of proper $\{a,b\}$-edge-weightings

Péter Madarasi, Máté Simon

arXiv:2609.31205v1cs.DMcs.CCmath.CO

TL;DR

The paper asks when two allowed edge weights can give adjacent vertices distinct incident-weight sums, and studies decision, optimization, and extension variants motivated by the 1-2-3 conjecture. The paper establishes complexity results and develops exact and approximation algorithms for proper edge-weightings and their variants. For every fixed distinct integer pair, deciding proper weighting is NP-complete on simple cubic planar graphs, and under ETH no 2^{o(√m)}-time algorithm exists on connected simple cubic planar graphs.

  • Problem

    The paper asks when two allowed edge weights can give adjacent vertices distinct incident-weight sums, and studies decision, optimization, and extension variants motivated by the 1-2-3 conjecture.

    Source: §1 · p. 1

  • Method

    The paper establishes complexity results and develops exact and approximation algorithms for proper edge-weightings and their variants.

    Source: §1.1 · pp. 1–2

  • Results

    For every fixed distinct integer pair, deciding proper weighting is NP-complete on simple cubic planar graphs, and under ETH no 2^{o(√m)}-time algorithm exists on connected simple cubic planar graphs.

    Source: §2.1 · p. 3, §2.2 · p. 8

  • Takeaways & Limitations

    On regular graphs, these results also apply to locally irregular 2-edge-coloring through its equivalence with proper {a, b}-edge-weightings.

    Source: §1 · p. 1, §1.1 · p. 1

    The exact-algorithm setting allows parallel edges but excludes loops.

    Source: §2.2 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

The paper studies proper two-weight edge assignments, motivated by the 1-2-3 conjecture and related graph-labeling problems. It establishes complexity, algorithmic, approximation, and extension results, with connections to locally irregular edge-colorings.

1 Introduction

  • On regular graphs, proper {a, b}-edge-weightings are equivalent to locally irregular 2-edge-colorings, linking the paper's decision and algorithmic results to that coloring problem.The 1-2-3 conjecture states that every simple graph without isolated edges has the {1, 2, 3}-property.Source: §1 · p. 1, §1.1 · p. 1

1.1 Our results

  • For every fixed pair of distinct integers, deciding whether a simple cubic planar graph has a proper {a, b}-edge-weighting is NP-complete; the square-root exponent is optimal under ETH.The paper also gives a deterministic 2^{O(√m)}-time algorithm on connected loopless planar multigraphs.Source: §1.1 · p. 1
  • Maximizing the number of proper edges admits an EPTAS on connected loopless planar multigraphs and a polynomial-time 1/2-approximation on loopless multigraphs, but is APX-complete on simple cubic graphs.Source: §1.1 · p. 2
  • Extending a partial weighting is NP-complete on simple cubic planar bipartite graphs, even when prescribed-edge components are length-6 paths, but is polynomial-time solvable on trees.The hardness also holds for locally irregular 2-edge-coloring under the same path restriction.Source: §1.1 · p. 2

1.2 Motivation and previous results

  • Neighbor-sum-distinguishing weightings arise from graph irregularity; irregularity strength seeks weights making all vertex sums pairwise distinct.The paper's properness condition instead requires distinct labels only at adjacent vertices.Source: §1 · p. 1, §1.2 · p. 2
  • The problem generalizes earlier {1, 2}-weighting hardness results [18, Theorem 1], [15, Theorem 1]; on regular graphs, affine transformations of two distinct weights preserve properness.This preservation extends the cubic-graph hardness result to every fixed distinct pair of integers a and b.Source: §1.2 · p. 2
  • Related work studies product-based edge and vertex weightings, locally irregular colorings [4, 9, 21], and bipartite-graph characterizations for particular weight pairs [30].Source: §1.2 · pp. 2–3

2 {a, b}-edge-weightings in planar graphs

This section studies the complexity and exact or subexponential algorithms for proper {a, b}-edge-weightings on simple cubic planar graphs, including ETH-based lower bounds and a transfer to locally irregular 2-edge-coloring. It also considers maximizing the number of proper edges on planar multigraphs, giving EPTAS results and noting that an FPTAS would imply P = NP.

2 {a, b}-edge-weightings in planar graphs

  • A deterministic EPTAS maximizes the number of proper edges on connected loopless planar multigraphs.Source: §2 · p. 3

2.1 NP-completeness for simple cubic planar graphs

  • For every fixed distinct a and b, deciding the {a, b}-property is NP-complete on simple cubic planar graphs; locally irregular 2-edge-coloring is also NP-complete there.Source: §2.1 · pp. 3, 7

2.2 Exact subexponential algorithm with a matching lower bound

  • A degree-cost separator decomposition and dynamic program find a proper weighting, or certify none exists, in deterministic 2^O(sqrt(m)) time on connected loopless planar multigraphs.Source: §2.2 · pp. 7–8
  • Under ETH, no 2^o(sqrt(m))-time algorithm decides the {a, b}-property on connected simple cubic planar graphs, for any fixed distinct a and b.Source: §2.2 · p. 8
  • Planarization and variable replacement yield a connected planar Monotone 2-in-4-SAT instance of size O(N^2), whose satisfying assignments correspond to proper weightings of a simple cubic planar graph.The graph has O(N^2) edges, and the construction preserves satisfiability between the formula and proper {0, 1}-edge-weighting.Source: §2.2 · p. 9
  • No 2^{o(√m)}-time algorithm exists for proper {a, b}-edge-weighting on simple cubic planar graphs under ETH, for any fixed distinct a and b.The reduction maps sparse 3-SAT instances with N variables to connected simple cubic planar graphs with O(N^2) edges, preserving satisfiability for {0, 1}; Proposition 2.1 transfers the lower bound to every fixed pair.Source: §2.2 · p. 9
  • Locally irregular 2-edge-coloring on simple cubic planar graphs has a deterministic 2^{O(√n)}-time algorithm and no 2^{o(√n)}-time algorithm under ETH.The equivalence with proper {0, 1}-edge-weighting holds componentwise.Source: §2.2 · p. 9

2.3 An EPTAS for the maximization problem

  • The EPTAS deletes BFS layer classes, then uses modular dynamic programming on remaining components; averaging over layer classes and prime moduli preserves at least a (1 − ε) fraction of optimal proper edges.The modular dynamic program uses states recording information for O(k) vertices.Source: §2.3 · p. 9
  • For every fixed distinct a and b, a deterministic EPTAS on connected loopless planar multigraphs returns a weighting with at least (1 − ε) OPTEW(G) proper edges in time 2^{O((1/ε) log(2/ε))}m^{O(1)}.Parallel edges are treated as distinct in vertex labels and the objective.Source: §2.3 · pp. 9, 12
  • The algorithm tests candidate weightings indexed by a partition choice and prime, using component dynamic programs and extending each solution to the whole graph.It chooses a pair for which many optimal proper edges remain inside the retained subgraph and have endpoint-label differences not divisible by the chosen prime.Source: §2.3 · p. 13
  • A (1 − ε)-approximation for Max {a, b}-edge-weighting on planar graphs follows by extending modular dynamic-program solutions to proper edge-weightings.The returned candidate has at least (1 − ε) OPTEW(G) proper edges.Source: §2.3 · p. 13
  • The EPTAS runs in 2^O((1/ε) log(2/ε))m^O(1) time in the standard bit model for fixed a and b.Its arithmetic-operation bound is 2^O((1/ε) log(2/ε))m^2.Source: §2.3 · pp. 13–14
  • Unless P = NP, no FPTAS exists for Max {a, b}-edge-weighting on simple cubic planar graphs.Setting ε = 1/(m + 1) would recover the exact integer optimum in polynomial time and decide the NP-complete problem from Theorem 2.2.Source: §2.3 · p. 14

3 APX-completeness for simple cubic graphs

The paper establishes APX-completeness for maximizing proper edges on simple cubic graphs and gives a polynomial-time 1/2-approximation on loopless multigraphs. Its hardness proof reduces cubic Max Cut using gadgets whose optimum value equals the cut optimum plus a fixed offset.

3 APX-completeness for simple cubic graphs

  • The approximation theorem treats parallel edges as distinct, while APX-completeness holds on simple cubic graphs.Source: §3 · p. 14
  • A polynomial-time 1/2-approximation for Max {a, b}-edge-weighting works on loopless multigraphs.It processes edges in order and chooses each weight to make at least half of the edges assigned to that step proper.Source: §3 · p. 14
  • Max {a, b}-edge-weighting is APX-complete for every fixed distinct pair a and b, even on simple cubic graphs.Source: §3 · p. 14
  • The reduction from cubic Max Cut satisfies OPTEW(G′) = K + OPTCUT(G), establishing APX-hardness for every fixed distinct pair.A cut S yields a weighting with K + |δG(S)| proper edges; conversely, majority values in vertex gadgets recover a cut, with noncrossing edges charged to distinct improper edges.Source: §3 · pp. 14–16

4 Extending partial edge-weightings

The paper establishes hardness for extending partial edge-weightings under strong planar, bipartite, and prescribed-path restrictions, while giving a polynomial-time algorithm for trees. It also reduces the antifactor problem on trees to proper {0, 1}-edge-weighting.

4 Extending partial edge-weightings

  • For every fixed distinct a and b, extension is NP-complete on simple cubic planar bipartite graphs, even when prescribed components are monochromatic paths of length 6.The corresponding locally irregular 2-edge-coloring extension problem has the same hardness, including the path restriction.Source: §4 · pp. 17–19

4.1 Extending on trees

  • For every fixed distinct a and b, a polynomial-time algorithm either extends a partial weighting on a tree to a proper one or reports that no extension exists.The dynamic program runs in O(|V|^3) time.Source: §4.1 · p. 19

4.2 The antifactor problem

  • The tree extension algorithm also gives a polynomial-time solution for the antifactor problem on trees, via a reduction to proper {0, 1}-edge-weighting.The reduction constructs a tree with O(n^3) vertices from an n-vertex antifactor instance.Source: §4.1 · p. 19, §4.2 · p. 20
Loading 2609.31205v1…