Observation 5: a split-network cut yields a separator of no greater charge
ProvedDvorakNorin2018.split_cut_yields_separatorflowsgraph-theorytreewidth
Let be finite with sinks . In the split-vertex network with nonnegative vertex capacity and nonnegative large-arc capacity , suppose a source/sink cut has capacity at most . Then admits a separation into disjoint parts , with no edge from to , such that
This proves the cut-conversion step of the max-flow reduction in Observation 5. It does not yet assert extraction of a cloud from a network flow.
Preamble
import Definitions.Def_DvorakNorin2018_SplitNetwork set_option autoImplicit false open scoped Classical BigOperators
Formal statement
namespace DvorakNorin2018
open TreewidthApprox.Pushed StableMSR.Recovery.SplitNetwork
theorem split_cut_yields_separator {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Finset V) (α M s : ℝ) (hα : 0 ≤ α) (hM : 0 ≤ M)
(hMs : s < M) (C : Finset (Node V)) (hsource : source ∈ C) (hsink : sink ∉ C)
(hcut : cut G W α M C ≤ s) :
∃ L S R : Finset V, IsPartition3 Finset.univ L S R ∧ NoEdge G L R ∧
W ⊆ L ∪ S ∧ (L.card : ℝ) + α * S.card ≤ s := by sorry
end DvorakNorin2018
Source
Dvorak–Norin, Treewidth of graphs with balanced separations, https://arxiv.org/pdf/1408.3869v2, Section 2.2, network construction preceding Observation 5. The finite-capacity version uses M>s.