{"id":"96472eb3-e354-479f-9ad2-09f01c7da24e","arxiv_id":"1908.00978","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors claim a polynomial-time algorithm for Dominating Induced Matching on P9-free graphs, generalizing earlier results, but a central observation in the proof is flawed.","lead":"This paper presents a polynomial-time algorithm for deciding whether a P9-free graph has a dominating induced matching, a special edge set that intersects every edge exactly once. The result extends previous work on P7- and P8-free graphs, but a key structural claim in the proof appears false, leaving the algorithm's correctness in doubt.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Observation 4 is false, but the decisive gap is Lemma 3's unproved assertion that Case 2.2 occurs only once; that assertion is what makes Step (B.2) polynomial.","rationale":"The reader is right that Observation 4 is false: its proof does not derive a contradiction from dist(w,y) < dist(v,y), and the triangle-with-tails graph is a counterexample. But the reader's example does not show the algorithm fails, because the algorithm may choose w as the central vertex; every edge incident with w is in an induced P3. So I would not base the rejection solely on Observation 4. The central claim requires a polynomial check in Lemma 3, and the last paragraph of Lemma 3 contains an unproved uniqueness assertion: after Claims 7-11, it says a possible coloring of T3 can be added and that Case 2.2 appears only once, with no argument tying a second occurrence to an induced P9. This is the step that bounds the branching of Step (B.2); without it, the proof does not establish polynomial time even if the structural picture is correct. The verdict should therefore remain REJECT, though the justification should rest on the Lemma 3 gap rather than on the falsity of Observation 4 alone.","tokens_in":20918,"tokens_out":24037,"duration_ms":275008,"concrete_test":"Formalize the omitted step in the final paragraph of Lemma 3: prove that any two occurrences of Case 2.2 in the same component K force an induced P9 in a graph that is P9-, (K4,diamond,butterfly)-free and satisfies (A1)-(A6), or else construct an explicit graph with at most 30 vertices satisfying those assumptions in which two such occurrences coexist. In the latter case, run the proposed coloring propagation on that graph and check whether the number of feasible xy-colorings remains bounded by a constant; if it grows, Lemma 3 is false and the polynomial-time bound collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Observation 4 is indeed false: in the triangle with two length-2 tails attached at w, u and v are central and uv is in no induced P3, while the unique d.i.m. contains uv. However, this example does not by itself refute the algorithm, because w is also central and every edge incident with w is in an induced P3; Step (A) can select w, and the recursive Step (C) then solves the remaining components. The load-bearing problem is in Lemma 3, Section 3, the case N4 = empty set. After Claims 7-11, the proof states: 'In general, if t2 does not completely color T3 then we can add a possible coloring of T3 which leads to a complete coloring of every neighbor Ti of T3. Since G is P9-free, Case 2.2 appears only once in component K.' No proof is given that such an added coloring is compatible with colors already forced, and no proof is given that a second occurrence of Case 2.2 forces an induced P9. If Case 2.2 can occur more than once, the search over feasible xy-colorings is not shown to be polynomial; this is exactly the part of Step (B.2) on which Theorem 3 depends. Thus the polynomial-time claim is unsupported as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to solve the Dominating Induced Matching (DIM) problem in polynomial time for P9-free graphs, extending the previously known P7-free linear-time and P8-free polynomial-time results. The approach follows the established framework for DIM: for a candidate matching edge xy contained in an induced P3, it partitions the graph into distance levels Ni(xy), applies a series of reduction rules (Vertex Reduction, Edge Reduction, assumptions (A1)-(A6), forcing rules (R1)-(R4)), and then attempts to complete a feasible black-white coloring. The main technical work is in Lemma 3, which claims that in the case N4 = empty set, each component of G[S2 ∪ N3] can be colored in polynomial time, and in Section 4, which extends the argument to N4 nonempty using a structural analysis of components in G[N4]. The final theorem (Theorem 3) asserts polynomial-time solvability of DIM on P9-free graphs.","tokens_in":21170,"tokens_out":18352,"duration_ms":190541,"significance":"If the main theorem is correct, it is a natural and meaningful advance in the study of dominating induced matchings in hereditary graph classes, supporting the conjecture that DIM is polynomial for Si,j,k-free graphs. The paper builds systematically on the authors' earlier work on P7- and P8-free graphs and does not merely reduce the P9 case to those results; the P9 arguments are new. The case analysis is extensive and several claims are carefully structured around explicit forbidden P9 configurations. No machine-checked proofs or code are supplied, so the contribution rests entirely on the correctness of the structural proof. Unfortunately, two load-bearing gaps prevent me from verifying the polynomial-time claim: Observation 4 is false as stated, and Lemma 3 contains an unproved assertion that is essential for the polynomial bound.","major_comments":[{"comment":"Observation 4 is false. Consider the P9-free graph consisting of a triangle (u,v,w) with two length-2 tails w-a-a' and w-b-b'. Vertices u and v are central, but the edge uv is contained in no induced P3, while the unique d.i.m. of this graph is {uv, aa', bb'}. The proof's assertion that dist(w,y) < dist(v,y) contradicts centrality is a non sequitur: a central vertex is defined by an absolute eccentricity bound, not by being closer to every vertex than v. Since Algorithm Step (A) requires a central vertex x such that every incident edge xy is contained in a P3, and the only justification for the existence of such an x is Observation 4, the preprocessing step is not justified as written. The example itself has another central vertex, w, with the required property, so a weaker existence statement may be true, but it is neither stated nor proved.","section":"Section 2.3, Observation 4; Algorithm Step (A)"},{"comment":"The proof of Lemma 3 concludes: 'Since G is P9-free, Case 2.2 appears only once in component K.' This is load-bearing with no proof. Step (B.2) of the algorithm needs the search over feasible xy-colorings to be polynomial; if Case 2.2 can occur in more than one Ti, the procedure would need to branch again, and the number of colorings is no longer bounded by the initial |T1| choices. Claims 7-11 handle a single unfinished T3 under the implicit assumption that all other neighbor sets are already colored; they do not rule out a second occurrence of Case 2.2 after T3 has been colored. The preceding sentence, 'we can add a possible coloring of T3 which leads to a complete coloring of every neighbor Ti of T3', also asserts compatibility with already forced colors without proof. A complete proof of the uniqueness of Case 2.2, or an alternative polynomial enumeration, is required for the polynomial-time claim.","section":"Section 3, Lemma 3, final paragraph"},{"comment":"Section 4's argument for the case N4 nonempty depends repeatedly on the polynomial-time coloring of components of G[S2 ∪ N3] that is supposed to be established by Lemma 3. For example, the text after Claim 18 states that 'for every Qi, it can be independently checked in polynomial time whether Qi has a feasible coloring or a contradiction.' If Lemma 3 is not repaired, the N4 nonempty case is unsupported as well. The paper should state explicitly where Lemma 3 is invoked and verify that after fixing a feasible coloring of the N4-component D, the remaining graph still satisfies the assumptions (A1)-(A6) and the reduction rules used in Lemma 3.","section":"Section 4, general structure"}],"minor_comments":[{"comment":"The phrase 'a central vertex in G has shortest distance to every other vertex in G' is ambiguous; Theorem 2 only guarantees the existence of a vertex with dist(v,w) <= floor(t/2) for all w. Please rephrase to avoid suggesting that v is a distance-minimizer among all vertices.","section":"Section 2.3, after Theorem 2"},{"comment":"The sentence 'w has more neighbors than v in G since G itself is no C3' is irrelevant to the claimed distance inequality and should be removed or replaced by a precise argument.","section":"Section 2.3, proof of Observation 4"},{"comment":"The proof says 'Let P be any induced path in G between u1 and u3 through N1 ∪ {x,y}'; it is not obvious that such an induced path with the required properties exists, and the subsequent construction of a P9 depends on it. Please provide a short justification or a more precise definition of P.","section":"Section 3, Claim 2"},{"comment":"The statement 'If there is a P5 (t,a,b,c,d) with endpoint t and four vertices a,b,c,d in N4 (such that only one of them, say a contacts t)' should specify whether the P5 is induced and what 'contacts' means; otherwise the claimed conclusion that t is the midpoint of a P9 is hard to verify.","section":"Section 4, first paragraph"},{"comment":"Observation 1(iii) says 'for each C6 either exactly two or none of its edges are in M'; this is likely intended to count the C6 edges that belong to M, but the wording could be clarified to avoid confusion with domination of C6 edges by M-edges outside the cycle.","section":"Section 2.2, Observation 1(iii)"},{"comment":"Step (C) applies the Vertex Reduction to x after all incident edges fail; this is only valid if the algorithm has indeed established that x is forced white. The link between exhaustively testing all incident edges and the forced-white conclusion should be stated explicitly, especially in view of the problem with Observation 4.","section":"Algorithm Step (C)"}],"recommendation":"major_revision","confidential_remarks":"The paper is a direct continuation of the authors' earlier work on P7- and P8-free graphs, and the self-citations are appropriate. The central claim may well be true, but as it stands the proof has two serious gaps: a false observation used in the preprocessing step and an unproved uniqueness assertion in the key polynomial-time lemma. I would be willing to reconsider a revised version that proves the missing 'Case 2.2 appears only once' statement and corrects the central-vertex argument; without those repairs, the polynomial-time theorem is not established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The paper is a genuine extension of the Pk-free DIM line: P9 is not in the cited literature, and the Section 3 machinery — distance levels, private-neighbor sets Ti, forcing rules, the component decomposition — is substantial original work, not a mechanical rerun of the P8 paper. Reuse of earlier published lemmas, such as Lemma 1 from [5], is legitimate citation, not circularity. If the proof were complete, Theorem 3 would be a solid increment in a well-known program.\n\nAs written, it is not complete. I agree with the stress-test note on Observation 4: the observation is false, and the triangle-with-two-tails example is a genuine counterexample. The proof's \"dist(w,y) < dist(v,y)\" is not a contradiction to centrality. But I also agree that this alone is probably patchable: in that example another central vertex satisfies the needed condition, so Step (A) could in principle still work. I would not rest a rejection on Observation 4 alone.\n\nThe load-bearing gap is Lemma 3, Section 3, case N4 = empty. The proof ends with a two-sentence assertion: if t2 does not completely color T3, we can \"add a possible coloring of T3\" that completely colors every neighbor, and \"Case 2.2 appears only once\" in the component because G is P9-free. This is exactly the claim that makes the search in Step (B.2) polynomial. No argument is supplied for either part: no proof that the added coloring is compatible with already forced colors, and no proof that a second occurrence of Case 2.2 contains an induced P9. If that assertion fails, the branching is not bounded polynomially and Theorem 3 does not follow. This is a major gap in the central argument, not a routine missing detail.\n\nThe paper reads honestly; the structural work is mostly careful, and the failure is an omitted proof step rather than an obviously wrong idea. But that is not enough for acceptance. Researchers working on DIM/EED and hereditary graph classes are the right audience, and the paper deserves a serious referee — the problem is natural, the extension is real, and the case analysis is large enough to pressure-test usefully. My recommendation is major revision, not acceptance: the authors need to prove the \"only once\" claim, or restructure Step (B.2) so it does not depend on it, and they need to fix Observation 4's statement and proof.","headline":"A substantial P9 extension with a real gap: Lemma 3's \"Case 2.2 appears only once\" assertion is load-bearing and unproved, and Observation 4 is false as stated.","tokens_in":21646,"tokens_out":6005,"would_cite":false,"duration_ms":63365,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C69","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that for every graph with no induced path on nine vertices, the existence of a dominating induced matching can be decided in polynomial time.","keywords":["dominating induced matching","efficient edge domination","P9-free graphs","polynomial-time algorithm","induced path","distance layers","black-white coloring","graph algorithms"],"falsifier":"Exhibit a connected P9-free graph with a central vertex v and an edge uv such that (i) uv lies in no induced P3, (ii) every d.i.m. contains uv, and (iii) no other edge incident to v can belong to a d.i.m.; then Step (B) finds no candidate edge and the algorithm terminates with the wrong answer. A concrete candidate is a triangle (u,v,w) with two length-2 tails attached at w, which has a unique d.i.m. using uv and appears to satisfy the failure conditions.","tokens_in":20700,"feed_emoji":"🧩","tokens_out":5291,"duration_ms":56620,"temperature":0.7,"pith_summary":"The paper extends the known polynomial-time boundary for Dominating Induced Matching (DIM) from P8-free graphs to P9-free graphs: in every connected graph that contains no induced path on nine vertices, one can decide in polynomial time whether some set of pairwise disjoint edges dominates every edge exactly once. The algorithm fixes a central vertex, tests each candidate matching edge incident to it by computing distance layers and forcing black-white colorings, and when no edge works, removes the central vertex as white and recurses on the remaining components. The result matters because DIM is NP-complete on general graphs, so each extension to a broader hereditary class shows where the hardness starts. If the proof is right, it also gives a constructive polynomial-time decision procedure, not merely an existence statement.","feed_headline":"Dominating induced matchings: polynomial time on P9-free graphs","feed_subtitle":"Extends the tractable boundary of an NP-complete problem from P8-free to P9-free graphs.","key_machinery":"The central machinery is the distance-level decomposition of a candidate d.i.m. edge xy, with layers $N_i = \\{z : \\mathrm{dist}(z, xy) = i\\}$. In a P9-free graph, $N_5$ is empty, so only four layers can contain anything. The argument uses a black-white feasible coloring model: black vertices are the endpoints of the matching edges, white vertices are the independent remainder, and the rules force colors layer by layer (white neighbors force black, black vertices force white neighbors, each $T_i$ must contain exactly one black vertex). The key structural lemmas bound the number of feasible colorings per component, using forbidden objects such as P5s with special endpoints, C6s and C7s in $G[S_2 \\cup N_3]$, and C9s involving N4.","core_discovery":"Theorem 3 is the central claim: DIM is solvable in polynomial time for P9-free graphs. Concretely, the algorithm takes a connected P9-free graph and a central vertex x whose distance to every other vertex is at most four, then for each edge xy incident to x it computes the distance layers N_i of xy and tries to extend xy to a full d.i.m. by a feasible black-white coloring. The structural analysis shows that N1 is an independent white set, N2 consists of forced black isolated vertices plus forced matching edges, N3 splits into private sets T_i attached to N2, and N4 components are paths or cycles with only few feasible colorings. The reductions force colors outward, and P9-freeness rules out the long induced paths that would allow too many colorings, so each candidate edge can be checked in polynomial time. If every incident edge fails, the central vertex is forced white and removed, and the process repeats on the components.","pith_inferences":["A natural testable extension is to attempt the same distance-layer strategy for P10-free graphs, where $N_5$ can be nonempty and new ambient structures enter the coloring analysis.","The layered coloring framework suggests a possible uniform approach for all fixed Pk-free classes via bounded-depth distance layers, though the current proof is specialized to depth four.","If the algorithm were implemented, the practical bottleneck would likely be the branching over feasible colorings of N4 components; small exhaustive checks on generated P9-free graphs could test where that branching actually appears.","The paper's low-level lemmas may be reusable for other domination-type problems on P9-free graphs, since the distance-layer decomposition is tied to the path bound rather than to the matching objective itself."],"forward_implications":["For every connected P9-free graph, the existence of a d.i.m. is decidable in time polynomial in the number of vertices, rather than being NP-complete.","The polynomial-time frontier for DIM moves one step further along the induced-path hierarchy, from P8-free to P9-free graphs, supporting the conjecture that DIM is tractable for every fixed Pk-free class.","The algorithm is constructive: when a d.i.m. exists it returns one, expressed as a feasible black-white coloring built from distance layers.","The reduction rules imply that any d.i.m. in a P9-free graph admits a forced layered structure, which could be used to enumerate or certify all d.i.m.s in polynomial time.","A direct consequence of Theorem 3 is that DIM is polynomial for every connected graph whose every component is P9-free, since the problem decomposes componentwise."],"supporting_citations":[{"why":"Supplies Theorem 2, that every connected Pt-free graph has a vertex within distance floor(t/2) of all others, which is the algorithm's starting point for choosing a central vertex.","marker":"[1]"},{"why":"Establishes linear-time DIM for P7-free graphs and is the source of Observation 1 and the triangle, diamond, and butterfly forcing rules reused here.","marker":"[4]"},{"why":"Gives the polynomial-time DIM algorithm for P8-free graphs and supplies the distance-level decomposition with S2, N3, and Ti machinery that this paper extends to the P9 case.","marker":"[5]"},{"why":"Proves NP-completeness of DIM for general graphs, the hardness baseline that makes polynomial results for P9-free graphs significant.","marker":"[10]"},{"why":"Introduces the feasible black-white coloring framework and the conjecture that DIM is polynomial for S_{i,j,k}-free graphs, which motivates the P9-free result.","marker":"[11]"}],"fun_headline_variants":["Polynomial-time DIM on P9-free graphs: a new frontier","DIM now polynomial on P9-free graphs","Extending tractability: DIM on P9-free graphs","From P8 to P9: DIM stays polynomial","P9-free graphs: dominating induced matchings in P-time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Observation 4: every edge incident to a central vertex in a P9-free graph lies in an induced P3, so testing only those edges in Step (B) cannot miss the unique d.i.m.; if that premise fails, the polynomial loop over candidate edges can skip the only edge that can carry the d.i.m.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time DIM on P9-free graphs: a new frontier","DIM now polynomial on P9-free graphs","Extending tractability: DIM on P9-free graphs","From P8 to P9: DIM stays polynomial","P9-free graphs: dominating induced matchings in P-time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000784,"raw_usage":{"total_tokens":3432,"prompt_tokens":885,"completion_tokens":2547,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":2463}},"tokens_in":501,"tokens_out":2547,"duration_ms":17657,"temperature":1.0,"reasoning_tokens":2463,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:33:44.993795+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a connected P9-free graph with a central vertex v and an edge uv such that (i) uv lies in no induced P3, (ii) every d.i.m. contains uv, and (iii) no other edge incident to v can belong to a d.i.m.; then Step (B) finds no candidate edge and the algorithm terminates with the wrong answer. A concrete candidate is a triangle (u,v,w) with two length-2 tails attached at w, which has a unique d.i.m. using uv and appears to satisfy the failure conditions.","supporting_citations":[{"cited_title":"Bacs´ o and Zs","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 2, that every connected Pt-free graph has a vertex within distance floor(t/2) of all others, which is the algorithm's starting point for choosing a central vertex."},{"cited_title":"Brandst¨ adt and R","cited_arxiv_id":null,"evidence_quote":"Establishes linear-time DIM for P7-free graphs and is the source of Observation 1 and the triangle, diamond, and butterfly forcing rules reused here."},{"cited_title":"Brandst¨ adt and R","cited_arxiv_id":null,"evidence_quote":"Gives the polynomial-time DIM algorithm for P8-free graphs and supplies the distance-level decomposition with S2, N3, and Ti machinery that this paper extends to the P9 case."},{"cited_title":"Grinstead, P.L","cited_arxiv_id":null,"evidence_quote":"Proves NP-completeness of DIM for general graphs, the hardness baseline that makes polynomial results for P9-free graphs significant."},{"cited_title":"Hertz, V.V","cited_arxiv_id":null,"evidence_quote":"Introduces the feasible black-white coloring framework and the conjecture that DIM is polynomial for S_{i,j,k}-free graphs, which motivates the P9-free result."}],"review_version":1}