{"id":"ac6656c8-c4c8-4d79-89c0-b1a52f4790be","arxiv_id":"2607.27004","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Fair Coloring is W[1]-hard by number of groups even on forests and modular-width-2 graphs (k=2), but FPT by neighborhood diversity (for k=2) and by neighborhood diversity plus number of groups in general.","lead":"The paper maps the parameterized complexity of fair graph coloring under group-balance constraints. It shows the problem is already hard on forests when parameterized only by the number of groups, yet becomes fixed-parameter tractable once neighborhood diversity is added.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"Theorem 4.2’s sufficiency gap is real: balanced matrix decomposition plus aggregate fairness does not imply per-class fairness.","rationale":"The reader correctly isolated the only material gap in the manuscript. Hardness (Theorems 3.1–3.2) and the k = 2 neighbourhood-diversity FPT (Theorem 4.1) are solid; the sole load-bearing positive claim that is incompletely supported is the general FPT result of Theorem 4.2. The concrete matrix counter-example demonstrates that the justification failure is not merely cosmetic: the algorithmic construction as written can output colour classes that violate the fairness threshold even when the ILP is feasible. Because the paper supplies no alternative construction or stronger decomposition lemma, the claim “FPT by nd + p” remains unproved. The appropriate editorial stance is therefore still CONDITIONAL, pending a correct repair of the matrix-decomposition step (or an entirely different FPT argument). No other concern rises to the same level of centrality.","tokens_in":13860,"tokens_out":685,"duration_ms":55476,"concrete_test":"Instantiate the matrix A = (3 1), set y_I = 2 and ℓ = 1, and enumerate all non-negative integer decompositions A = A_1 + A_2 whose row sums and column sums each differ by at most 1. Confirm that every such pair contains a summand whose two column sums differ by 2. This single check shows that Lemma 2.2 + constraint (10) do not entail per-class fairness, exactly as required by the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central positive claim that Fair Coloring is FPT by (nd, p) rests on the converse direction of Theorem 4.2. After solving ILP2, the authors form, for each type I, the matrix A with entries x_{i,j,I} and invoke Lemma 2.2 to write A = A_1 + // + A_{y_I} so that row sums and column sums of the summands differ by at most 1. They then assert (p. 11) that “because of Conditions (10) and (14) the coloring is ℓ-fair.” Condition (10) only bounds the aggregate column-difference vector by y_I·ℓ. Column-sum balance alone permits the individual differences d_s = (A_s)_j - (A_s)_{j'} to vary by as much as 2. Consequently a summand can realise difference ℓ+1 while another realises ℓ-1, violating the per-class Max-Min requirement. A minimal counter-example is the 1\times2 matrix A = (3 1), y_I = 2, ℓ = 1 (aggregate difference 2 ≤ 2ℓ). Every decomposition whose row and column sums differ by ≤ 1 produces a summand with column difference 2 > ℓ. The same phenomenon arises whenever a stable-set module is the sole member of I. The cited lemma therefore does not justify the step from aggregate to per-class fairness, leaving the FPT algorithm incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies the parameterized complexity of Fair Coloring: given a graph whose vertices are partitioned into p groups, decide whether there is a proper k-coloring in which every color class is ℓ-fair under the Max-Min criterion. The main negative results are that the problem is W[1]-hard parameterized by p alone, already for k=2, on forests of component depth 2 and on modular-width-2 graphs (Theorem 3.1); the hardness is obtained via a new intermediate result that Unary Vector Bin Packing is W[1]-hard in the dimension (Theorem 3.2). On the positive side the authors give an XP algorithm in p for k=2 (Theorem 3.3), an FPT algorithm in neighborhood diversity for k=2 via an integral difference-constraint LP (Theorem 4.1), and claim FPT in the combined parameter (nd,p) for arbitrary k by reducing to an ILP with 2^O(nd)nd p variables and invoking Lenstra (Theorem 4.2).","tokens_in":14202,"tokens_out":1546,"duration_ms":49185,"significance":"If correct, the results cleanly locate the tractability boundary of a natural fairness-constrained coloring problem: hardness already on forests and mw=2 when parameterized only by the number of groups, contrasted with FPT once neighborhood diversity (and, for general k, also p) is added. The by-product that unary multi-dimensional bin packing is W[1]-hard in the dimension is of independent interest and is obtained by a clean parameterized reduction from Grid Tiling. The k=2 FPT algorithm via integrality of a difference-constraint polytope is technically neat. These contributions would be a solid addition to the parameterized-complexity literature on fair graph problems, provided the general FPT claim is repaired.","major_comments":[{"comment":"Theorem 4.2, sufficiency direction (pp. 10–11): after solving ILP2 the authors form, for each type I, the matrix A=(x_{i,j,I}) and invoke Lemma 2.2 to write A=A_1+⋯+A_{y_I} so that row sums and column sums of the summands differ by at most 1. They then assert that “because of Conditions (10) and (14) the coloring is ℓ-fair.” Condition (10) only bounds the aggregate column-difference vector by y_I·ℓ. Column-sum balance alone permits the individual differences d_s=(A_s)_j-(A_s)_{j'} to vary; a summand can realise difference ℓ+1 while another realises ℓ-1. A minimal counter-example is the 1\times2 matrix A=(3 1), y_I=2, ℓ=1 (aggregate difference 2≤2ℓ): every balanced decomposition produces a summand with column difference 2>ℓ. The same phenomenon occurs whenever a stable-set module is the sole member of I. Consequently the cited lemma does not justify the step from aggregate to per-class fai","section":"Theorem 4.2, sufficiency (pp. 10-11)"},{"comment":"Theorem 4.2, ILP2 formulation: Condition (11) is written as a logical implication (“if y_I=0 then all x_{i,j,I}=0”). This is not a linear (or even polynomial) constraint. Without it, a feasible solution may place positive mass on a type with y_I=0; the subsequent matrix decomposition with b=y_I=0 is then undefined and the construction fails. For stable-set modules, constraint (8) only forces ∑_j x_{i,j,I}≥y_I, which is vacuous when y_I=0, so the implication is not implied by the remaining inequalities. The ILP must be rewritten with standard linear inequalities (e.g., big-M bounds x_{i,j,I}≤n_{i,j} y_I) before Lenstra’s algorithm can be applied.","section":"Theorem 4.2, ILP2 conditions (11)-(12)"}],"minor_comments":[{"comment":"Figure 1 caption and the yellow node “nd”: the text states that nd is FPT for k=2 and open in general, which matches Theorem 4.1, but the figure legend could explicitly mark the open status of nd for arbitrary k to avoid confusion with the green (nd+p) node.","section":"Figure 1"},{"comment":"Theorem 3.3: the DP table size is written (2|V|)^{p choose 2} while the running-time claim uses (2|V|)^{p^2}; the two expressions differ by a lower-order factor but should be aligned for precision.","section":"Theorem 3.3"},{"comment":"Proof of Theorem 3.1, sufficiency: the displayed equalities |C_1 ∩ V_j|=B+n-m and |C_2 ∩ V_j|=A+m are correct under the given definitions of |X_j| and |Y_j|, but a one-line reminder that A_j=∑_i w_{i,j} cancels would help the reader.","section":"Theorem 3.1"},{"comment":"Several minor typos: “dimen-sions” (p. 6), “depthtwo” (p. 8), “ify I=0” missing spaces (p. 10), and “O^*(2^{O(2^{nd} nd^2 p log p)})” whose exponent is slightly looser than the Lenstra bound with k=Θ(2^{nd} nd p).","section":null},{"comment":"Related-work paragraph on Fair Matching cites the authors’ own concurrent work [18]; a brief forward pointer clarifying the relationship (same fairness measure, different problem) would improve readability.","section":"Section 1, Related Work"}],"recommendation":"major_revision","confidential_remarks":"The hardness chain and the k=2 results appear solid and publishable on their own. The gap in Theorem 4.2 is genuine and load-bearing for the general FPT claim advertised in the abstract and Figure 1; I would not accept until that direction is repaired or the claim is withdrawn. The fix may be non-trivial (a different ILP or a genuinely fair decomposition routine) but seems within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The main takeaway is a clean W[1]-hardness for Fair Coloring by number of groups p, already at k=2, on forests of depth two and on modular-width-two graphs, plus a reusable byproduct that unary vector bin packing is W[1]-hard by dimension. Both reductions (Grid Tiling to packing, packing to coloring) look carefully written and correct. The XP algorithm for k=2 and the FPT algorithm by neighborhood diversity alone when k=2 (difference-constraint LP whose vertices are integral) are also convincing and use standard tools well.\n\nWhat is new is the problem itself under Max-Min group balance, the packing hardness, and the precise location of the FPT/W[1] border on these parameters. The citation pattern is appropriate; the self-citation is minor and the classical balanced-edge-coloring lemmas are properly invoked.\n\nThe soft spot is real and load-bearing for one positive claim. In Theorem 4.2 the authors solve an ILP that only enforces aggregate fairness per type, then invoke the balanced matrix decomposition (Lemma 2.2) and assert that each summand is automatically ℓ-fair. Column-sum balance alone does not force every individual difference vector inside [-ℓ,ℓ]; a summand can overshoot while another compensates. The 1×2 counter-example (A=(3 1), y_I=2, ℓ=1) already shows the step fails. So the claimed FPT by (nd,p) is incompletely justified. The rest of the paper does not depend on it.\n\nThis is for people who work on parameterized algorithms for coloring or fairness constraints on graphs. A referee who knows Lenstra and structural parameters will get value from the hardness side and the k=2 results immediately; the gap in 4.2 is fixable in revision (stronger ILP, different rounding, or an extra matching step) and does not sink the contribution. I would send it to peer review.","headline":"Solid hardness map and a clean k=2 FPT, but the general (nd,p) FPT has a real gap in the matrix-decomposition step.","tokens_in":14845,"tokens_out":506,"would_cite":true,"duration_ms":16547,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","05C15","68Q25"],"pacs":[],"model":"grok-4.5","headline":"Fair coloring is already W[1]-hard by the number of groups on forests and modular-width-two graphs, even for two colors, yet becomes FPT once neighborhood diversity is a parameter.","keywords":["fair coloring","parameterized complexity","neighborhood diversity","modular-width","vector bin packing","W[1]-hardness","FPT algorithms","equitable coloring"],"falsifier":"Produce a concrete matrix that satisfies the aggregate fairness constraint of the ILP yet every balanced decomposition into the prescribed number of summands has at least one summand whose group counts differ by more than the allowed threshold; or prove no such matrix exists.","tokens_in":14696,"feed_emoji":"⚖️","tokens_out":939,"duration_ms":32345,"temperature":0.7,"pith_summary":"The paper asks when a proper graph coloring can also keep given demographic groups nearly balanced inside every color class (the difference between any two groups at most a fixed threshold). It proves that measuring complexity only by the number of groups leaves the problem hard: already for two colors the question is W[1]-hard on forests whose components have depth two and on graphs of modular-width two. Hardness is obtained by first showing that unary multi-dimensional bin packing is W[1]-hard by dimension, then reducing that problem to fair two-coloring. On the positive side, when the input has small neighborhood diversity the two-color case is fixed-parameter tractable, and for any number of colors the combination of neighborhood diversity and number of groups is enough for an FPT algorithm via integer programming. A reader who cares about fair districting, load balancing or demographic balance on networks now knows exactly which structural parameters rescue the problem and which do not.","feed_headline":"Fair coloring stays hard on forests by group count","feed_subtitle":"Already W[1]-hard for two colors; neighborhood diversity restores fixed-parameter tractability","key_machinery":"A parameterized reduction from Grid Tiling through Unary Multi-dimensional Bin Packing that builds a simple forest (or modular-width-two graph) whose fair two-colorings encode exact capacity solutions; on the algorithmic side an integer linear program whose variables count color classes by valid type-sets of neighborhood-diversity modules, solved by Lenstra’s theorem after a balanced matrix decomposition.","core_discovery":"Fair Coloring is W[1]-hard parameterized by the number of groups p alone, already when only two colors are allowed, on forests of depth-two components and on modular-width-two graphs. The same problem is FPT parameterized by neighborhood diversity when the number of colors is two, and FPT parameterized by the pair (neighborhood diversity, p) for arbitrary numbers of colors. As a by-product, unary vector bin packing is W[1]-hard with respect to dimension.","pith_inferences":["Whether Fair Coloring is FPT by neighborhood diversity alone for more than two colors is the immediate open boundary left by the paper’s dichotomy.","The same type-set ILP encoding may apply directly to other Max-Min fairness problems already studied for matchings and shortest paths.","If the balancing step fails, an FPT algorithm can still be recovered by enumerating finer integer distributions inside each type rather than invoking the matrix lemma."],"forward_implications":["Unary multi-dimensional bin packing admits no FPT algorithm parameterized solely by dimension (unless FPT equals W[1]).","Fair two-coloring on forests is already intractable when only the number of demographic groups is treated as the parameter.","Neighborhood diversity alone restores fixed-parameter tractability for the two-color case without needing the number of groups.","For arbitrary numbers of colors the pair (neighborhood diversity, number of groups) yields an FPT algorithm via bounded-variable integer programming.","An XP algorithm exists for two colors parameterized only by the number of groups."],"fun_headline_variants":["Fair coloring W[1]-hard by groups alone on forests","Two-color fair coloring hard on forests via group count","Neighborhood diversity makes two-color fair coloring FPT","Fair coloring FPT by neighborhood diversity plus groups","Unary vector bin packing W[1]-hard by dimension"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The FPT proof for general numbers of colors assumes that a balanced splitting of an already-fair aggregate assignment automatically produces individually fair color classes, which the cited balancing lemma does not guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Fair coloring W[1]-hard by groups alone on forests","Two-color fair coloring hard on forests via group count","Neighborhood diversity makes two-color fair coloring FPT","Fair coloring FPT by neighborhood diversity plus groups","Unary vector bin packing W[1]-hard by dimension"]},"model":"grok-4.5","effort":"low","cost_usd":0.003233,"raw_usage":{"total_tokens":1126,"prompt_tokens":772,"num_sources_used":0,"completion_tokens":62,"cost_in_usd_ticks":32328000,"prompt_tokens_details":{"text_tokens":772,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":292,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":772,"tokens_out":62,"duration_ms":5342,"temperature":1.0,"reasoning_tokens":292,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T14:20:00.558281+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Produce a concrete matrix that satisfies the aggregate fairness constraint of the ILP yet every balanced decomposition into the prescribed number of summands has at least one summand whose group counts differ by more than the allowed threshold; or prove no such matrix exists.","supporting_citations":[],"review_version":1}