{"id":"56e6edb2-72c2-4396-8180-49d32fe0a263","arxiv_id":"2411.14533","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"First IP formulations and a local-search enhanced BRKGA for the connected Grundy coloring problem, with experiments showing the representatives formulation beats a standard one and the enhanced metaheuristic modestly improves on a baseline.","lead":"This paper presents the first integer programming formulations and a genetic algorithm for the connected Grundy coloring problem, where the goal is to maximize colors used by a first-fit greedy coloring under a connected vertex ordering. It gives researchers exact and heuristic tools for a known NP-hard graph parameter that bounds the quality of connected greedy coloring heuristics.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Benchmark modification in Section 5.1.1 can change the connected Grundy number (acknowledged counterexample), so reported BRKGA performance on modified instances may not reflect original graphs; this weakens the empirical support for the central claim.","rationale":"The reader's weakest assumption identifies the Section 5.1.1 benchmark modification as the load-bearing concern. This is the most concrete and acknowledged soft spot: the paper's computational experiments, which are the primary evidence for the BRKGA's effectiveness and for the comparison between formulations, are run on graphs that have been artificially connected by adding paths. The authors themselves provide a counterexample showing the modification can increase the connected Grundy number, so the relationship between the modified instances and the original disconnected graphs is not controlled. The central claim that the BRKGA finds high-quality solutions for large instances is therefore only validated on these altered instances. The IP formulations, if correct, remain a valid contribution, and the relative comparison between BRKGA variants on the same modified instances is internally sound. However, the external validity of the benchmark results is compromised. The proposed concrete test would settle whether the modification actually changes the objective values in the benchmark set. A secondary issue, the apparent typo in Algorithm 1 line 10 (enqueues v instead of the neighbor u), is easily corrected and does not change the intended method. The reader's CONDITIONAL verdict is appropriate; no adjustment is needed.","tokens_in":36991,"tokens_out":27852,"duration_ms":249342,"concrete_test":"Select all disconnected benchmark instances used in Section 5. For each, compute the connected Grundy number of the modified graph and of each original connected component, using the proposed IP formulations for small instances (n ≤ 30) and the BRKGA with multiple seeds for larger instances. Compare Γc(G_mod) with max_i Γc(component_i). Report the number and magnitude of discrepancies. If any non-negligible fraction differs beyond the known isolated-vertex counterexample, the modification changes the instances and the reported results do not transfer to the original graphs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central empirical claim is that the proposed BRKGA finds high-quality solutions for instances up to 500 vertices. Section 5.1.1 modifies disconnected benchmark graphs by adding a path between highest-degree vertices of each connected component, and the authors assume that for most cases the connected Grundy number of the modified graph equals the maximum over components. They explicitly concede a counterexample with two isolated vertices where the equality fails (max + 1 = 2). Because the benchmark set is the primary evidence for the BRKGA's effectiveness, and because the modification is known to alter the objective in at least one case, the reported solution values and comparisons on those instances are not established to be representative of the original graphs. The relative performance of BRKGA+R+LS versus BRKGA-B is internally valid, but the absolute quality and generalizability of the results to the original instance set are not. This affects the strength of the claim that the BRKGA is a high-quality solver for the connected Grundy coloring problem on general graphs, as the test instances themselves have been artificially altered without a proven relationship to the intended graphs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the connected Grundy coloring problem, in which one seeks a proper vertex coloring obtainable by a first-fit heuristic on a connected vertex sequence, maximizing the number of colors. The authors propose two integer programming formulations (a standard partition-based model and a representatives-based model), and a biased random-key genetic algorithm (BRKGA) enhanced with a reset mechanism and a local search procedure using a newly defined neighborhood. They provide a theoretical analysis of the local search neighborhood, present computational experiments on instances with up to 30 vertices for the exact methods and up to 500 vertices for the heuristics, and extend the approach to the (non-connected) Grundy coloring problem.","tokens_in":37173,"tokens_out":20632,"duration_ms":187391,"significance":"If the results are correct, this is the first systematic optimization study of the connected Grundy coloring problem, a natural NP-hard variant of Grundy coloring. The two IP formulations are non-trivial, and the neighborhood analysis is a useful theoretical contribution. The paper also shows that the proposed BRKGA can be adapted to the Grundy coloring problem and may improve known results. The computational study is extensive, with 50 runs per instance and comparisons across several graph classes. However, the empirical support for the central claim is weakened by an unproven modification of disconnected benchmark instances, and the correctness of the formulations is asserted rather than formally proven. The local-search theory also contains a proof gap that should be addressed.","major_comments":[{"comment":"The procedure that connects disconnected benchmark instances by adding a path between the highest-degree vertices of each component can change the connected Grundy number of the resulting graph; the authors themselves concede the counterexample of two isolated vertices, where the optimum increases from 1 to 2. The paper neither reports how many of the 282 tested instances were disconnected nor provides any empirical or theoretical validation that the equality Γc(G) = max_i Γc(G_i) holds for the instances actually used in Tables 7-10. Since the BRKGA objective values are computed on these modified graphs, the reported solution qualities cannot be directly attributed to the original benchmark graphs. This weakens the central claim that the proposed BRKGA finds high-quality solutions on the original instance set. The authors should restrict the benchmark to connected graphs, or prove invariance conditions for their modification, or report per-instance evidence that the modification does not alter the optimum (for example, using the combinatorial upper bounds on the original components).","section":"5.1.1"},{"comment":"The paper does not provide a formal proof that formulations (1)-(9) and (10)-(20) are exact models of the connected Grundy coloring problem. In particular, the representatives-based formulation contains subtle constraints such as (12), (14), and (15) whose interpretation is not fully formalized, and it is not shown that the integer programming optimum equals Γc(G) for every connected graph G. A correctness proof, or at least a detailed bijection between feasible IP solutions and connected Grundy colorings, is essential because the optimality claims in Section 5.3 and the use of these formulations as exact benchmarks depend on this equivalence.","section":"2"},{"comment":"The proof of Proposition 4 is not rigorous as written. In the case p_S'(v) < p_S(v), the interval [1, p_S'(v)] in S' contains the vertex v, whereas in S it contains the vertex that occupied that position before the move, so the statement that the two solutions have the same vertices colored the same way in that interval is false. The conclusion that all vertices keep their colors may still be true, but the proof must be corrected; as written, it does not rule out the possibility that a vertex adjacent to v changes color because v now appears earlier with the same color. Since Proposition 4 is used to justify pruning in the local search (Section 4.3), a correct proof is needed.","section":"4.2"}],"minor_comments":[{"comment":"In Algorithm 1, line 10, the pseudocode enqueues the variable v (the vertex just colored) instead of u (the neighbor being examined); it should read Enqueue(Q, u).","section":"3.2"},{"comment":"The first paragraph of Section 4 contains a typo: 'in it's i-th position' should be 'in its i-th position'. The abstract also has 'AGrundy' missing a space.","section":"4"},{"comment":"The caption of Figure 11(a) refers to 'BRKGA+R+LS and BRKGA-B', but the comparison is with BRKGA-G (the Grundy coloring BRKGA from Silva et al.); the caption should be corrected.","section":"6.1"},{"comment":"The parameter tuning is performed on a subset of 28 instances; the paper should clarify whether these instances are also included in the final test set, since in-sample tuning would make the reported differences more favorable to the tuned variant.","section":"5.2"},{"comment":"Tables 7-10 report averages over 50 runs but no dispersion measure; adding standard deviations or confidence intervals would help the reader judge the variability of the reported improvements.","section":"5.4"}],"recommendation":"major_revision","confidential_remarks":"The benchmark modification issue in Section 5.1.1 is the most serious concern. If the authors cannot demonstrate that the connection procedure preserves the connected Grundy number on the tested instances, the computational evidence should be reframed as being about the modified instances only, which would considerably weaken the paper's contribution. The missing correctness proof for the IP formulations is also a substantive gap for a formulation paper. The local-search theory is otherwise interesting, and the experimental design is extensive; these strengths make the paper worth revising."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the first optimization-based treatment of the connected Grundy coloring problem, with two IP formulations and a BRKGA plus local search. It is a competent, honest piece of work. The formulations appear correct, the neighborhood analysis is a genuine addition, and the experiments are extensive. The main caveat, which the stress-test flagged, is real but manageable: the authors modify disconnected DIMACS instances by wiring components together with paths, and they concede a case where this changes the objective. That weakens the absolute quality claims on those instances, but the relative BRKGA comparison is unaffected, and the transparency about the failure case earns trust. The paper's other soft spots are minor: no code or data, no variance over the 50 runs, and a few DIMACS instances where the enhanced method loses to the baseline. The improvements are small—around one percent on random graphs, less elsewhere—so the evidence for the local search is suggestive rather than decisive. None of this undermines the main contribution. The IPs are new and the BRKGA is a solid engineering contribution. I would send this to a serious referee. Have the authors provide code and instance data, and ask them to report per-instance variance and to be more explicit about how many benchmark instances were disconnected and how the path-connection step changed the objective on those.","headline":"A solid, honest first computational treatment of connected Grundy coloring: first IP formulations and a useful BRKGA, with a benchmark-modification caveat that is real but not disqualifying.","tokens_in":37724,"tokens_out":2250,"would_cite":true,"duration_ms":24056,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","90C27","90C10","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces the first exact and heuristic optimization methods for the connected Grundy coloring problem, with a representative-based integer program that dominates the standard one and a local-search genetic algorithm that…","keywords":["connected Grundy coloring","Grundy number","first-fit coloring","integer programming","formulation by representatives","biased random-key genetic algorithm","local search","graph coloring"],"falsifier":"Take a small disconnected graph with three components, compute the connected Grundy number of the path-connected version produced by the Section 5.1.1 procedure, and compare it with the maximum connected Grundy number of the components; the first non-trivial case where the two differ shows that the benchmark modification changes the problem being solved.","tokens_in":36761,"feed_emoji":"🎨","tokens_out":9659,"duration_ms":78317,"temperature":0.7,"pith_summary":"The paper's goal is to give the first general optimization methods for the connected Grundy coloring problem, in which vertices are colored by a first-fit heuristic over a connected ordering and one wants the maximum number of colors, the connected Grundy number $\\Gamma_c(G)$. It proposes two integer programming formulations, a standard partition model and a symmetry-breaking \"representatives\" model, plus a biased random-key genetic algorithm enhanced with reset and local search. The computational evidence is that the representative formulation wins on small graphs, while the genetic algorithm delivers high-quality colorings on instances up to 500 vertices in five-minute runs. The paper also shows the same local-search framework improves existing heuristic results for the ordinary Grundy coloring problem.","feed_headline":"First exact and heuristic methods for connected Grundy coloring","feed_subtitle":"A representative-based IP wins on small graphs; the genetic algorithm reaches 500-vertex instances.","key_machinery":"The central object is a connected Grundy coloring: a proper vertex coloring obtainable by the first-fit rule on a vertex sequence in which every new vertex is adjacent to an earlier one. The argument runs through two IP models; the standard model uses variables $z_{vkt}$ deciding that vertex $v$ receives color $k$ at time $t$, with constraints enforcing properness, the Grundy property, and connectivity, while the representatives model uses variables $Z_{vut}$ and $y_{vu}$ so each vertex is represented by an earlier vertex and representatives are ordered, breaking symmetry. The heuristic machinery is a BRKGA whose random-key vector encodes vertex priorities, a decoder that produces a connected sequence with a priority queue in $O(|V|\\log|V| + |E|)$, and a local search that moves a single vertex to a position next to one of its neighbors; Propositions 7 and 8 give $O(1)$ and $O(|N(v)|)$ connectivity checks that make the neighborhood search practical.","core_discovery":"On its own terms, the paper establishes that connected Grundy coloring can be attacked directly: the first claim is that two integer programming formulations correctly encode first-fit colorings over connected vertex sequences, with the representatives model breaking symmetries, and that the representatives model is computationally superior on the tested benchmark. The second claim is that a biased random-key genetic algorithm whose decoder builds a connected sequence by repeatedly extracting the highest-priority reachable vertex, with a local search that moves one vertex next to a neighbor and a reset mechanism, reliably produces high-quality colorings for instances up to 500 vertices. The paper further reports that the approach, with connectivity checks removed, improves the Grundy coloring problem, finding new best-known solutions on 36 of 362 benchmark instances.","pith_inferences":["The benchmark-connection procedure in Section 5.1.1 is the paper's least controlled step: if adding a path between high-degree vertices changes the connected Grundy number for graphs beyond the two-isolated-vertices example, the large-instance results describe the modified graphs rather than the original disconnected benchmarks.","The representatives model's edge on dense graphs suggests that symmetry is the principal obstacle for exact connected Grundy coloring, so symmetry-breaking cuts or orbitopal fixing could plausibly extend exact solvability beyond 30 vertices.","The move-one-vertex-next-to-a-neighbor neighborhood is a generic operation for first-fit-based coloring problems and could be tested on connected greedy edge colorings or other constrained first-fit settings.","The paper does not explore incremental decoding, but the decoder's priority-queue structure suggests the BRKGA could be adapted to streaming graphs where vertices arrive over time."],"forward_implications":["Exact computation of the connected Grundy number is feasible for small graphs: the two formulations together proved optimality on 132 of 240 instances with up to 30 vertices, and another 46 were certified optimal by matching known upper bounds.","The symmetry-breaking representatives formulation is the stronger exact tool, especially on dense instances, and is the better starting point for any future exact method.","The reset-and-local-search BRKGA recipe transfers to the ordinary Grundy coloring problem, where it produced new best-known solutions on 36 of 362 instances.","Large graphs of up to 500 vertices can receive good connected Grundy colorings within a 300-second budget, making the heuristic usable where the IPs run out of memory.","Because $\\Gamma_c(G) \\le \\Gamma(G)$, any connected coloring that reaches a known Grundy upper bound is automatically optimal; this certificate was used throughout the small-instance experiments."],"supporting_citations":[{"why":"Introduces connected greedy colorings and proves computing the connected Grundy number is NP-hard even on chordal graphs, establishing the problem this paper solves.","marker":"Benevides et al. (2014)"},{"why":"Shows deciding whether a connected Grundy coloring with 7 colors exists is NP-complete and gives the polynomial-time cases for small k, framing the problem's complexity.","marker":"Bonnet et al. (2018)"},{"why":"Provides the IP formulations, BRKGA, and benchmark set for the Grundy coloring problem that this work extends to the connected setting and compares against.","marker":"Silva et al., 2024"},{"why":"Defines the biased random-key genetic algorithm framework whose elite, mutant, and crossover mechanics the paper adapts.","marker":"Gonçalves and Resende (2011)"},{"why":"Source of the formulation-by-representatives idea used to break symmetries in the second IP model.","marker":"Corrêa et al. (2004)"},{"why":"Gives the $\\Delta_2(G)+1$ upper bound used to restrict the color set in both formulations.","marker":"Zaker (2008)"},{"why":"Defines the stair-factor upper bound used alongside the other bounds to limit the available colors.","marker":"Shi et al. (2005)"},{"why":"Supplies the DIMACS benchmark instances used for the large-scale experiments.","marker":"Trick et al. (2015)"},{"why":"Provides the DSatur greedy heuristic used as one warm-start solution for the IP formulations.","marker":"Brélaz (1979)"}],"fun_headline_variants":["Connected Grundy gets its first exact and heuristic methods","Genetic algorithm scales connected Grundy coloring to 500 vertices","Representative-based IP wins on small, GA on large connected Grundy","Representative IP wins over standard for connected Grundy","Biased random-key GA with local search for connected Grundy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that adding a path between the highest-degree vertices of disconnected components leaves the connected Grundy number unchanged in the typical case; the paper itself gives a graph with two isolated vertices where this fails, so the modified benchmark results may not transfer to the original disconnected graphs.","fun_headline_variants_meta":{"raw":{"variants":["Connected Grundy gets its first exact and heuristic methods","Genetic algorithm scales connected Grundy coloring to 500 vertices","Representative-based IP wins on small, GA on large connected Grundy","Representative IP wins over standard for connected Grundy","Biased random-key GA with local search for connected Grundy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00142,"raw_usage":{"total_tokens":5740,"prompt_tokens":958,"completion_tokens":4782,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":4699}},"tokens_in":574,"tokens_out":4782,"duration_ms":36354,"temperature":1.0,"reasoning_tokens":4699,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:12:43.505113+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small disconnected graph with three components, compute the connected Grundy number of the path-connected version produced by the Section 5.1.1 procedure, and compare it with the maximum connected Grundy number of the components; the first non-trivial case where the two differ shows that the benchmark modification changes the problem being solved.","supporting_citations":[],"review_version":1}