{"id":"1c16fb85-a443-4bed-b595-2b2686ba3688","arxiv_id":"2505.00412","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"On kP3-free graphs, the maximum weight list r-colorable induced subgraph problem is solvable in polynomial time for every fixed r and k, as are the distance-d versions for d at least 6.","lead":"For graphs that exclude k disjoint copies of a three-vertex path, the paper gives fast algorithms for finding the heaviest induced subgraph that can be colored with r colors from vertex-specific lists. This settles the computational complexity of this broad family of problems on such graphs and answers open questions about odd-cycle transversals and distance-coloring.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the amiable-family construction and the matching reduction appear sound, and the delicate containment inductions in Lemmas 8 and 7 are internally consistent.","rationale":"The reader identified the containment claims in Lemma 8 and Lemma 7 as the weakest assumption, and I agree that these are the most delicate parts of the proof. However, on close reading I found no actual flaw. In Lemma 8, the induction is carefully structured: the invariant that every member is P3-free is maintained by construction, and the containment proof splits correctly into the two exhaustive cases, each time passing to the anti-neighborhood of an induced P3 that is anticomplete to the recursive graph, so the (k-1)P3-free hypothesis is justified. In Lemma 9, the equivalence between feasible colorings and matchings is exact: a coloring gives at most one vertex per color and per connected component of each S_i, and a matching selects vertices from distinct components, which are pairwise at distance at least d, giving a valid (d,r)-coloring. The distance-d proof in Lemma 7 is more involved, especially the Gi-compatible notion in Claim (6), but the argument that every F-avoiding distance-d independent set is captured appears coherent: in each case where vi is added, the recursive call on N^{>=4}(vi) captures I\\{vi} because distance-d independence forces I\\{vi} to lie in N^{>=d}(vi), and the forbidden set in the recursive call excludes F as well as vertices at distance < d from vi. The d >= 6 condition is genuinely used and is not an artifact; the inequality 2(d-3) <= d-1 fails exactly for d <= 5, matching the acknowledged limitation. Since the central claim holds up under this scrutiny, the verdict should remain unchanged. The one caveat is that the paper is not machine-checked and the distance-d induction is complex enough that an independent implementation-based check on small graphs would be a prudent verification step.","tokens_in":20971,"tokens_out":33708,"duration_ms":333162,"concrete_test":"Implement Algorithm 1 (amiable family) and Algorithm 2 (distance-d amiable family) in a small exhaustive setting: enumerate all kP3-free graphs on up to n = 10 vertices for k = 2, 3 and, for Algorithm 2, set d = 6. For each graph, verify all three defining properties: (a) every output member induces a P3-free subgraph; (b) for Algorithm 2, the connected components of each member are pairwise at distance at least d in G; and (c) every (F-avoiding, when F is the recursive forbidden set) independent set / distance-d independent set is contained in at least one output member. A single graph where containment fails would pinpoint the exact inductive step in Claim (2) or Claim (6) that is broken; if all tests pass, the central containment guarantee is empirically corroborated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. I scrutinized the two pillars of the central claim. In Lemma 8, Claim (2) is the load-bearing part: every independent set must be contained in some member of the computed amiable family. The two-case analysis is exhaustive: if adding vi to S creates a P3, either some component of G[S] is partial to vi (yielding the P3 vi-u-w with u-w adjacent), or vi is complete to at least two components (yielding the P3 u-vi-w). In both cases the chosen P3 is anticomplete to the anti-neighborhood on which the recursive call is made, so the (k-1)P3-free argument is valid. The addition of {vi,w} or {vi} with the recursive set C correctly covers the independent set. Lemma 9's matching reduction is also sound: because each S_i induces a P3-free graph, its components are cliques, so a valid coloring places at most one vertex of each color in each component, exactly matching the auxiliary bipartite-graph construction. For the distance-d results, the proof of Lemma 7 is intricate, especially Claim (6) with the Gi-compatible induction, but the key inequalities hold: the d >= 6 restriction is forced by 2(d-3) <= d-1, and the F-avoiding invariant ensures recursive members lie in N^{>=d}(u), which is what makes the containment induction close. I found no concrete counterexample, missing case, or circular step. The self-acknowledged limitation for d < 6 is clearly scoped and does not affect Theorem 3.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Max-Weight List r-Colorable Induced Subgraph on kP3-free graphs. The main result, Theorem 3, states that for every fixed r≥1 and every k, this problem admits a polynomial-time algorithm on kP3-free graphs. The approach is to compute an amiable family of polynomial size (Lemma 8), meaning a family of P3-free induced subgraphs that jointly contain every independent set, and then reduce the problem to polynomially many maximum-weight bipartite matching instances (Lemma 9). The paper derives several consequences: a complete dichotomy for the problem on H-free graphs for r≥5 under P≠NP (Theorem 4), progress on Odd Cycle Transversal and a related open problem of Agrawal et al., and a short self-contained proof of the known polynomial-time solvability of List r-Coloring on kP3-free graphs. For distances d, the paper introduces distance-d amiable families and proves, for every fixed d≥6, polynomial-time algorithms for Max-Weight Distance-d Independent Set and List (d,r)-Coloring on kP3-free graphs (Theorems 5 and 6), with the d≥6 restriction explicitly forced by the proof in Lemma 7.","tokens_in":70,"tokens_out":8292,"duration_ms":662060,"significance":"If the results hold, this is a substantial contribution to the algorithmic theory of H-free graphs. Theorem 4 completely settles the complexity of a natural list-coloring variant for r≥5, and Theorem 3 answers and generalizes a question left open by Agrawal et al. for Odd Cycle Transversal. The paper also provides a much shorter and self-contained proof of the previously technical result of Chudnovsky, Hajebi, and Spirkl. A notable strength is that the paper is transparent about its scope: it explicitly notes that no proof for k>2 existed in Lozin's prior work and supplies a full proof, and it clearly states that the distance-d theorems apply only for d≥6, with d=4 left open in Question 11. The algorithmic reductions are clean, the size bounds and running-time recurrences are explicit, and the proofs of Lemmas 8, 9, and 7 are written in enough detail to be verifiable.","major_comments":[],"minor_comments":[{"comment":"The loops \"for every member S∈S do\" modify S inside the loop; please specify that the enumeration is over a snapshot of S taken at the start of the iteration, otherwise the pseudocode is formally ambiguous.","section":"Section 3, Algorithm 1"},{"comment":"The notation \"viuw\" for an induced P3 with middle vertex vi is defined, but in the later case analysis the two patterns \"viuw\" and \"uviw\" require the reader to track which vertex is the degree-2 vertex; a one-sentence reminder at the first use in the proof of Claim (2) would improve readability.","section":"Lemma 8 proof"},{"comment":"The forbidden set (F∩N^{≥4}(u))∪(N^{≥4}(u)∩N^{≤d-1}(u)) is central to Claims (5) and (6), but it is introduced without an intuitive explanation; a short comment saying that it encodes the vertices that are either forbidden outright or too close to u would help the reader follow the recursive call.","section":"Section 4, Algorithm 2"},{"comment":"The sentence \"the failure for d∈{3,5} is to be expected given the hardness results in Theorem 2\" should be qualified: Theorem 2 does not settle d=4, and the paper leaves d=4 open in Question 11; the current phrasing might suggest all d≤5 are resolved.","section":"Section 4, discussion before Lemma 7"},{"comment":"In the base cases for k=1, the text writes Λd_1(G)={V(G)\\F}, but the algorithm is defined as Λd_k(G,F); please use the two-argument notation consistently.","section":"Lemma 7 proof"},{"comment":"The proof says \"find a maximum-size induced subgraph H\" while Lemma 9 is stated for weights; since all weights can be taken to be 1, this is fine, but a one-line remark would remove any ambiguity.","section":"Theorem 6 proof"}],"recommendation":"accept","confidential_remarks":"This is a strong, self-contained paper. The proofs of the two amiable-family lemmas are lengthy but detailed, and the matching reduction is clean. The d≥6 restriction is transparently acknowledged and the d=4 open case is clearly identified. I see no need for further technical revision beyond the minor presentation points listed for the authors."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline: this paper does what it says. Theorem 3 gives a polynomial-time algorithm for Max-Weight List r-Colorable Induced Subgraph on kP3-free graphs, a genuine extension of the Chudnovsky–Hajebi–Spirkl List r-Coloring result, and the proof is self-contained, bypassing the heavy Hajebi–Li–Spirkl step. Theorem 4 completes the H-free dichotomy for r>=5. That is a real advance, not an incremental tweak.\n\nWhat is new and good: the amiable-family construction in Lemma 8 is re-proved from scratch because Lozin's note for k>2 lacked a proof; the induction for containment of independent sets is written in full detail. The reduction to weighted bipartite matching in Lemma 9 is clean and correct. The paper is also honest about its limits: it explicitly scopes out d<6 for the distance-d results, leaves d=4 open for distance-d independent set, and notes that the max-weight induced-subgraph version with distances measured inside the subgraph is not handled. The citation pattern is normal; prior work is credited clearly.\n\nSoft spots, in proportion: the distance-d section is the fragile part. Lemma 7 is long, and the proof of Claim (6) is intricate; the d>=6 restriction is forced by a specific inequality (2(d-3) <= d-1), and the argument would collapse for smaller d. That is not an error given the statement, but it means the distance-d theorems are narrower and less robust than the main result. I also would not call the running time practical: n^{O(rk)} is polynomial in the formal sense, but for moderate k and r it grows fast. That is not a correctness issue. I checked the load-bearing containment claims in Lemmas 8 and 7 as far as I could and found no gap, but the case analysis in Lemma 7 deserves careful scrutiny from a referee.\n\nWho this is for: researchers working on algorithmic dichotomies for H-free graphs. The paper deserves a serious referee, not a desk reject. My recommended outcome is acceptance, conditional on a careful check of Lemma 7.","headline":"A genuinely new polynomial-time algorithm for max-weight list r-colorable induced subgraphs on kP3-free graphs, with a self-contained proof and a completed dichotomy for r>=5; the distance-d part is narrower and more fragile but honestly scoped.","tokens_in":21840,"tokens_out":2878,"would_cite":true,"duration_ms":29462,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C15","05C69","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that Max-Weight List $r$-Colorable Induced Subgraph can be solved in polynomial time on $kP_3$-free graphs for every fixed $r$ and $k$, and extends this to distance-$d$ analogues for $d \\geq 6$.","keywords":["kP3-free graphs","Max-Weight List r-Colorable Induced Subgraph","Odd Cycle Transversal","amiable family","distance-d independent set","list coloring","H-free graphs","polynomial-time algorithm"],"falsifier":"A concrete check: enumerate all $kP_3$-free graphs on up to ten vertices, run the $\\Gamma_k$ or $\\Lambda^d_k$ construction, and verify that every maximal (distance-$d$) independent set lies in some family member; any violation refutes the containment claim. For the distance case, specifically search for a $2P_3$-free graph in which two cliques of a recursively built set are at distance exactly $d-1$ for some $d < 6$, which the inequality $2(d-3) \\leq d-1$ rules out.","tokens_in":20815,"feed_emoji":"🎨","tokens_out":18401,"duration_ms":149088,"temperature":0.7,"pith_summary":"This paper proves a broad tractability result: on graphs that contain no $k$ disjoint induced copies of the three-vertex path $P_3$, the problem of finding a maximum-weight induced subgraph that admits a list $r$-coloring is solvable in polynomial time, for every fixed $r$ and $k$. This single result specializes to maximum independent set ($r=1$), odd cycle transversal ($r=2$), and list $r$-coloring, so all of these problems become polynomial-time solvable on $kP_3$-free graphs. The proof shows that such graphs admit a polynomial-size 'amiable family' of simple, clique-union vertex sets that cover every maximal independent set, and then reduces the search to a polynomial number of maximum-weight bipartite matching problems. A distance-$d$ variant of the same machinery yields polynomial-time algorithms for Max-Weight Distance-$d$ Independent Set and List $(d,r)$-Coloring for every $d \\geq 6$.","feed_headline":"Maximum list-colorable subgraph is polynomial on kP3-free graphs","feed_subtitle":"One method gives exact algorithms for independent set, odd cycle transversal, and list coloring on this graph family.","key_machinery":"The load-bearing object is the amiable family and its distance-$d$ generalization. An amiable family is a polynomial-size collection of vertex subsets of a graph $G$ such that each member induces a $P_3$-free subgraph (every connected component is a clique) and every maximal independent set is contained in some member; a distance-$d$ amiable family adds the requirements that the components of each member are pairwise at distance at least $d$ in $G$ and that every maximal distance-$d$ independent set is covered. The paper proves these families exist and can be computed in polynomial time for $kP_3$-free graphs (Lemma 8, and Lemma 7 for $d \\geq 6$) via an algorithm that enumerates induced $P_3$'s and recursively builds families on anti-neighborhoods, which are $(k-1)P_3$-free. The second supporting mechanism is Lemma 9, which converts an $r$-tuple of family members into an auxiliary weighted bipartite graph whose left side is the vertices of the union, whose right side is the connected components of the induced $P_3$-free subgraphs, and whose edges carry vertex weights; a maximum-weight matching then selects the best color assignment subject to lists and to each color class lying inside its designated family member.","core_discovery":"The central discovery is that Max-Weight List $r$-Colorable Induced Subgraph is polynomial-time solvable on $kP_3$-free graphs for every fixed $r \\geq 1$ and $k \\in \\mathbb{N}$, a statement the paper proves as Theorem 3 by combining two structural ingredients. First, every $kP_3$-free graph admits an amiable family: a collection of $|V(G)|^{O(k)}$ vertex subsets, each inducing a $P_3$-free subgraph (a disjoint union of cliques), such that every maximal independent set is contained in one of them; the recursive construction enumerates induced $P_3$'s and recurses on their anti-neighborhoods, which are $(k-1)P_3$-free. Second, for each $r$-tuple of family members, the problem of choosing a maximum-weight induced subgraph with a list-respecting coloring whose color classes lie in those members reduces to a maximum-weight bipartite matching problem, solved by the Hungarian method. The paper obtains distance-$d$ analogues by strengthening the family definition to require that the components of each member be pairwise at distance at least $d$ and that every maximal distance-$d$ independent set be covered; this works for every $d \\geq 6$, with the threshold forced by an inequality in the containment proof.","pith_inferences":["The matching-based reduction indicates that on $kP_3$-free graphs, list-colorable induced subgraph problems have a hidden combinatorial structure independent of standard width parameters, which are known to be unbounded even for $2P_3$-free graphs; the same template might apply to other hereditary properties closed under replacing components.","The $d \\geq 6$ threshold is an artifact of the inequality $2(d-3) \\leq d-1$ in the containment proof, so the genuinely open case $d=4$ could be settled by seeking a polynomial-size distance-$4$ amiable family; the authors suspect no such family exists.","A concrete testable extension is to verify the containment property computationally: enumerate all small $kP_3$-free graphs and check that every maximal (distance-$d$) independent set lies inside the constructed family, which would directly test the paper's central structural claim.","The amiable-family recursion could in principle be ported to other forbidden-induced-subgraph classes in which deleting the neighbourhood of a small obstruction reduces the number of forbidden copies, offering a route to new dichotomies for induced subgraph problems."],"forward_implications":["Odd Cycle Transversal is polynomial-time solvable on $kP_3$-free graphs for every $k$, resolving the open problem that had been posed for $(P_3+P_2)$-free graphs.","For every fixed $r \\geq 5$, assuming $\\mathsf{P} \\neq \\mathsf{NP}$, Max-Weight List $r$-Colorable Induced Subgraph is polynomial-time solvable on $H$-free graphs if and only if $H$ is an induced subgraph of $kP_3$ or of $P_5+kP_1$, completing the dichotomy.","List $r$-Coloring on $kP_3$-free graphs is polynomial-time solvable for all fixed $r$ and $k$, with a proof that is shorter and self-contained compared with the earlier proof of this result.","Max-Weight Distance-$d$ Independent Set and List $(d,r)$-Coloring are polynomial-time solvable on $kP_3$-free graphs for every fixed $d \\geq 6$, and the only remaining open case for the independent set problem is $d=4$.","Toward the Odd Cycle Transversal dichotomy on $H$-free graphs, the sole remaining open case is $H = k_4P_4 + k_3P_3 + k_2P_2 + k_1P_1$ with $k_4 \\geq 1$ and $k_4+k_3 \\geq 2$; the specific graph $(P_4+P_3)$ is singled out as Question 10."],"supporting_citations":[{"why":"Points out that the amiable family property holds for every k≥2, providing the recursive template that Lemma 8 formalizes.","marker":"[20]"},{"why":"Introduces amiable families and proves their existence for k=2; supplies the central notion and the base case for the construction.","marker":"[21]"},{"why":"The bipartite-matching reduction adapts an idea from the prior proof that List r-Coloring is polynomial on kP3-free graphs; that result is generalized here.","marker":"[7]"},{"why":"Provides the maximum-weight bipartite matching algorithm (Hungarian method) that solves each auxiliary problem in Lemma 9.","marker":"[25]"},{"why":"Poses the open problem on (P3+P2)-free graphs that the main theorem answers, and gives the P5-free algorithm used in the broader dichotomy.","marker":"[1]"},{"why":"Establishes tractability on P5+kP1-free graphs, which pairs with the main theorem to give the complete r≥5 dichotomy on H-free graphs.","marker":"[15]"},{"why":"Shows NP-hardness of Distance-d Independent Set for d=3 and d=5 on kP3-free graphs, fixing the limits of the distance-d results and leaving only d=4 open.","marker":"[12]"}],"fun_headline_variants":["Max-weight list r-coloring solved on kP3-free graphs","One method for independent set, odd cycle transversal & list coloring on kP3-free graphs","Distance-d independent set and list coloring solved on kP3-free graphs","Unified polynomial algorithm for three classic problems on kP3-free graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm is correct only if every (distance-$d$) independent set is contained in one of the polynomial many $P_3$-free containers that the recursive construction produces, and this containment is exactly what the inductive Claims (2) and (6) assert; if that proof failed for any $kP_3$-free input, an optimal color class could be missed.","fun_headline_variants_meta":{"raw":{"variants":["Max-weight list r-coloring solved on kP3-free graphs","One method for independent set, odd cycle transversal & list coloring on kP3-free graphs","Distance-d independent set and list coloring solved on kP3-free graphs","Unified polynomial algorithm for three classic problems on kP3-free graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00183,"raw_usage":{"total_tokens":7324,"prompt_tokens":1200,"completion_tokens":6124,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":816,"completion_tokens_details":{"reasoning_tokens":6042}},"tokens_in":816,"tokens_out":6124,"duration_ms":43281,"temperature":1.0,"reasoning_tokens":6042,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:42:56.369626+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check: enumerate all $kP_3$-free graphs on up to ten vertices, run the $\\Gamma_k$ or $\\Lambda^d_k$ construction, and verify that every maximal (distance-$d$) independent set lies in some family member; any violation refutes the containment claim. For the distance case, specifically search for a $2P_3$-free graph in which two cliques of a recursively built set are at distance exactly $d-1$ for some $d < 6$, which the inequality $2(d-3) \\leq d-1$ rules out.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Points out that the amiable family property holds for every k≥2, providing the recursive template that Lemma 8 formalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces amiable families and proves their existence for k=2; supplies the central notion and the base case for the construction."},{"cited_title":"Chudnovsky, S","cited_arxiv_id":null,"evidence_quote":"The bipartite-matching reduction adapts an idea from the prior proof that List r-Coloring is polynomial on kP3-free graphs; that result is generalized here."},{"cited_title":"Schrijver.Combinatorial Optimization - Polyhedra and Efficiency, volume 24 ofAlgorithms and Combinatorics","cited_arxiv_id":null,"evidence_quote":"Provides the maximum-weight bipartite matching algorithm (Hungarian method) that solves each auxiliary problem in Lemma 9."},{"cited_title":"Agrawal, P","cited_arxiv_id":null,"evidence_quote":"Poses the open problem on (P3+P2)-free graphs that the main theorem answers, and gives the P5-free algorithm used in the broader dichotomy."},{"cited_title":"Henderson, E","cited_arxiv_id":null,"evidence_quote":"Establishes tractability on P5+kP1-free graphs, which pairs with the main theorem to give the complete r≥5 dichotomy on H-free graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows NP-hardness of Distance-d Independent Set for d=3 and d=5 on kP3-free graphs, fixing the limits of the distance-d results and leaving only d=4 open."}],"review_version":1}