{"id":"33183ad5-c133-4d1c-9c58-ee2077d04880","arxiv_id":"1908.03788","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every positive integer k, any graph that contains an induced path on k vertices also contains an avoidable induced path on k vertices.","lead":"This paper proves that every graph containing an induced path on k vertices also contains an avoidable induced path on k vertices, settling a 2019 conjecture. The result unifies earlier theorems on avoidable vertices and edges and comes with an elementary algorithm to find such a path.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the unexpanded induced-cycle lifting in Lemma 2.3 is valid, and the minimal-counterexample induction for Theorem 1.9 holds together.","rationale":"The reader's verdict is ACCEPT with moderate confidence, and its weakest-assumption analysis points to Lemma 2.3 as the most fragile unexpanded step. I focused on exactly that step. The worry is that replacing the merged vertex u in an induced cycle of G' by u1, u2, or the edge u1u2 might introduce a chord. A direct case analysis shows this cannot happen: because C is induced, u has exactly two neighbours a and b on C, and neither u1 nor u2 can have any adjacency to the rest of C beyond the chosen preimage(s). If a common preimage of a and b exists, one vertex closes the cycle; otherwise the two disjoint singleton preimages together with the edge u1u2 close it. No new chord can appear, and a-b is not an edge since C is induced. The remaining steps of the proof were checked for internal consistency: the use of minimality to obtain HR on the smaller merged graph, the domination claims in Claims 2.6 and 2.8, and the final contradictions in Lemmas 2.5 and 2.7 are all sound. The theorem's central claim is therefore supported, and the constructive algorithm matches the proof. I find no load-bearing objection, so the reader's ACCEPT verdict should stand unchanged. The only caveat is that the proof is not machine-checked; the suggested brute-force test would further reduce the already low residual risk around the one compressed case split.","tokens_in":116,"tokens_out":13554,"duration_ms":267381,"concrete_test":"Run an exhaustive brute-force verification of Lemma 2.3 for all graphs on at most 8 vertices: for every edge u1u2 and every induced path Q in G-N[{u1,u2}] that is avoidable in the merged graph G', check that Q is avoidable in G, i.e. that every extension xQy in G is contained in an induced cycle. If a counterexample appears, the replacement step in Lemma 2.3 is genuinely flawed; if none appears over the full enumeration, the compressed case split is confirmed on all small instances.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the induction, no load-bearing flaw emerges. The only genuinely compressed step is Lemma 2.3, where an induced cycle C in the merged graph G' containing the merged vertex u is lifted to G by replacing u with u1, u2, or the edge u1u2 'as appropriate'. This step is valid. Let a and b be the two neighbours of u on C. If some ui is adjacent to both a and b, insert ui and close the cycle through a-ui-b. Otherwise the sets of preimages of a and b are disjoint singletons, so one of u1,u2 is adjacent to a and the other to b; inserting the edge u1u2 closes a-ui-uj-b. In either case, no chord is introduced: any extra adjacency from ui to a vertex of C-{a,b} would make u adjacent to that vertex in G', contradicting that C is induced and u has degree 2 in C; and a-b cannot be an edge because C is induced. Thus the replacement is a genuine, though unexpanded, case split rather than a gap. With Lemma 2.3 secured, Claim 2.6, Lemma 2.5, and Lemma 2.7 are internally consistent, and the minimal-counterexample proof of Theorem 2.4 goes through. The algorithm in Section 3 faithfully mirrors the proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves the conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced path on k vertices also contains an avoidable induced path on k vertices. The proof is by minimal counterexample, using a strengthened induction hypothesis HR that asks for an avoidable P_k in G - N[u] whenever this induced subgraph contains a P_k. The central technical step is Lemma 2.3, which transfers HR from a graph obtained by merging an edge u_1u_2 into a vertex u back to the original graph. The authors also derive corollaries on multiple avoidable paths, exhibit a family of graphs showing that the analogous statement for two disjoint avoidable P_k fails for k >= 3, and give an O(n^{k+2}) algorithm based on the proof.","tokens_in":6104,"tokens_out":10141,"duration_ms":103284,"significance":"The result settles an open conjecture and unifies earlier work on avoidable vertices, avoidable edges, and the cycle-restricted theorem of Chvátal et al. The proof is elementary, self-contained, and the strengthened induction hypothesis is a clean and reusable idea. The explicit algorithm is a useful bonus, and its O(n^{k+2}) running time is plausibly best possible under ETH because it already must detect an induced P_k. The counterexample to the disjoint analogue sharpens the boundary of what can be expected from such theorems.","major_comments":[],"minor_comments":[{"comment":"The sentence \"By replacing u with either u1, u2 or the edge u1u2 as appropriate\" is the only place where the proof asks the reader to supply a nontrivial case split that is load-bearing for Claim 2.6 and Theorem 2.4. Please spell out the two cases: either some u_i is adjacent to both neighbours of u on the induced cycle C, in which case u_i closes the cycle directly, or the two preimages are distinct singletons, in which case the edge u_1u_2 closes the cycle. In both cases no chord is introduced, because any extra edge would create an adjacency from u to a non-neighbour on C in G'.","section":"Section 2, Lemma 2.3"},{"comment":"The title page has \"A voidable paths in graphs\" and the abstract has \"A voidability\"; these should be \"Avoidable paths\" and \"Avoidability\", respectively.","section":"Title and abstract"},{"comment":"The recurrence R(n) <= n·n^k + max(R(n-1), B(n-2)) omits the case where u is isolated, in which case the call to FindAvoidablePath(G - N[u], k) is on a graph with n-1 vertices. The correct bound is max(R(n-1), B(n-1)), and the stated O(n^{k+2}) conclusion is unchanged.","section":"Section 3, complexity analysis"},{"comment":"The correctness of the algorithm is stated only informally as following from the proof of Theorem 2.4. A short explicit invariant describing what FindAvoidablePathRefined(G, k, u) guarantees when HR(G, k, u) holds would make the algorithm verifiable, especially since the recursion can return a P_k found in a proper induced subgraph.","section":"Section 3, Algorithm 1"}],"recommendation":"minor_revision","confidential_remarks":"No concerns about novelty or citation practice. The only point that may deserve extra scrutiny in revision is the expanded case analysis in Lemma 2.3; after checking, it is valid, but it should be written out."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the real thing. The paper proves the Beisegel et al. conjecture: for every positive integer k, every graph with an induced P_k contains an avoidable P_k. Prior work covered k=1,2 and a cycle-restricted version by Chvátal et al. The proof is a minimal-counterexample induction with a strengthened property HR. The HR property is the new idea, and it does the job: Claim 2.6 says every P_k in G−N[u] dominates N(u), Lemma 2.5 uses that to pull the avoidable path back, and Lemma 2.7 finishes. I went through the steps; the logic is consistent and the induction is sound. The paper also subsumes the earlier theorems, which is fair because the proof is self-contained and actually gives the stronger statement.\n\nThe one soft spot is minor but real. Lemma 2.3 says that an induced cycle in the merged graph G′ containing the merged vertex u can be lifted to G by replacing u 'with either u1, u2 or the edge u1u2 as appropriate'. This is the hinge of the heredity argument, and the paper does not list the cases. I reconstructed them: if one of u1,u2 is adjacent to both neighbours of u on the cycle, insert that vertex; otherwise the two vertices split the two neighbours, so insert the edge. No chord appears because an extra adjacency from the inserted vertex to a cycle vertex would make u adjacent to a non-consecutive vertex in G′, contradicting that the cycle is induced. The case split is valid; it just needs to be written out.\n\nThe algorithm section is honest and the O(n^{k+2}) bound is fine. The ETH comment is correct. Minor quibbles: the recurrence for R(n) is sketched, and Question 4.1 is open, but neither affects the main theorem. The counter-example to the disjoint-paths analogue is a nice touch.\n\nThis is a genuine advance for structural graph theory and for people who construct induced paths. I would send it to review and, with the Lemma 2.3 case split made explicit, accept. There is no fitting and no overreach.","headline":"Solid proof of a genuine conjecture about avoidable induced paths; the only compressed step is a valid but unwritten case split.","tokens_in":6665,"tokens_out":3181,"would_cite":true,"duration_ms":32814,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C38","05C75","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every positive integer k, every graph that contains an induced path on k vertices also contains an avoidable path on k vertices.","keywords":["avoidable path","induced path","induced cycle","chordal graphs","graph algorithms","parameterized complexity","P_k-free","simplicial vertex"],"falsifier":"Find a graph G and edge u1u2 such that the merged graph G' has an induced cycle through the merged vertex u whose preimage under every one of the three replacements (u1 alone, u2 alone, or the edge u1u2) has a chord. Such an example would break Lemma 2.3 and with it the induction that proves Theorem 1.9.","tokens_in":5664,"feed_emoji":"🔗","tokens_out":5471,"duration_ms":52910,"temperature":0.7,"pith_summary":"This paper proves a conjecture about induced paths: for every positive integer k, every finite graph either has no induced path on k vertices, or it contains an avoidable one. An avoidable path is an induced path with the stronger property that every way of extending it by one vertex at each end closes up into an induced cycle. The result generalises the classical fact that chordal graphs have simplicial vertices, and it removes a cycle-length restriction from an earlier theorem. The proof is constructive and self-contained, and it yields an algorithm that runs in O($n^{{k+2}}$) time.","feed_headline":"Every graph with an induced path has an avoidable one","feed_subtitle":"New proof settles a recent conjecture for all path lengths and gives a near-optimal algorithm.","key_machinery":"The central device is the merging operation: given an edge u1u2, form G' by identifying u1 and u2 into a single vertex u with neighbourhood N({u1,u2}). Lemma 2.3 shows that if the refined property HR holds in the smaller merged graph, then HR passes back to the original graph at u1. That transfer step is the engine of the proof: an induced cycle through the merged vertex is turned into an induced cycle in the original graph by replacing u with u1, u2, or the edge u1u2 'as appropriate'. The induction then runs on a minimal counterexample, and two short claims force every induced P_k in the residual graph to dominate the relevant neighbourhood, producing the contradiction.","core_discovery":"The paper establishes Theorem 1.9: for every positive integer k, every graph that contains an induced P_k (an induced path on k vertices) also contains an avoidable P_k, where a path is avoidable when it is induced and every induced extension of it lies in an induced cycle. The proof goes through a stronger statement, property HR(G,k,u): for every graph G and vertex u, either G - N[u] contains no induced P_k, or G contains an avoidable P_k wholly inside G - N[u]. This stronger form is what makes the induction go through, and it also yields corollaries about finding two avoidable paths that are non-adjacent.","pith_inferences":["The same merging trick may transfer avoidability for other induced substructures whose extensions are paths, such as trees of fixed size, though the 'as appropriate' replacement step would need a new justification for branching shapes.","Corollary 1.10 gives a constructive handle on separator-based decompositions: repeatedly prune closed neighbourhoods to extract several mutually avoiding paths, which could be useful in graph-colouring or domination arguments.","The O(n^{k+2}) algorithm may be practical for small k (k=3,4) in sparse graphs, and could likely be improved by using faster algorithms for detecting induced paths in special graph classes, since the reduction step only calls InducedPath on subgraphs.","One untested direction is whether the graph family form of Question 4.1 has a positive answer if the family contains trees beyond paths; the paper's counterexample suggests that cycle structure, not just path structure, drives avoidability."],"forward_implications":["If G has an induced P_k avoiding a connected induced subgraph G[X] (i.e. in G - N[X]), then an avoidable P_k of G can be found there (Corollary 1.10).","If G contains two non-adjacent induced P_k, then it contains two non-adjacent avoidable P_k (Corollary 1.11).","The proof yields an explicit algorithm for finding an avoidable P_k in O(n^{k+2}) time, and the paper notes this is the best order of magnitude one can expect under the Exponential Time Hypothesis, because finding an induced P_k itself is W[1]-hard parameterised by k.","The natural analogue for disjoint paths fails: for every k >= 3 there is a graph with two disjoint induced P_k but no two disjoint avoidable P_k."],"supporting_citations":[{"why":"It states the conjecture and proves the base cases k=1,2, which this paper resolves.","marker":"[BCG+19]"},{"why":"It proves the same existence under a restriction on induced cycle lengths; this paper removes that restriction.","marker":"[CRS02]"},{"why":"It supplies the classical simplicial-vertex theorem for chordal graphs that avoidability generalises.","marker":"[Dir61]"},{"why":"It is one of the sources from which existence of an avoidable vertex (k=1) is inferred.","marker":"[OCF76]"},{"why":"It is another source for the avoidable-vertex existence theorem.","marker":"[BB98]"},{"why":"It is a further source for the avoidable-vertex existence theorem, cited for Theorem 1.2.","marker":"[ACTV15]"},{"why":"It provides the parameterized-hardness reference used to show an induced-path subroutine is nearly optimal under ETH.","marker":"[CFK+15]"}],"fun_headline_variants":["Induced paths guarantee avoidable counterparts","Every induced path yields an avoidable path","No induced path is alone: avoidable paths exist","For every k, induced P_k implies an avoidable P_k"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing step is Lemma 2.3's assertion that an induced cycle through the merged vertex can always be converted back to an induced cycle in the original graph by replacing the merged vertex with one endpoint, the other endpoint, or the edge between them, without creating a chord.","fun_headline_variants_meta":{"raw":{"variants":["Induced paths guarantee avoidable counterparts","Every induced path yields an avoidable path","No induced path is alone: avoidable paths exist","For every k, induced P_k implies an avoidable P_k"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000526,"raw_usage":{"total_tokens":2462,"prompt_tokens":791,"completion_tokens":1671,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":407,"completion_tokens_details":{"reasoning_tokens":1610}},"tokens_in":407,"tokens_out":1671,"duration_ms":14939,"temperature":1.0,"reasoning_tokens":1610,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:02:37.546234+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a graph G and edge u1u2 such that the merged graph G' has an induced cycle through the merged vertex u whose preimage under every one of the three replacements (u1 alone, u2 alone, or the edge u1u2) has a chord. Such an example would break Lemma 2.3 and with it the induction that proves Theorem 1.9.","supporting_citations":[],"review_version":1}