Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Connectivity-Preserving Minimum Separator in AT-free Graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2506.03612 v2 pith:KOHLOMEH submitted 2025-06-04 cs.DS

Batya Kenig This is my paper
classification cs.DS MSC 05C8505C4068Q2568R10
keywords safeseparatorconnectivity-preservingAT-freegraphsminimal2-disjointconnectedsubgraphsvertexminimumcutgraphalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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)}).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Figure 6, lines 11-14; Section 6 runtime paragraph] 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.
  2. [Section 4, Theorem 3] 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.
  3. [Section 3.2 and Section 4, Lemma 7] 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.
  4. [Section 4, Algorithm 1 overview] 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.
minor comments (5)
  1. [Figure 6, line 15] 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.
  2. [Section 3.2 and Appendix E] 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.
  3. [Appendix F, title] The title 'Min-Safe Sep ara tor' contains a spacing typo; it should read 'Min Safe Separator'.
  4. [Section 4, Lemma 6 proof in Appendix C] 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.
  5. [General notation] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: derivation is self-contained and relies on an external lemma; the identified empty-S* issue is a correctness bug, not a circular step.

full rationale

The paper's derivation chain is self-contained relative to standard min-separator theory. The central algorithm combines Definition 1, Lemmas 1-6 (proved in the appendix), Lemmas 9-12 and Corollary 3 (proved from AT-free structure), with Lemma 7 attributed to Takata [19] as an external black box. Lemma 7 is not derived from the target theorem, nor is it a self-citation; it is an external result from a 2010 journal paper. Corollary 1's reduction of "unique separator in N_G(sA)" to "unique close separator" uses Lemma 5 (proved) and is a genuine implication, not a definitional equivalence. The loop over pairs (S_A, S_B) and the contraction in Lemma 4 provide a constructive reduction from safe separators to ordinary min s,t-separators; no fitted parameter is renamed as a prediction. The skeptic's concern about the empty S* branch in CloseTo is a potential correctness bug in the pseudocode, not a circularity: it may cause Algorithm 1 to output an incorrect answer on some inputs, but it does not make the paper's derivation equivalent to its inputs. No circular step is exhibited, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on standard separator theory, the external Takata uniqueness theorem, and flow algorithms, plus the paper's own proven structural lemmas. No invented entities or fitted parameters.

assumptions (3)
  • standard math Lemma 7 (Takata): for a connected set sA avoiding N_G[t], N_G(sA) contains a unique minimal s,t-separator, findable in O(m) time.
    Used as a black box in Corollary 1, Lemma 9, and the CloseTo procedure; the uniqueness is load-bearing for enumerating 'close' separators, but no proof or exact reference location in [19] is given.
  • standard math Lemma 1 (Berry et al.): a separator X is a minimal s,t-separator iff N(C_s(G-X))=N(C_t(G-X))=X.
    Foundation for many arguments about full components; cited to [2] without proof.
  • standard math Max-flow min-cut and the almost-linear time minimum-cost flow algorithm are used to compute minimum s,t-separators in time T(n,m).
    Runtime bound for MinSep subroutine depends on external flow algorithms [4,21].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Connectivity-Preserving Minimum Separator in AT-free Graphs." pith.science (2026). https://pith.science/paper/KOHLOMEH

@misc{pith2026250603612,
  author       = {Pith},
  title        = {Pith review of: Connectivity-Preserving Minimum Separator in AT-free Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KOHLOMEH}},
  note         = {Machine review of arXiv:2506.03612}
}
abstract

Let $A$ and $B$ be disjoint, non-adjacent vertex-sets in an undirected, connected graph $G$, whose vertices are associated with positive weights. We address the problem of identifying a minimum-weight subset of vertices $S\subseteq V(G)$ that, when removed, disconnects $A$ from $B$ while preserving the internal connectivity of both $A$ and $B$. We call such a subset of vertices a connectivity-preserving, or safe minimum $A,B$-separator. Deciding whether a safe $A,B$-separator exists is NP-hard by reduction from the 2-disjoint connected subgraphs problem, and remains NP-hard even for restricted graph classes that include planar graphs, and $P_\ell$-free graphs if $\ell\geq 5$. In this work, we show that if $G$ is AT-free then in polynomial time we can find a safe $A,B$-separator of minimum weight, or establish that no safe $A,B$-separator exists.

Figures

Figures reproduced from arXiv: 2506.03612 by the authors.

Figure 2
Figure 2. ). Let S ∈ Ss,t(G). Lemma 11 establishes that A ⊆ Cs(G−S) if and only if Cs(G−S) ∩ TD ̸= ∅. The complete proof is in Section D of the Appendix. s Ts Ct(G−Ts) a1 a2 t [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Illustration for the proof of Theorem 2 (Case 2). [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 5
Figure 5. Illustration–Lemma 12. Corollary 3. Let G be AT-free, Ts ∈ Ss,t(G) where Ts ⊆ NG(s)\NG[t], and ∅ ⊂ A ⊆ V(G), such that A ∩ (Cs(G−Ts) ∪ Ts ∪ Ct(G−Ts)) = ∅. Define {C1, . . . , Cℓ} def = {C ∈ C(G−Ts) : C ∩ A ̸= ∅}, and S ∗ def = Tℓ i=1 NG(Ci). Then: {S ∈ Ss,t(G) : A ⊆ Cs(G−S)} = S v∈S∗ {S ∈ Ss,t(G) : v ∈ Cs(G−S)} Proof. Since ∅ ⊂ A ⊆ V(G)\(Cs(G−Ts) ∪ Ts ∪ Ct(G−Ts)), then ℓ ≥ 1. Assume wlog that |NG(C1)| ≤ |NG(C2)| ≤ ·… view at source ↗
Figures from the paper (1 more)
Figure 6
Figure 6. Figure 6: Algorithm for returning the minimal s, t-separators that are close to sA according to Definition 1 [PITH_FULL_IMAGE:figures/full_fig_p023_6.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems

    cs.DS 2025-11 unverdicted novelty 7.0 of 10

    Connectivity-preserving important separators of size at most k number 2^{O(k log k)} and can be enumerated in the same bound, yielding 2^{O(k log k)} FPT time for constant-class Node Multiway Cut-Uncut.

Reference graph

Works this paper leans on

24 extracted references · 8 canonical work pages · cited by 1 Pith paper

  1. [19]

    Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph.Discret

    Ken Takata. Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph.Discret. Appl. Math., 158(15):1660–1667, 2010.doi:10. 1016/j.dam.2010.05.013

    work page 2010

  2. [1]

    Fomin, Petr A

    Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach, and Tuukka Korhonen. Two-sets cut-uncut on planar graphs. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 ofLIPIcs, pages 22:1–22...

    doi:10.4230/lipics 2024

  3. [2]

    Generating all the minimal separators of a graph.Int

    Anne Berry, Jean Paul Bordat, and Olivier Cogis. Generating all the minimal separators of a graph.Int. J. Found. Comput. Sci., 11(3):397–403, 2000.doi: 10.1142/S0129054100000211

    doi:10.1142/s0129054100000211

  4. [3]

    On the complexity of testing for odd holes and induced odd paths.Discret

    Daniel Bienstock. On the complexity of testing for odd holes and induced odd paths.Discret. Math., 90(1):85–92, 1991.doi:10.1016/0012-365X(91)90098-M

    work page doi:10.1016/0012-365x(91)90098-m 1991

  5. [4]

    Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

    Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022.doi:10.1109/FOCS54457.2022.00064

    arXiv 2022

  6. [5]

    Asteroidaltriple-freegraphs

    DerekG.Corneil,StephanOlariu,andLornaStewart. Asteroidaltriple-freegraphs. SIAM J. Discret. Math., 10(3):399–430, 1997.doi:10.1137/S0895480193250125

    doi:10.1137/s0895480193250125 1997

  7. [6]

    Kevin Wood, and Alexandra M

    Christopher Cullenbine, R. Kevin Wood, and Alexandra M. Newman. Theoretical and computational advances for network diversion.Networks, 62(3):225–242, 2013. URL:https://doi.org/10.1002/net.21514,doi:10.1002/NET.21514

    doi:10.1002/net.21514 2013

  8. [7]

    Norman D. Curet. The network diversion problem.Military Operations Research, 6(2):35–44, 2001. URL:http://www.jstor.org/stable/43943674

    work page arXiv 2001

Show all 24 references
  1. [8]

    Solving the 2-Disjoint connected subgraphs problem faster than2 n

    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Woj- taszczyk. Solving the 2-Disjoint connected subgraphs problem faster than2 n. Algorithmica, 70(2):195–207, October 2014.doi:10.1007/s00453-013-9796-x

    2014 doi

  2. [9]

    On ddos attack related minimum cut problems.CoRR, abs/1412.3359, 2014

    Qi Duan, Jafar Haadi Jafarian, Ehab Al-Shaer, and Jinhui Xu. On ddos attack related minimum cut problems.CoRR, abs/1412.3359, 2014. URL:http://arxiv. org/abs/1412.3359,arXiv:1412.3359

    2014 arXiv

  3. [10]

    On the connectivity preserving minimum cut problem

    Qi Duan and Jinhui Xu. On the connectivity preserving minimum cut problem. J. Comput. Syst. Sci., 80(4):837–848, 2014. URL:https://doi.org/10.1016/j. jcss.2014.01.003,doi:10.1016/J.JCSS.2014.01.003

    2014 doi

  4. [11]

    Cambridge University Press, 2012

    Shimon Even and Guy Even.Graph Algorithms, Second Edition. Cambridge University Press, 2012

    2012

  5. [12]

    Golovach, Dieter Kratsch, and Daniël Paulusma

    Petr A. Golovach, Dieter Kratsch, and Daniël Paulusma. Detecting induced minors in AT-free graphs.Theor. Comput. Sci., 482:20–32, 2013. URL:https://doi.org/ 10.1016/j.tcs.2013.02.029,doi:10.1016/J.TCS.2013.02.029

    2013 doi

  6. [13]

    Silveira

    Chris Gray, Frank Kammer, Maarten Löffler, and Rodrigo I. Silveira. Remov- ing local extrema from imprecise terrains.Computational Geometry, 45(7):334– 349, August 2012. URL:https://www.sciencedirect.com/science/article/ pii/S0925772112000533,doi:10.1016/j.comgeo.2012.02.002

    2012 doi

  7. [14]

    Liu, and Aaron Sidford

    Tarun Kathuria, Yang P. Liu, and Aaron Sidford. Unit capacity maxflow in almost O(m 4 3 )time. In Sandy Irani, editor,61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 119–130. IEEE, 2020.doi:10.1109/FOCS4670...

    2020

  8. [15]

    The induced disjoint paths prob- lem

    Ken-ichi Kawarabayashi and Yusuke Kobayashi. The induced disjoint paths prob- lem. InIPCO, volume 5035 ofLecture Notes in Computer Science, pages 47–61. Springer, 2008

    2008

  9. [16]

    Disjoint paths and connected subgraphs for H- free graphs.Theoretical Computer Science, 898:59–68, 2022

    Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Disjoint paths and connected subgraphs for H- free graphs.Theoretical Computer Science, 898:59–68, 2022. URL: https://www.sciencedirect.com/science/article/pii/S0304397521006344, doi:https://d...

    2022 doi

  10. [17]

    Liu and Aaron Sidford

    Yang P. Liu and Aaron Sidford. Faster energy maximization for faster maximum flow. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Ka- math, and Julia Chuzhoy, editors,Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chi...

    2020

  11. [18]

    Daniël Paulusma and Johan M. M. van Rooij. On partitioning a graph into two connected subgraphs.Theoretical Computer Science, 412(48):6761–6769, November 2011. URL:https://www.sciencedirect.com/science/article/pii/ S0304397511007675,doi:10.1016/j.tcs.2011.09.001

    2011 doi

  12. [20]

    Connectingterminalsand2-disjointconnected subgraphs

    JanArneTelleandYngveVillanger. Connectingterminalsand2-disjointconnected subgraphs. In Andreas Brandstädt, Klaus Jansen, and Rüdiger Reischuk, editors, Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revis...

    2013

  13. [21]

    Liu, Maxi- milian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford

    Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maxi- milian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In64th IEEE Annual Sym- posium on Foundations of Computer Science, FOCS 2...

    2023

  14. [22]

    Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang

    Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, MDPs, andℓ1-regression in nearly linear time for dense instances. In Samir Khuller and Virginia Vassilevska Williams, editors,STOC ’21: 53rd Annual AC...

    2021

  15. [23]

    Woeginger

    Pim van ’t Hof, Daniël Paulusma, and Gerhard J. Woeginger. Partitioning graphs into connected parts.Theoretical Computer Science, 410(47):4834–4843, November 2009. URL:https://www.sciencedirect.com/science/article/pii/ S0304397509004198,doi:10.1016/j.tcs.2009.06.028. APPENDIX ...

    2009 doi

  16. [24]

    The input to this problem is an undirected graphGand a collection ofkvertex pairs {(s1, t1),

    We show this by reduction from theInduced disjoint pathsproblem. The input to this problem is an undirected graphGand a collection ofkvertex pairs {(s1, t1), . . . ,(sk, tk)}wheres i ̸=t i andk≥2. The goal is to determine whether Ghas a set ofkpaths that are mutually induced (...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.