{"id":"c77d0517-3c29-4572-b1b8-ec2bb9965dff","arxiv_id":"2506.03612","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A polynomial-time algorithm computes a minimum-weight connectivity-preserving A,B-separator in AT-free graphs, or decides none exists, running in O(n^4 T(n,m)).","lead":"The paper gives a polynomial-time algorithm to find a minimum-weight vertex set that separates two specified groups A and B in an AT-free graph while keeping each group internally connected. It also proves new NP-hardness results for general graphs with two terminals per group, and introduces structural properties of minimal separators that may be reusable.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"CloseTo's empty-S* branch is mishandled, so Algorithm 1 returns the wrong answer on a 4-vertex AT-free graph; Theorem 3 is also never proved.","rationale":"The reader rejected the paper for missing proof of Theorem 3 and an alleged black-box uniqueness lemma. My stress-test confirms the missing proof is a real problem, but identifies a sharper and more concrete failure: the published pseudocode of CloseTo is incorrect for empty S*, causing Algorithm 1 to fail on a trivial AT-free path instance. This is a counterexample to the central algorithmic claim as stated, not merely an unproved theorem. Lemma 7 (Takata uniqueness) actually appears to be true—one can prove that any two minimal s,t-separators contained in N(X) for connected X must coincide—so that specific reader concern is less severe. However, the empty-S* bug is decisive: the algorithm as written does not implement the intended procedure, and the paper's correctness theorem is therefore false as stated. The issues are likely fixable (e.g., by adding an explicit branch for S* empty and providing a formal proof of Theorem 3), but the manuscript as presented does not support the claimed result. I recommend REJECT rather than CONDITIONAL because the provided algorithm is demonstrably wrong on a valid input, and the central theorem is unproved.","tokens_in":23654,"tokens_out":50845,"duration_ms":524653,"concrete_test":"Run Algorithm 1 (or just CloseTo) on the path graph with vertices a-b-c-d, A={a,b}, B={d}, s=a, t=d, all weights 1. The correct output is {c}. With the published pseudocode, CloseTo returns an empty family because S* is empty, and the algorithm outputs ⊥. This single instance falsifies the claimed correctness of Theorem 3. A secondary check: patch lines 14-26 to handle S*=∅ by executing once with A_v=A, and verify the algorithm then outputs {c}.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim is that Algorithm 1 finds a minimum safe A,B-separator. This is false for the algorithm as written. In CloseTo (Figure 6, lines 11-14), when no component C of G'−T_s contains a vertex of A outside the s- and t-components, the set S* is empty. The accompanying text says the loop should then execute once with A_v=A, but the pseudocode's 'for all v in S*' loop does not execute, so F remains empty and CloseTo returns an empty family. This is not a cosmetic mismatch: on the AT-free path a-b-c-d with A={a,b}, B={d}, unit weights, and s=a, t=d, the unique safe separator is {c}. Algorithm 1 removes L=N(A)∩N(B)={c}, leaving G' with components {a,b} and {d}. CloseTo(G',a,d,{b}) has T_s={b} and sA={a,b} not contained in C_s(G'−T_s)={a}; since A={b} lies in T_s, there are no qualifying components, so S* is empty and the pseudocode returns no candidate separators. The main loop then finds no pair (S_A,S_B), and Algorithm 1 outputs ⊥ instead of {c}. Thus Theorem 3, which asserts the algorithm returns a minimum safe separator, fails on a simple input. Additionally, no formal proof of Theorem 3 is provided; the sketch in Section 4 does not address corner cases such as empty S*, disconnected s and t after removing mandatory vertices, or the case where the contracted sets are disjoint but one is not contained in the other's s-component. These are not merely missing details: the pseudocode is demonstrably incorrect as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims the first polynomial-time algorithm for the minimum-weight connectivity-preserving (safe) A,B-separator problem on AT-free graphs, with running time O(n^4 T(n,m)) where T(n,m) is the time for a minimum s,t-separator. The approach introduces the notion of minimal s,t-separators close to a connected vertex set sA, proves structural results about such separators in AT-free graphs, and combines them in Algorithm 1, whose main subroutine CloseTo enumerates the family of close separators. The central algorithmic claim is Theorem 3, that Algorithm 1 returns a minimum safe separator or correctly reports that none exists.","tokens_in":23969,"tokens_out":4081,"duration_ms":49277,"significance":"If the main claim were correct, the paper would be significant: it would give the first polynomial-time algorithm for the minimum safe A,B-separator with unbounded A and B on a broad infinite graph class, and the structural lemmas on minimal separators in AT-free graphs could be of independent interest. However, the manuscript as written has a concrete correctness bug in the CloseTo procedure that makes Algorithm 1 fail on a simple 4-vertex path, and the central theorem is stated without a proof. These issues are load-bearing, so the current version cannot be accepted despite the value of the surrounding structural work.","major_comments":[{"comment":"The empty-S* branch is not implemented in the pseudocode, and this is not a cosmetic issue. Figure 6 computes S* as the intersection over the components C_i that contain A outside the s- and t-components; when no such component exists, the accompanying text says the loop should execute once with A_v = A, but the code's 'for all v in S*' loop executes zero times and F remains empty. This yields a wrong answer on the AT-free path a-b-c-d with A={a,b}, B={d}, unit weights, s=a, t=d. The unique safe separator is {c}; Algorithm 1 removes N(A)∩N(B)={c}, leaving G' with components {a,b} and {d}. CloseTo(G',a,d,{b}) then has T_s={b} and sA={a,b} not contained in C_s(G'-T_s)={a}; since A={b} lies in T_s, no component qualifies, so S* is empty and the pseudocode returns no candidate separators. The main loop finds no pair (S_A,S_B), and Algorithm 1 outputs ⊥ instead of {c}. This directly contradicts Theorem 3 and Corollary 2.","section":"Figure 6, lines 11-14; Section 6 runtime paragraph"},{"comment":"Theorem 3, which asserts the correctness of Algorithm 1, is stated without a proof. The paragraph after Lemma 8 gives an informal derivation, but it does not constitute a complete correctness argument: it does not address the empty-S* branch, the case where s and t become disconnected after removing mandatory vertices, or the case in the counterexample above where the contracted sets are disjoint but the relevant containment conditions fail. Since the correctness of the algorithm is the central claim of the paper, the absence of a formal proof is a load-bearing gap.","section":"Section 4, Theorem 3"},{"comment":"Lemma 7 is used as a black box from Takata [19] with no theorem number, no proof, and no verification that the cited result implies the precise uniqueness statement needed: that N_G(sA) contains a unique minimal s,t-separator close to sA, findable in O(m) time. This uniqueness is load-bearing for Corollary 1, Lemma 9, and the CloseTo procedure; if the cited theorem does not imply exactly this claim, the enumeration step collapses. The authors should either prove the claim directly or give a precise citation with a theorem number and a derivation of the stated form.","section":"Section 3.2 and Section 4, Lemma 7"},{"comment":"The correctness argument for the reduction of safe A,B-separators to pairs (S_A,S_B) assumes that every safe minimal separator S is captured by some pair of close separators with the appropriate containment. This step relies on Lemma 6 and Lemma 8 and is plausible, but it is only sketched in Section 4; the sketch does not handle the interaction between the empty-close-family case and the mandatory set N(A)∩N(B), which is exactly where the counterexample fails. The proof needs to be supplied in full to be checked.","section":"Section 4, Algorithm 1 overview"}],"minor_comments":[{"comment":"The pseudocode in line 15 refers to C_s(G−T_s) and T_s, but these objects were computed in G′; the notation should be made consistent (e.g., C_s(G′−T_s)) to avoid ambiguity.","section":"Figure 6, line 15"},{"comment":"The symbol S* is introduced both as an intersection over the neighborhoods of components and then treated as an empty set when no components exist; the paper should state the convention explicitly, since an empty intersection over a family of sets is usually the whole vertex set.","section":"Section 3.2 and Appendix E"},{"comment":"The title 'Min-Safe Sep ara tor' contains a spacing typo; it should read 'Min Safe Separator'.","section":"Appendix F, title"},{"comment":"In the proof of Lemma 6, the notation 'C_S(G−S)' appears where 'C_s(G−S)' is meant; this typo should be corrected.","section":"Section 4, Lemma 6 proof in Appendix C"},{"comment":"The use of the symbol 'T' both for a minimal separator and for the intersection operator in the definition of S* is distracting; a different symbol for the intersection operation would improve readability.","section":"General notation"}],"recommendation":"reject","confidential_remarks":"The concrete counterexample in the report shows that Algorithm 1 as written returns the wrong answer on a 4-vertex AT-free graph, so the central algorithmic claim fails for the submitted artifact. The omitted proof of Theorem 3 and the unsupported Lemma 7 are additional major gaps. The structural results in Sections 5 and 6 may be salvageable, so a revised paper that fixes the empty-S* branch, supplies a full correctness proof, and either proves or precisely cites the uniqueness lemma could be reconsidered as a new submission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper tackles Min Safe Separator on AT-free graphs and claims an O(n^4 T(n,m)) algorithm when A and B are unbounded. The high-level strategy is genuinely novel: define \"close\" minimal separators, show that in AT-free graphs there are at most n^2 of them, enumerate all pairs, contract the relevant connected components, and reduce to a minimum s,t-separator computation. The structural lemmas, especially Lemma 12 about nested neighborhoods of components outside T_s, look plausible and are the real contribution here. If Theorem 3 were proven, this would be the first polynomial-time algorithm for unbounded A,B on a broad graph class and would improve the existing O(n^15) decision algorithm for 2-disjoint connected subgraphs.\n\nThe paper is not ready as submitted. The main issue: Theorem 3, the correctness of Algorithm 1, is stated without proof. The overview in Section 4 gives a sketch, but it does not handle the compatibility condition in line 8, does not justify disjointness of the two contracted sets, and does not account for cases where one of the candidate families is empty. That is a load-bearing gap, not a stylistic omission.\n\nSecond, the CloseTo pseudocode does not match its own prose. The text explicitly says that when S* is empty the loop should run once with A_v = A, but Figure 6's \"for all v in S*\" skips entirely. On the AT-free path a-b-c-d with A={a,b}, B={d}, the printed code returns ⊥ instead of the unique safe separator {c}. I traced the branch and the stress-test counterexample is correct. The bug is likely fixable since the prose describes the intended behavior, but it means the algorithm as written is not the algorithm described.\n\nThird, Lemma 7 is load-bearing: it asserts uniqueness of a minimal s,t-separator in N_G(sA) when G[sA] is connected, citing Takata without a theorem number. If that exact statement is not in [19], the enumerative machinery collapses. The rest of the citation pattern looks fine, and the related work on 2-disjoint connected subgraphs is covered fairly.\n\nThis paper is for researchers working on graph separators, AT-free graphs, and connectivity-constrained cuts. The structural lemmas may be of independent interest even if the main theorem needs repair. I would send it to a serious referee, but with the clear expectation that the proof of Theorem 3 must be supplied and the pseudocode corrected. I would not cite the main result yet.","headline":"Plausible and structurally interesting approach to safe separators in AT-free graphs, but the central correctness theorem is unproved and the printed pseudocode has a concrete bug, so it should not be accepted as-is.","tokens_in":24511,"tokens_out":7181,"would_cite":false,"duration_ms":81183,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C40","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that in AT-free graphs a minimum-weight safe A,B-separator can be found in O(n^4 T(n,m)) time, the first polynomial-time algorithm for unbounded A and B on an infinite graph class.","keywords":["safe separator","connectivity-preserving separator","AT-free graphs","minimal separator","2-disjoint connected subgraphs","vertex separator","minimum cut","graph algorithms"],"falsifier":"Run the following check on any small graph: pick vertices s and t and a set A such that G[sA] is connected and sA ∩ N[t] = ∅, then list all minimal s,t-separators contained in N_G(sA); if two distinct such separators exist, Lemma 7 as the paper uses it is false and the enumeration step loses its guarantee. Equivalently, search AT-free graphs for an instance where the number of close separators exceeds $n^{2}$, which would refute Theorem 2 and the O($n^{4}$) runtime.","tokens_in":23426,"feed_emoji":"✂️","tokens_out":8556,"duration_ms":85021,"temperature":0.7,"pith_summary":"This paper gives the first polynomial-time algorithm for the connectivity-preserving, or \"safe,\" minimum A,B-separator problem on AT-free graphs, a class that includes interval, permutation, and cocomparability graphs. In this problem one wants a minimum-weight set of vertices whose removal disconnects a vertex set A from a vertex set B while keeping A and B each internally connected; deciding merely whether such a separator exists is NP-hard in general, even when A and B each have only two vertices. The paper proves that in AT-free graphs the number of \"close\" minimal separators one needs to consider is polynomial (at most $n^{2}$, or n under a favorable condition), and that by enumerating them and contracting components one can reduce the problem to O($n^{4}$) calls to a minimum s,t-separator subroutine. If correct, this is the first polynomial bound for the safe separator problem with unbounded A and B on any infinite nontrivial graph class.","feed_headline":"AT-free graphs get the first polynomial-time safe separator algorithm.","feed_subtitle":"Finds a minimum-weight cut keeping A and B internally connected, with O(n^4) minimum separator calls.","key_machinery":"The load-bearing object is the family F_sA(G): the minimal s,t-separators that are \"close to sA,\" meaning they keep A on the s-side and are minimal with respect to the size of the s-side component among all minimal s,t-separators that do so. The argument depends on a uniqueness lemma (cited as [19]) stating that when G[sA] is connected and sA avoids the closed neighborhood of t, the neighborhood N_G(sA) contains exactly one minimal s,t-separator; this lets individual candidates be generated in O(m) time. The AT-free structure enters through a lemma (Lemma 12) showing that, for the unique separator T_s that lies in N_G(s), the neighborhoods of components of G - T_s other than the s- and t-sides are nested by inclusion; absence of an asteroidal triple is exactly what forces this nesting. Nesting implies that the set of separators keeping A on the s-side is a union of at most |T_s| ≤ n families, each of size at most n, yielding the O($n^{2}$) bound and the close-separator enumeration in O($n^{2}$ m) time. The final reduction contracts the s-side component of a close separator and the t-side component of another, after which any minimum s,t-separator of the contracted graph is a minimum safe separator.","core_discovery":"The central claim is Theorem 1: for any connected, vertex-weighted AT-free graph G and disjoint non-adjacent vertex sets A and B, there is an algorithm that either outputs a minimum-weight safe A,B-separator or correctly reports that none exists, running in O($n^{4}$ · T(n,m)) time, where T(n,m) is the cost of a single minimum s,t-separator computation (currently $m^{{1+o(1)}}$). The proof shows that every minimal safe separator is, for any chosen s in A and t in B, a minimal s,t-separator whose s-side contains A and whose t-side contains B. The number of candidates that need to be checked is bounded polynomially: the family F_sA(G) of minimal s,t-separators that are \"close\" to sA has size at most $n^{2}$ in an AT-free graph, and this bound is proved using a nesting property of component neighborhoods that rules out asteroidal triples. The algorithm enumerates these families for A and B, contracts the s-side and t-side components, and solves a plain minimum s,t-separator instance for each pair.","pith_inferences":["The enumeration-plus-contraction pattern suggests a meta-result: any graph class where the close-separator families for unbounded vertex sets have polynomial size inherits a polynomial algorithm for the safe separator problem; AT-free graphs are the first such class.","The uniqueness lemma cited as [19] deserves a self-contained proof or a counterexample, since it is used for both correctness and runtime; if it does not hold in full generality, Theorem 1 would still be valid on any subclass of AT-free graphs where the uniqueness property does hold.","A testable extension is to chordal or circular-arc graphs: if their minimal-separator families have similar nesting or bounded close-enumeration, the same reduction would yield the first safe-separator algorithm for those classes.","The hardness reductions in the appendix imply that safe separators encode disjoint connected subgraphs, so any future algorithm must implicitly solve that NP-hard problem; the AT-free structural lemmas are precisely what make the encoding harmless there."],"forward_implications":["In every AT-free graph, including interval, permutation, cocomparability, cobipartite, and trapezoid graphs, the minimum safe A,B-separator can be found in O(n^4 · T(n,m)) time, and in O(n^2 · T(n,m)) time when A and B lie near the unique s- and t-side separators.","The safe-separator decision problem is NP-hard in general and remains NP-hard with |A|=|B|=2, so a polynomial algorithm cannot be expected on unrestricted graphs; AT-free graphs mark a genuine tractability boundary.","The structural result that close minimal separators in AT-free graphs number at most n^2 is a transferable ingredient: it turns a question about disjoint connected subgraphs into a question about enumerable minimal separators.","Because the algorithm is built on any minimum s,t-separator oracle, improvements to max-flow immediately improve the safe-separator runtime; with current max-flow the bound is O(n^4 m^{1+o(1)})."],"supporting_citations":[{"why":"Supplies the uniqueness lemma for the minimal s,t-separator in N_G(sA), which is the load-bearing property behind the close-separator enumeration.","marker":"[19]"},{"why":"Shows 2-disjoint connected subgraphs is polynomial in AT-free graphs with O(n^15) runtime; this paper's algorithm extends that setting to minimum safe separators much faster.","marker":"[12]"},{"why":"Introduces the connectivity-preserving minimum separator problem and shows the vertex variant with |A|=2, |B|=1 is hard to approximate while the edge variant is tractable on planar graphs; the problem definition and hardness context come from here.","marker":"[10]"},{"why":"Standard reduction from minimum s,t-separator to minimum s,t-cut / max-flow, defining the subroutine time T(n,m) in Theorem 1.","marker":"[11]"},{"why":"Almost-linear time max-flow algorithm, giving the current bound T(n,m) = m^{1+o(1)} quoted in the runtime.","marker":"[4]"},{"why":"NP-completeness of 2-disjoint connected subgraphs, used in the appendix to prove Min Safe Separator NP-hard by edge subdivision.","marker":"[23]"},{"why":"NP-hardness of induced disjoint paths with k=2, used to show safe-separator existence is NP-hard even when |A|=|B|=2.","marker":"[15]"}],"fun_headline_variants":["Polynomial-time safe separator for AT-free graphs","First poly-time algorithm for safe A-B separators","Safe separators now polynomial in AT-free graphs","AT-free graphs: safe separators in polynomial time","Minimum-weight safe cuts for AT-free graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm stands on a black-box lemma cited as [19] asserting that if the closed set sA is connected and avoids the closed neighborhood of t, then the neighborhood of sA contains exactly one minimal s,t-separator; if that uniqueness claim is not actually true, the enumeration of the candidate family collapses and with it the polynomial bound.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time safe separator for AT-free graphs","First poly-time algorithm for safe A-B separators","Safe separators now polynomial in AT-free graphs","AT-free graphs: safe separators in polynomial time","Minimum-weight safe cuts for AT-free graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00019,"raw_usage":{"total_tokens":1348,"prompt_tokens":959,"completion_tokens":389,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":317}},"tokens_in":575,"tokens_out":389,"duration_ms":4708,"temperature":1.0,"reasoning_tokens":317,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:01:54.676671+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the following check on any small graph: pick vertices s and t and a set A such that G[sA] is connected and sA ∩ N[t] = ∅, then list all minimal s,t-separators contained in N_G(sA); if two distinct such separators exist, Lemma 7 as the paper uses it is false and the enumeration step loses its guarantee. Equivalently, search AT-free graphs for an instance where the number of close separators exceeds $n^{2}$, which would refute Theorem 2 and the O($n^{4}$) runtime.","supporting_citations":[{"cited_title":"Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph.Discret","cited_arxiv_id":null,"evidence_quote":"Supplies the uniqueness lemma for the minimal s,t-separator in N_G(sA), which is the load-bearing property behind the close-separator enumeration."},{"cited_title":"Golovach, Dieter Kratsch, and Daniël Paulusma","cited_arxiv_id":null,"evidence_quote":"Shows 2-disjoint connected subgraphs is polynomial in AT-free graphs with O(n^15) runtime; this paper's algorithm extends that setting to minimum safe separators much faster."},{"cited_title":"The induced disjoint paths prob- lem","cited_arxiv_id":null,"evidence_quote":"NP-hardness of induced disjoint paths with k=2, used to show safe-separator existence is NP-hard even when |A|=|B|=2."}],"review_version":1}