Observation 5, forward direction: cloud supply is bounded by separator charge
ProvedDvorakNorin2018.cloud_supply_le_separator_chargeflowsgraph-theorytreewidth
Let be a finite undirected graph, let be its designated sinks, and let and describe a -cloud. Flow is supported on graph edges, leaves no sink, and satisfies
Assume its congestion is at most , so at every vertex. For every separation into pairwise disjoint parts , with no edge between and and with , the total supply satisfies
Equivalently, a cloud with supply greater than excludes every separator whose sink-side charge is at most . This is the forward implication of Observation 5. The converse, constructing a cloud by max-flow/min-cut, is a separate result.
Preamble
import Definitions.Def_TreewidthApprox_Pushed_Setting set_option autoImplicit false open scoped Classical BigOperators
Formal statement
namespace DvorakNorin2018
open TreewidthApprox.Pushed
theorem cloud_supply_le_separator_charge {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Finset V) (supply : V → ℝ) (flow : V → V → ℝ) (α : ℝ)
(hsupply : ∀ v, 0 ≤ supply v ∧ supply v ≤ 1)
(hflow : ∀ u v, 0 ≤ flow u v)
(hsupport : ∀ u v, ¬ G.Adj u v → flow u v = 0)
(hsinks : ∀ u ∈ W, ∀ v, flow u v = 0)
(hcons : ∀ v ∉ W, supply v + ∑ u, flow u v = ∑ u, flow v u)
(hcongestion : ∀ v, supply v + ∑ u, flow u v ≤ α)
(L S R : Finset V) (hpart : IsPartition3 Finset.univ L S R)
(hno : NoEdge G L R) (hW : W ⊆ L ∪ S) :
(∑ v, supply v) ≤ (L.card : ℝ) + α * S.card := by sorry
end DvorakNorin2018
Source
Z. Dvorak and S. Norin, Treewidth of graphs with balanced separations, arXiv:1408.3869v2, https://arxiv.org/pdf/1408.3869v2, Section 2.2, Observation 5 (PDF pp. 4–5), forward implication. This is a foundation for the separator-to-treewidth step used by Ravichandran–Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Theorem 4.3 and Lemma 4.4.