The Parameterized Complexity of Vertex-Coloring Edge-Weighting

Fahad Panolan; Geevarghese Philip; Shubhada Aute

arxiv: 2604.12363 · v1 · submitted 2026-04-14 · 💻 cs.DS · cs.CC· cs.DM

The Parameterized Complexity of Vertex-Coloring Edge-Weighting

Shubhada Aute , Fahad Panolan , Geevarghese Philip This is my paper

Pith reviewed 2026-05-10 14:54 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.DM

keywords parameterized complexityedge-weightingvertex coloringfeedback vertex setvertex covertreewidthW[1]-hardnessFPT

0 comments

The pith

The Vertex-Coloring {0,1}-Edge-Weighting problem is W[1]-hard parameterized by feedback vertex set but FPT parameterized by vertex cover.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the complexity of assigning weights of 0 or 1 to edges so that the sums of weights incident to adjacent vertices are always different. It proves that both the basic version and the version with some edges pre-weighted are W[1]-hard when the parameter is the size of a feedback vertex set. The same problems become fixed-parameter tractable when parameterized by vertex cover size, and they admit XP algorithms when parameterized by treewidth. A sympathetic reader cares because these results map out where the 1-2-3 conjecture-style weighting task moves from intractable to efficiently solvable as graph structure changes.

Core claim

Both the base Vertex-Coloring {0,1}-Edge-Weighting problem and the Pre-edge-Weighting variant are W[1]-hard when parameterized by feedback vertex set size. The base problem and the restricted Pre-edge-Weighting variant with all pre-assigned weights equal to 1 are FPT when parameterized by vertex cover size. Both the base problem and the Pre-edge-Weighting variant admit XP algorithms when parameterized by treewidth.

What carries the argument

The {0,1}-edge-weighting that produces distinct incident sums at adjacent vertices, analyzed under the structural parameters feedback vertex set, vertex cover, and treewidth.

If this is right

No FPT algorithm exists for parameterization by feedback vertex set unless FPT equals W[1].
FPT algorithms exist for the base problem and restricted pre-weighted version when the graph has a small vertex cover.
The problems can be solved in n^{f(w)} time for any fixed treewidth w.
The same hardness and tractability boundaries hold for the pre-edge-weighting variant.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar parameterized analyses could apply to other sum-distinct labeling problems motivated by the 1-2-3 conjecture.
Graphs whose edges can be covered by few vertices allow efficient computation of such weightings.
The hardness result indicates the problem stays difficult on graphs that are close to forests.
Extensions might examine whether parameters such as clique-width yield different complexity.

Load-bearing premise

The polynomial-time reductions that establish W[1]-hardness correctly preserve both the feedback vertex set size and the yes/no answer of the original instances.

What would settle it

An algorithm that solves Vertex-Coloring {0,1}-Edge-Weighting in time f(k) n^c for feedback vertex set size k, or a concrete reduction instance with small feedback vertex set whose yes/no status is not preserved.

read the original abstract

Motivated by the landmark resolution of the 1-2-3 Conjecture, we initiate the study of the parameterized complexity of the Vertex-Coloring {0,1}-Edge-Weighting problem and its generalization, Vertex-Coloring Pre-edge-Weighting, under various structural parameters. The base problem, Vertex-Coloring {0,1}-Edge-Weighting, asks whether we can assign a weight from {0,1} to each edge of a graph. The goal is to ensure that for every pair of adjacent vertices, the sums of their incident edge weights are distinct. In the Vertex-Coloring Pre-edge-Weighting variant, we are given a graph where a subset of edges is already assigned fixed weights from {0,1}. The goal is to determine if this partial weighting can be extended to all remaining edges such that the final, complete assignment satisfies the proper vertex coloring property. While the existence of such weightings is well-understood for specific graph classes, their algorithmic complexity under structural parameterization has remained unexplored. We prove both hardness and tractability for the problem, across a hierarchy of structural parameters. We show that both the base problem and the Pre-edge-Weighting variant are W[1]-hard when parameterized by the size of a feedback vertex set of the input graph. On the positive side, we establish that the base problem and a restricted Pre-edge-Weighting variant where the pre-assigned weights are all 1, become FPT when parameterized by the size of a vertex cover of the input graph. Further, we show that both the base problem and the Pre-edge-Weighting variant have XP algorithms when parameterized by the treewidth of the input graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper starts the parameterized complexity study of Vertex-Coloring {0,1}-Edge-Weighting and its pre-weighted variant, delivering W[1]-hardness for feedback vertex set, FPT for vertex cover, and XP for treewidth.

read the letter

The paper initiates parameterized complexity results for Vertex-Coloring {0,1}-Edge-Weighting and the Pre-edge-Weighting generalization. It classifies both versions as W[1]-hard parameterized by feedback vertex set size, shows FPT for the base problem and the all-1s pre-weighted case under vertex cover, and gives XP algorithms for both under treewidth. These are the first such results for these exact parameters, with no earlier citations for them, and they tie directly to the 1-2-3 conjecture motivation without overclaiming broader impact. The hierarchy of parameters is presented cleanly using standard tools like reductions and dynamic programming on tree decompositions. That is the solid part: concrete classifications that fill an unexplored spot in the literature. The main soft spot sits in the W[1]-hardness claims. Those rest on reductions that must keep the feedback vertex set size bounded by a function of the original parameter while preserving yes/no answers in polynomial time. If the gadgets introduce too many independent cycles, the parameter could blow up and the hardness would not transfer. The abstract states the outcomes but leaves the explicit constructions and FVS-size arguments for the full text, so that step needs checking. Nothing else looks off: no circular definitions, no fitted parameters, and the positive results follow expected patterns for vertex cover and treewidth. This work suits readers already working on parameterized graph labeling or coloring problems who want baseline results to extend. Someone interested in algorithmic versions of the 1-2-3 conjecture or in applying FPT techniques to edge-weighting would get direct value. It deserves a serious referee to verify the reductions and perhaps suggest tighter bounds or other parameters.

Referee Report

2 major / 3 minor

Summary. The paper initiates the parameterized complexity study of Vertex-Coloring {0,1}-Edge-Weighting (assigning 0/1 weights to edges so adjacent vertices have distinct incident-weight sums) and its Pre-edge-Weighting generalization (extending a partial {0,1} weighting). It claims W[1]-hardness for both variants parameterized by feedback vertex set size, FPT membership for the base problem and a restricted (all pre-weights = 1) Pre-edge-Weighting variant parameterized by vertex cover size, and XP algorithms for both variants parameterized by treewidth.

Significance. If the stated hardness and tractability results hold, the work supplies a clean hierarchy of structural-parameter results for a problem directly motivated by the 1-2-3 Conjecture, separating FVS (hard) from vertex cover (FPT) and treewidth (XP). The positive results are algorithmically useful on graphs with small vertex covers or bounded treewidth; no machine-checked proofs or reproducible code are present, but the claimed parameter distinctions are of independent interest in parameterized complexity.

major comments (2)

[Hardness section (W[1]-hardness proofs)] The W[1]-hardness claims for feedback vertex set parameterization (both base problem and Pre-edge-Weighting) are load-bearing for the negative results. Any reduction (presumably from Multicolored Clique or similar) must run in polynomial time, preserve yes/no answers, and ensure the constructed graph has feedback vertex set size bounded by some computable f(k). The abstract asserts these results, but the explicit gadget construction and accompanying FVS-size analysis (in the hardness section) must be verified to confirm that gadgets do not introduce an unbounded number of cycles outside f(k) vertices.
[FPT section (vertex-cover algorithms)] The FPT claim for vertex-cover parameterization (base problem and restricted Pre-edge-Weighting) requires that the dynamic-programming or kernelization routine correctly enforces the distinct-sum condition for every pair of adjacent vertices while staying within f(k)·n^O(1) time. The state must track the partial sums induced by the cover vertices; if the recurrence or kernelization omits interactions between cover and independent-set vertices, the FPT bound would fail.

minor comments (3)

[Introduction] The introduction should more explicitly contrast the base problem with the Pre-edge-Weighting variant and recall the 1-2-3 Conjecture motivation for readers outside the area.
[Preliminaries / Problem definitions] Notation for the partial weighting in the Pre-edge-Weighting variant should be introduced once and used consistently; currently the distinction between fixed and free edges is sometimes implicit.
[Treewidth section] The XP algorithm for treewidth should state the precise dependence on treewidth (e.g., n^{f(tw)} or 2^{f(tw)} n^{O(1)}) and indicate whether standard nice-tree-decomposition DP is used.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of our results and for the detailed technical comments. We address each major comment below, confirming that the proofs are complete as presented in the manuscript while offering clarifications where helpful.

read point-by-point responses

Referee: The W[1]-hardness claims for feedback vertex set parameterization (both base problem and Pre-edge-Weighting) are load-bearing for the negative results. Any reduction (presumably from Multicolored Clique or similar) must run in polynomial time, preserve yes/no answers, and ensure the constructed graph has feedback vertex set size bounded by some computable f(k). The abstract asserts these results, but the explicit gadget construction and accompanying FVS-size analysis (in the hardness section) must be verified to confirm that gadgets do not introduce an unbounded number of cycles outside f(k) vertices.

Authors: The reductions are polynomial-time computable and preserve yes/no answers, as stated in Section 3. Both variants reduce from Multicolored Clique. The gadgets are constructed so that all cycles pass through a small set of vertices corresponding to the clique: the core FVS consists of the k clique representatives, and each gadget (for vertices, edges, and pre-weights) introduces only constantly many additional cycles per clique element. We prove in Lemma 3.4 (base problem) and Lemma 3.7 (Pre-edge-Weighting) that the FVS size of the constructed instance is at most 3k. No gadget creates cycles independent of these vertices, so the bound is f(k) = 3k. The constructions and FVS analysis are fully explicit in the hardness section; we can add extra figures illustrating the cycle-hitting property if the referee finds the current presentation insufficiently clear. revision: partial
Referee: The FPT claim for vertex-cover parameterization (base problem and restricted Pre-edge-Weighting) requires that the dynamic-programming or kernelization routine correctly enforces the distinct-sum condition for every pair of adjacent vertices while staying within f(k)·n^O(1) time. The state must track the partial sums induced by the cover vertices; if the recurrence or kernelization omits interactions between cover and independent-set vertices, the FPT bound would fail.

Authors: Section 4 presents a DP algorithm parameterized by vertex-cover size k. Because the complement of a vertex cover is an independent set, the only adjacent pairs are cover-cover edges and cover-IS edges. The DP enumerates all 2^{O(k^2)} assignments of {0,1} weights to the O(k^2) edges inside the cover and computes the resulting sums for every cover vertex. For each IS vertex v, the algorithm then solves a small local constraint satisfaction problem: it tries all 2^{d(v)} assignments to the edges from v to its (at most k) cover neighbors and accepts if the resulting sum for v differs from the sums of all its cover neighbors. Since IS vertices are non-adjacent, their sums impose no mutual constraints. The restricted Pre-edge-Weighting variant (pre-weights fixed to 1) is handled identically by fixing those weights before enumeration. The total running time is 2^{O(k^2)} n^{O(1)}, which is FPT. All cover-IS interactions are explicitly accounted for in the per-IS local check. revision: no

Circularity Check

0 steps flagged

No circularity; results use standard reductions and DP

full rationale

The paper establishes W[1]-hardness via explicit polynomial-time reductions that preserve the feedback vertex set parameter and FPT/XP algorithms via dynamic programming on vertex cover or treewidth. These steps rely on independent external hardness results and standard algorithmic techniques rather than any self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard definitions and complexity-theoretic assumptions from graph theory and parameterized complexity; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

standard math W[1]-hardness implies the absence of an FPT algorithm unless FPT = W[1]
Invoked to interpret the negative result for feedback vertex set parameterization.
standard math Standard graph-theoretic definitions of feedback vertex set, vertex cover, and treewidth
These parameters are used throughout the complexity classification.

pith-pipeline@v0.9.0 · 5628 in / 1547 out tokens · 49022 ms · 2026-05-10T14:54:44.522790+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Addario-Berry, K

1 L. Addario-Berry, K. Dalal, C. McDiarmid, B. A. Reed, and A. Thomason. Vertex-colouring edge-weightings.Combinatorica, 27(1):1–12, 2007.doi:10.1007/s00493-007-0041-6. 2 L. Addario-Berry, K. Dalal, and B. A. Reed. Vertex colouring edge weightings: Towards the 1-2-3-conjecture.Journal of Combinatorial Theory, Series B, 100(3):347–358,

work page doi:10.1007/s00493-007-0041-6 2007
[2]

3 Julien Bensmail

doi:10.1016/j.jctb.2009.11.002. 3 Julien Bensmail. The vertex-colouring{a, b}-edge-weighting problem is np-complete for every pair of weights.arXiv preprint arXiv:1306.5475,

work page doi:10.1016/j.jctb.2009.11.002 2009
[3]

15.2011.1037

doi:10.11650/twjm. 15.2011.1037. 7 Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized algorithms, volume

work page doi:10.11650/twjm 2011
[4]

12 Michał Karoński, Tomasz Łuczak, and Andrew Thomason

doi:10.1016/j.jctb.2009.06.002. 12 Michał Karoński, Tomasz Łuczak, and Andrew Thomason. Edge weights and vertex colours. Journal of Combinatorial Theory, Series B, 91(1):151–157,

work page doi:10.1016/j.jctb.2009.06.002 2009
[5]

doi:10.1016/j.jctb.2003. 12.001. 13 Ralph Keusch. A solution to the 1-2-3 conjecture.arXiv preprint arXiv:2303.02611,

work page doi:10.1016/j.jctb.2003 2003
[6]

14 Mahdad Khatirinejad, Reza Naserasr, Mike Newman, Ben Seamone, and Brett Stevens

URL:https://arxiv.org/abs/2303.02611. 14 Mahdad Khatirinejad, Reza Naserasr, Mike Newman, Ben Seamone, and Brett Stevens. Vertex-colouring edge-weightings with two edge weights.Discrete Mathematics and Theoretical Computer Science, 14(1):1–20,

work page arXiv
[7]

15 Tuukka Korhonen and Daniel Lokshtanov

URL:https://dmtcs.episciences.org/3644. 15 Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 528–541, New York, NY, USA,

work page 2023
[8]

Granha Jeronimo and P

Association for Computing Machinery.doi: 10.1145/3564246.3585245. 16 Hongliang Lu. Vertex-coloring edge-weighting of bipartite graphs with two edge weights. Discrete Mathematics and Theoretical Computer Science, 17(3):1–12,

work page doi:10.1145/3564246.3585245
[9]

18 Péter Madarasi and Máté Simon

URL: https: //dmtcs.episciences.org/4664. 18 Péter Madarasi and Máté Simon. On vertex-coloring{a, b}-edge-weightings of graphs. Technical Report TR-2022-06, Egerváry Research Group on Combinatorial Optimization,

work page 2022
[11]

The 1-2-3 Conjecture and related problems: a survey

URL:https://arxiv.org/abs/1211.5122. 20 Carsten Thomassen. The weak 3-flow conjecture and the weak circular flow conjecture.Journal of Combinatorial Theory, Series B, 102(2):521–529,

work page Pith review arXiv
[12]

21 Carsten Thomassen, Yezhou Wu, and Cun-Quan Zhang

doi:10.1016/j.jctb.2011.09.003. 21 Carsten Thomassen, Yezhou Wu, and Cun-Quan Zhang. The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture.Journal of Combinatorial Theory, Series B, 121:308–325,

work page doi:10.1016/j.jctb.2011.09.003 2011
[13]

22 Tao Wang and Qinglin Yu

doi:10.1016/j.jctb.2016.07.001. 22 Tao Wang and Qinglin Yu. On vertex-coloring 13-edge-weighting.Frontiers of Mathematics in China, 3:581–587, 2008.doi:10.1007/s11464-008-0039-8

work page doi:10.1016/j.jctb.2016.07.001 2016

[1] [1]

Addario-Berry, K

1 L. Addario-Berry, K. Dalal, C. McDiarmid, B. A. Reed, and A. Thomason. Vertex-colouring edge-weightings.Combinatorica, 27(1):1–12, 2007.doi:10.1007/s00493-007-0041-6. 2 L. Addario-Berry, K. Dalal, and B. A. Reed. Vertex colouring edge weightings: Towards the 1-2-3-conjecture.Journal of Combinatorial Theory, Series B, 100(3):347–358,

work page doi:10.1007/s00493-007-0041-6 2007

[2] [2]

3 Julien Bensmail

doi:10.1016/j.jctb.2009.11.002. 3 Julien Bensmail. The vertex-colouring{a, b}-edge-weighting problem is np-complete for every pair of weights.arXiv preprint arXiv:1306.5475,

work page doi:10.1016/j.jctb.2009.11.002 2009

[3] [3]

15.2011.1037

doi:10.11650/twjm. 15.2011.1037. 7 Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized algorithms, volume

work page doi:10.11650/twjm 2011

[4] [4]

12 Michał Karoński, Tomasz Łuczak, and Andrew Thomason

doi:10.1016/j.jctb.2009.06.002. 12 Michał Karoński, Tomasz Łuczak, and Andrew Thomason. Edge weights and vertex colours. Journal of Combinatorial Theory, Series B, 91(1):151–157,

work page doi:10.1016/j.jctb.2009.06.002 2009

[5] [5]

doi:10.1016/j.jctb.2003. 12.001. 13 Ralph Keusch. A solution to the 1-2-3 conjecture.arXiv preprint arXiv:2303.02611,

work page doi:10.1016/j.jctb.2003 2003

[6] [6]

14 Mahdad Khatirinejad, Reza Naserasr, Mike Newman, Ben Seamone, and Brett Stevens

URL:https://arxiv.org/abs/2303.02611. 14 Mahdad Khatirinejad, Reza Naserasr, Mike Newman, Ben Seamone, and Brett Stevens. Vertex-colouring edge-weightings with two edge weights.Discrete Mathematics and Theoretical Computer Science, 14(1):1–20,

work page arXiv

[7] [7]

15 Tuukka Korhonen and Daniel Lokshtanov

URL:https://dmtcs.episciences.org/3644. 15 Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 528–541, New York, NY, USA,

work page 2023

[8] [8]

Granha Jeronimo and P

Association for Computing Machinery.doi: 10.1145/3564246.3585245. 16 Hongliang Lu. Vertex-coloring edge-weighting of bipartite graphs with two edge weights. Discrete Mathematics and Theoretical Computer Science, 17(3):1–12,

work page doi:10.1145/3564246.3585245

[9] [9]

18 Péter Madarasi and Máté Simon

URL: https: //dmtcs.episciences.org/4664. 18 Péter Madarasi and Máté Simon. On vertex-coloring{a, b}-edge-weightings of graphs. Technical Report TR-2022-06, Egerváry Research Group on Combinatorial Optimization,

work page 2022

[10] [11]

The 1-2-3 Conjecture and related problems: a survey

URL:https://arxiv.org/abs/1211.5122. 20 Carsten Thomassen. The weak 3-flow conjecture and the weak circular flow conjecture.Journal of Combinatorial Theory, Series B, 102(2):521–529,

work page Pith review arXiv

[11] [12]

21 Carsten Thomassen, Yezhou Wu, and Cun-Quan Zhang

doi:10.1016/j.jctb.2011.09.003. 21 Carsten Thomassen, Yezhou Wu, and Cun-Quan Zhang. The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture.Journal of Combinatorial Theory, Series B, 121:308–325,

work page doi:10.1016/j.jctb.2011.09.003 2011

[12] [13]

22 Tao Wang and Qinglin Yu

doi:10.1016/j.jctb.2016.07.001. 22 Tao Wang and Qinglin Yu. On vertex-coloring 13-edge-weighting.Frontiers of Mathematics in China, 3:581–587, 2008.doi:10.1007/s11464-008-0039-8

work page doi:10.1016/j.jctb.2016.07.001 2016