Observation 5: bounded-congestion clouds and weighted separators
ProvedDvorakNorin2018.cloud_separator_equivalenceLet be a finite undirected graph, let be a designated set of sinks, and let . There exists a -cloud with vertex supplies in , congestion at most , and total supply greater than if and only if every separation into disjoint parts with no edge between and and satisfies
A cloud consists of nonnegative flows supported on graph edges, with no outgoing flow from sinks. Outside the sinks, incoming flow plus supply equals outgoing flow. Congestion is incoming flow plus supply at each vertex.
The theorem includes both implications, the finite-capacity split-network construction, application of max-flow/min-cut, and explicit decoding of the resulting network flow into the cloud. Nonnegative parameters include the source's strictly positive case. It is the full Observation 5 needed for the subsequent tame-cloud argument; it does not assert the later tameness or treewidth conclusions.
import Definitions.Def_TreewidthApprox_Pushed_Setting set_option autoImplicit false open scoped Classical BigOperators
namespace DvorakNorin2018
open TreewidthApprox.Pushed
theorem cloud_separator_equivalence {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Finset V) (α s : ℝ) (hα : 0 ≤ α) (hs : 0 ≤ s) :
(∃ (g : V → ℝ) (f : V → V → ℝ),
(∀ v, 0 ≤ g v ∧ g v ≤ 1) ∧ (∀ u v, 0 ≤ f u v) ∧
(∀ u v, ¬ G.Adj u v → f u v = 0) ∧ (∀ u ∈ W, ∀ v, f u v = 0) ∧
(∀ v ∉ W, g v + ∑ u, f u v = ∑ u, f v u) ∧
(∀ v, g v + ∑ u, f u v ≤ α) ∧ s < ∑ v, g v) ↔
∀ L S R : Finset V, IsPartition3 Finset.univ L S R → NoEdge G L R →
W ⊆ L ∪ S → s < (L.card : ℝ) + α * S.card := by sorry
end DvorakNorin2018