arxiv: 2511.15849 · v3 · submitted 2025-11-19 · 💻 cs.DS · cs.CC

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

Batya Kenig This is my paper

Pith reviewed 2026-05-17 20:02 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords important separatorscut-uncut problemsfixed-parameter algorithmsnode multiway cutgraph separationconnectivity constraintsenumeration algorithmsparameterized complexity

0 comments

The pith

Connectivity-preserving important separators can be enumerated in 2^{O(k log k)} time, extending classical separator techniques to cut-uncut problems that require both disconnection and internal connectivity preservation.

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

The paper establishes a structured family of separators for graphs where some terminals must be disconnected while others must remain connected within specified groups. It proves that connectivity-preserving important separators of size at most k number at most 2 to the O of k log k and can be listed efficiently up to polynomial overhead. This bound directly yields faster fixed-parameter algorithms for Node Multiway Cut-Uncut when the number of connectivity equivalence classes is constant. A reader would care because many network design and clustering tasks mix separation requirements with preservation constraints, and prior important-separator methods broke down in these mixed settings. If the bound holds, separator-based FPT techniques become applicable to a broader class of problems that combine cutting and keeping connections.

Core claim

We introduce connectivity-preserving important separators, a new framework for cut problems with connectivity constraints. Our main result shows that this family is highly structured: the number of connectivity-preserving important separators of size at most k is 2^{O(k log k)}, and they can be enumerated within the same bound up to polynomial factors. As an application, we obtain improved fixed-parameter algorithms for Node Multiway Cut-Uncut. In particular, when the number of equivalence classes is constant—including 2-Sets Cut-Uncut—our approach yields a 2^{O(k log k)} running time, improving on the previous 2^{O(k^2 log k)} dependence. More broadly, our results show that separator-based

What carries the argument

Connectivity-preserving important separators: minimal vertex sets that separate some terminal pairs while keeping terminals inside each equivalence class path-connected, serving as the enumerable building blocks that replace classical reachability-based important separators in mixed cut-preserve settings.

If this is right

Node Multiway Cut-Uncut with a constant number of equivalence classes admits a 2^{O(k log k)} FPT algorithm.
2-Sets Cut-Uncut improves from 2^{O(k^2 log k)} to 2^{O(k log k)} time.
Separator enumeration extends from pure disconnection problems to any setting that simultaneously requires cuts and preservation of specified connectivities.
The same enumeration bound supports kernelization or branching algorithms that rely on guessing a small separator in cut-uncut instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The enumeration procedure may generalize to weighted or directed graphs if the importance notion is redefined via shortest-path or flow distances.
Problems with implicitly defined connectivity constraints, such as those arising from matroid or clustering objectives, could be attacked once the constraints are materialized.
The 2^{O(k log k)} bound suggests that similar structured families exist for other mixed separation-preservation tasks, such as Steiner multicut with group-connectivity requirements.

Load-bearing premise

The connectivity constraints must be supplied explicitly as equivalence classes on terminals, and the input graph must be undirected and simple.

What would settle it

Construct an explicit family of undirected graphs with given terminal equivalence classes where the count of connectivity-preserving important separators of size k exceeds 2^{c k log k} for any fixed c, or exhibit an instance on which any enumeration algorithm requires super-2^{O(k log k)} time.

Figures

Figures reproduced from arXiv: 2511.15849 by Batya Kenig.

read the original abstract

Graph separation is a central tool in parameterized algorithm design, and important separators are among its most successful ingredients. They yield small, structured families of separators that can be enumerated efficiently, and underlie fixed-parameter algorithms for many problems. However, this framework fundamentally breaks down in cut-uncut settings, where one must separate terminal sets while preserving connectivity inside specified groups of terminals. In such problems, the classical reachability-based notion of importance no longer captures the separators that matter. We introduce connectivity-preserving important separators, a new framework for cut problems with connectivity constraints. Our main result shows that this family is highly structured: the number of connectivity-preserving important separators of size at most $k$ is $2^{O(k \log k)}$, and they can be enumerated within the same bound up to polynomial factors. As an application, we obtain improved fixed-parameter algorithms for Node Multiway Cut-Uncut. In particular, when the number of equivalence classes is constant - including 2-Sets Cut-Uncut - our approach yields a $2^{O(k \log k)}$ running time, improving on the previous $2^{O(k^2 \log k)}$ dependence. More broadly, our results show that separator-based methods can be extended from pure disconnection problems to problems that simultaneously require separation and preservation of connectivity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper defines connectivity-preserving important separators and shows they number at most 2^{O(k log k)} with an enumeration algorithm in the same bound, yielding faster FPT for Node Multiway Cut-Uncut with constant equivalence classes.

read the letter

The main thing to know is that the authors have adapted the important-separator framework to cut-uncut problems by introducing connectivity-preserving important separators. The standard reachability notion fails here because it does not account for the terminals that must stay connected, so a new definition is needed to capture the separators that actually matter for these mixed constraints.

Referee Report

1 major / 3 minor

Summary. The paper introduces connectivity-preserving important separators as an extension of the classical important-separator framework to cut-uncut problems that require both separating certain terminal sets and preserving connectivity within specified groups. The central result establishes that the number of connectivity-preserving important separators of size at most k is 2^{O(k log k)} and that they can be enumerated in the same bound up to polynomial factors. This framework is applied to Node Multiway Cut-Uncut, yielding a 2^{O(k log k)} FPT algorithm when the number of equivalence classes is constant (including the 2-Sets Cut-Uncut case), improving on the prior 2^{O(k^2 log k)} dependence.

Significance. If the enumeration bound and reduction hold, the work meaningfully extends separator techniques to mixed cut-and-preservation settings, which are common in parameterized graph problems. The explicit 2^{O(k log k)} bound and the improved runtime for constant-class Node Multiway Cut-Uncut constitute a concrete advance. The paper receives credit for deriving a structured, enumerable family that directly supports better algorithms without relying on ad-hoc case analysis.

major comments (1)

[§4] §4 (application to Node Multiway Cut-Uncut): the reduction invokes the enumeration routine; it is not immediately clear whether the number of invocations is bounded by a function of the (constant) number of classes alone or whether an extra k-dependent factor appears in the analysis that would affect the claimed 2^{O(k log k)} runtime.

minor comments (3)

[Definition 3.1] Definition 3.1: the formal definition of a connectivity-preserving important separator would benefit from an explicit comparison to the classical reachability-based importance condition to highlight the precise modification.
[Abstract] The abstract states the enumeration bound 'up to polynomial factors'; stating the precise polynomial degree or the form of the enumeration time (e.g., 2^{O(k log k)} n^{O(1)}) would improve precision.
[Figure 2] Figure 2: the diagram illustrating a connectivity-preserving separator would be clearer if the equivalence classes were labeled directly on the terminals.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation for minor revision. The single major comment concerns the runtime analysis in the application to Node Multiway Cut-Uncut; we address it directly below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [§4] §4 (application to Node Multiway Cut-Uncut): the reduction invokes the enumeration routine; it is not immediately clear whether the number of invocations is bounded by a function of the (constant) number of classes alone or whether an extra k-dependent factor appears in the analysis that would affect the claimed 2^{O(k log k)} runtime.

Authors: We appreciate the referee highlighting this point for clarity. In the reduction of Section 4, the algorithm enumerates all connectivity-preserving important separators of size at most k (in 2^{O(k log k)} time) and, for each such separator, performs a constant number of recursive subcalls whose branching factor depends only on the fixed number c of equivalence classes. Because c is constant, this contributes a multiplicative factor of 2^{O(c)} per enumerated separator. The recursion depth is at most k, but the overall search tree size is bounded by 2^{O(k log k)} (absorbing the constant-class branching into the O-notation). Consequently, the total running time remains 2^{O(k log k)} n^{O(1)} with no additional k-dependent factor arising from the number of invocations. We will insert a short clarifying paragraph at the end of Section 4 that explicitly states this bound on the number of invocations and recomputes the runtime to make the dependence on c transparent. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper defines connectivity-preserving important separators as a new extension of the classical important-separator framework to handle joint cut-and-preservation constraints. The central claim is a combinatorial upper bound of 2^{O(k log k)} on the number of such separators of size at most k, together with an enumeration algorithm achieving the same bound up to polynomial factors. This bound is presented as a theorem proved via graph-theoretic arguments on the structure of separators that respect given connectivity equivalence classes. No equation or lemma reduces the claimed count to a fitted parameter, a self-referential definition, or a load-bearing self-citation whose validity depends on the present result. The framework is explicitly positioned as building on prior independent work on important separators, and the application to Node Multiway Cut-Uncut follows directly from the new enumeration procedure. The derivation chain therefore remains non-circular and externally verifiable through standard parameterized-algorithm techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard undirected-graph separation axioms plus the new definition of connectivity preservation; no free parameters or invented entities are visible in the abstract.

axioms (1)

standard math Undirected graphs admit well-defined vertex separators and reachability relations.
Invoked implicitly when defining separators and connectivity preservation.

invented entities (1)

connectivity-preserving important separator no independent evidence
purpose: A separator that disconnects terminals while preserving connectivity inside specified equivalence classes.
New object introduced to extend the classical important-separator framework to cut-uncut problems.

pith-pipeline@v0.9.0 · 5530 in / 1260 out tokens · 113230 ms · 2026-05-17T20:02:05.479930+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · 4 internal anchors

[1]

A pa- rameterized algorithm for vertex connectivity survivable network design problem with uniform demands

Jørgen Bang-Jensen, Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh. A pa- rameterized algorithm for vertex connectivity survivable network design problem with uniform demands. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, ed- itors,31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, ...

work page doi:10.4230/lipics.esa.2023.13 2023
[2]

Fomin, Petr A

Matthias Bentert, P˚ al Grøn˚ as 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, Lan- guages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages ...

work page doi:10.4230/lipics.icalp.2024.22 2024
[3]

Fomin, Fanny Hauser, and Saket Saurabh

Matthias Bentert, Fedor V. Fomin, Fanny Hauser, and Saket Saurabh. The parameterized com- plexity landscape of two-sets cut-uncut. In ´Edouard Bonnet and Pawel Rzazewski, editors, 19th International Symposium on Parameterized and Exact Computation, IPEC 2024, Septem- ber 4-6, 2024, Royal Holloway, University of London, Egham, United Kingdom, volume 321 of...

work page doi:10.4230/lipics.ipec.2024.14 2024
[4]

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

work page doi:10.1142/s0129054100000211 2000
[5]

Multicut is FPT.SIAM J

Nicolas Bousquet, Jean Daligault, and St´ ephan Thomass´ e. Multicut is FPT.SIAM J. Comput., 47(1):166–207, 2018.doi:10.1137/140961808

work page doi:10.1137/140961808 2018
[6]

A fixed-parameter algorithm for the directed feedback vertex set problem.J

Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem.J. ACM, 55(5):21:1–21:19, 2008. doi:10.1145/1411509.1411511

work page doi:10.1145/1411509.1411511 2008
[7]

[AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor

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

work page doi:10.1109/focs54457.2022.00064 2022
[8]

Designing FPT algorithms for cut problems using randomized contractions

Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. CoRR, abs/1207.4079, 2012. URL:http://arxiv.org/abs/1207.4079,arXiv:1207.4079

work page internal anchor Pith review Pith/arXiv arXiv 2012
[9]

Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset.SIAM J

Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and D´ aniel Marx. Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset.SIAM J. Comput., 42(4):1674–1696, 2013.doi:10.1137/12086217X

work page doi:10.1137/12086217x 2013
[10]

Corneil, Stephan Olariu, and Lorna Stewart

Derek G. Corneil, Stephan Olariu, and Lorna Stewart. Asteroidal triple-free graphs.SIAM J. Discret. Math., 10(3):399–430, 1997.doi:10.1137/S0895480193250125. 22

work page doi:10.1137/s0895480193250125 1997
[11]

Kevin Wood, and Alexandra M

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

work page doi:10.1002/net.21514 2013
[12]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

work page 2015
[13]

Springer, 2012

Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics. Springer, 2012

work page 2012
[14]

Yefim A. Dinitz. Algorithm for solution of a problem of maximum flow in a network with power estimation.Soviet Mathematics Doklady, 11(5):1277–1280, 1970. Original blocking-flow / level graph algorithm for exact max-flow; worst-case timeO(n 2m) in general graphs

work page 1970
[15]

On DDoS Attack Related Minimum Cut Problems

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

work page internal anchor Pith review Pith/arXiv arXiv 2014
[16]

On the connectivity preserving minimum cut problem.J

Qi Duan and Jinhui Xu. On the connectivity preserving minimum cut problem.J. Com- put. 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

work page doi:10.1016/j.jcss.2014.01.003 2014
[17]

Cambridge University Press, 2012

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

work page 2012
[18]

2019.09.018,doi:10.1016/J.TCS.2019.09.018

Petr A. Golovach, Dieter Kratsch, and Dani¨ el 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

work page doi:10.1016/j.tcs 2013
[19]

Silveira

Chris Gray, Frank Kammer, Maarten L¨ offler, and Rodrigo I. Silveira. Removing 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

work page doi:10.1016/j.comgeo.2012.02.002 2012
[20]

The induced disjoint paths problem

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

work page 2008
[21]

Connectivity-preserving minimum separator in at-free graphs, 2025

Batya Kenig. Connectivity-preserving minimum separator in at-free graphs, 2025. URL: https://arxiv.org/abs/2506.03612,arXiv:2506.03612

work page arXiv 2025
[22]

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

Walter Kern, Barnaby Martin, Dani¨ el Paulusma, Siani Smith, and Erik Jan van Leeuwen. Disjoint paths and connected subgraphs for H-free graphs.Theoretical Computer Sci- ence, 898:59–68, 2022. URL:https://www.sciencedirect.com/science/article/pii/ S0304397521006344,doi:10.1016/j.tcs.2021.10.019

work page doi:10.1016/j.tcs.2021.10.019 2022
[23]

Listing all minimal separators of a graph.SIAM J

Ton Kloks and Dieter Kratsch. Listing all minimal separators of a graph.SIAM J. Comput., 27(3):605–613, 1998.doi:10.1137/S009753979427087X

work page doi:10.1137/s009753979427087x 1998
[24]

Clustering with local restrictions.Inf

Daniel Lokshtanov and D´ aniel Marx. Clustering with local restrictions.Inf. Comput., 222:278– 292, 2013. URL:https://doi.org/10.1016/j.ic.2012.10.016,doi:10.1016/J.IC.2012. 10.016. 23

work page doi:10.1016/j.ic.2012.10.016 2013
[25]

Slightly superexponential parameterized problems.SIAM Journal on Computing, 47(3):675–702, 2018.arXiv:https://doi.org/10

Daniel Lokshtanov, D´ aniel Marx, and Saket Saurabh. Slightly superexponential parameterized problems.SIAM Journal on Computing, 47(3):675–702, 2018.arXiv:https://doi.org/10. 1137/16M1104834,doi:10.1137/16M1104834

work page doi:10.1137/16m1104834 2018
[26]

Parameterized graph separation problems.Theor

D´ aniel Marx. Parameterized graph separation problems.Theor. Comput. Sci., 351(3):394–406,

work page
[27]

URL:https://doi.org/10.1016/j.tcs.2005.10.007,doi:10.1016/J.TCS.2005. 10.007

work page doi:10.1016/j.tcs.2005.10.007 2005
[28]

Treewidth reduction for constrained separation and bipartization problems

D´ aniel Marx, Barry O’Sullivan, and Igor Razgon. Treewidth reduction for constrained separation and bipartization problems. InSTACS 2010: 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 ofLeibniz International Proceed- ings in Informatics (LIPIcs), pages 561–572. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Infor- matik, 2010....

work page doi:10.4230/lipics.stacs.2010.2485 2010
[29]

Finding small separators in linear time via treewidth reduction.ACM Trans

D´ aniel Marx, Barry O’Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction.ACM Trans. Algorithms, 9(4):30:1–30:35, 2013.doi:10.1145/2500119

work page doi:10.1145/2500119 2013
[30]

Fixed-parameter tractability of multicut parameterized by the size of the cutset.SIAM J

D´ aniel Marx and Igor Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset.SIAM J. Comput., 43(2):355–388, 2014.doi:10.1137/110855247

work page doi:10.1137/110855247 2014
[31]

Dani¨ el Paulusma and Johan M. M. van Rooij. On partitioning a graph into two con- nected 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

work page doi:10.1016/j.tcs.2011.09.001 2011
[32]

Large Isolating Cuts Shrink the Multiway Cut

Igor Razgon. Large isolating cuts shrink the multiway cut.CoRR, abs/1104.5361, 2011. URL: http://arxiv.org/abs/1104.5361,arXiv:1104.5361

work page internal anchor Pith review Pith/arXiv arXiv 2011
[33]

Almost 2-SAT is Fixed-Parameter Tractable

Igor Razgon and Barry O’Sullivan. Almost 2-sat is fixed-parameter tractable.CoRR, abs/0801.1300, 2008. URL:http://arxiv.org/abs/0801.1300,arXiv:0801.1300

work page internal anchor Pith review Pith/arXiv arXiv 2008
[34]

Connecting terminals and 2-disjoint connected subgraphs

Jan Arne Telle and Yngve Villanger. Connecting terminals and 2-disjoint connected subgraphs. In Andreas Brandst¨ adt, Klaus Jansen, and R¨ udiger Reischuk, editors,Graph-Theoretic Con- cepts in Computer Science - 39th International Workshop, WG 2013, L¨ ubeck, Germany, June 19-21, 2013, Revised Papers, volume 8165 ofLecture Notes in Computer Science, pages 418–

work page 2013
[35]

Springer, 2013.doi:10.1007/978-3-642-45043-3\_36

work page doi:10.1007/978-3-642-45043-3 2013
[36]

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

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algo- rithm for minimum-cost flow.CoRR, abs/2309.16629, 2023. URL:https://doi.org/10. 48550/arXiv.2309.16629,arXiv:2309.16629,doi:10.48550/ARXIV.2309.16629. 24 APPENDIX A Proofs from Secti...

work page doi:10.48550/arxiv.2309.16629 2023
[37]

For allS∈ S s,t(G′) such thatS⊆T ′ ∪C s(G′−T ′) it holds thatS∈ S s,t(G)

work page
[38]

3.κ s,t(G′) =κ s,t(G)

For allS∈ S s,t(G′) such thatS⊆T ′ ∪C t(G′−T ′), it holds that|S| ≥ |T ′|. 3.κ s,t(G′) =κ s,t(G). 28 Proof.We first prove item 1. SinceT∈ S sD,t(G), then by Lemma A.1, it holds thatT= NG(Ct(G−T)). We claim thatT ′ ∈ S s,t(G). SinceT ′ def =N G(Cs(G−T)), then clearly it is an s, t-separator inG. SinceT ′ ⊆T=N G(Ct(G−T)), thenT ′\{w}no longer separatessfrom...

work page
[39]

SinceC s(G−L∗ sAQ,t(G))⊆C s(G−S), then Ai ⊆ S C∈D C∪C s(G−L∗ sAQ,t(G))⊆C s(G−S), and henceA i is connected inG −S

Otherwise,A i ⊆ S C∈D C∪C s(G−L∗ sAQ,t(G)). SinceC s(G−L∗ sAQ,t(G))⊆C s(G−S), then Ai ⊆ S C∈D C∪C s(G−L∗ sAQ,t(G))⊆C s(G−S), and henceA i is connected inG −S. Now, letq∈Q. We show, by case analysis, thatqis connected tosAinG −S. For brevity, we denoteC q def =C q(G−L∗ sAQ,t(G))

work page
[40]

Ifs∈C q, then sinceC s(G−L∗ sAQ,t(G)) =C q ⊆C s(G−S), thenqis connected tosAinG −S

work page
[41]

IfC q ∈ D, then by assumptionC q ⊆C s(G−S), and henceqis connected tosAinG −S

work page
[42]

We have previously established thatC q is connected inG −S

Suppose thatC q /∈ D ∪ {Cs(G−L∗ sAQ,t(G))}. We have previously established thatC q is connected inG −S. SinceC q /∈ D, thenCq ∩sA̸=∅, and sinceC q is connected inG −S, then qis connected tosAinG −S. This proves thatS∈ L sAQ,t(G) whereS|=R, or thatS∈ F sAQ,t,min(G). Lemma4.3. LetS∈ L s,t(G), and letD∈ C(G −S) wheres /∈Dandt /∈D. DefineT D def =N G(D). For ...

work page
[43]

Ifx∈L ∗ sA,t(G) thenκ sA,tx(G)> κ sA,t(G)

work page
[44]

Ifx∈L t sA,t(G) thenκ sAx,t(G)> κ sA,t(G)

LetL t sA,t(G)∈ L sA,t(G) that is closest tot. Ifx∈L t sA,t(G) thenκ sAx,t(G)> κ sA,t(G). Proof.By Lemma 3.3, it holds thatS sA,t(G) =S s,t(H) whereHis the graph that results fromG by adding all edges betweensandN G[A]. In particular,κ sA,t(G) =κ s,t(H),L ∗ sA,t(G) =L ∗ s,t(H), andL t sA,t(G) =L t s,t(H). LetT∈ L sA,tx(G), and henceT∈ L s,tx(H). By defini...

work page