Finite split-vertex network for bounded-congestion clouds
DefinitionDvorakNorin2018_SplitNetworkflowsgraph-theorytreewidth
For a finite graph with sinks , split each vertex into an input and an output node, and add a source and a sink. Source-to-input capacities are ; input-to-output capacities are ; graph edges give output-to-input arcs of capacity unless their tail belongs to ; outputs of vertices in connect to the sink with capacity . Other capacities are zero. Cut capacity sums capacities from the cut to its complement. Finite is chosen above the supply threshold of interest.
Definition code
import Definitions.Def_TreewidthApprox_Pushed_Setting
import Mathlib.Data.Fintype.BigOperators
set_option autoImplicit false
open scoped Classical BigOperators
namespace StableMSR.Recovery.SplitNetwork
abbrev Node (V : Type) := Unit ⊕ (Unit ⊕ (V ⊕ V))
abbrev source {V : Type} : Node V := Sum.inl ()
abbrev sink {V : Type} : Node V := Sum.inr (Sum.inl ())
abbrev input {V : Type} (v : V) : Node V := Sum.inr (Sum.inr (Sum.inl v))
abbrev output {V : Type} (v : V) : Node V := Sum.inr (Sum.inr (Sum.inr v))
noncomputable def capacity {V : Type} [DecidableEq V] (G : SimpleGraph V)
(W : Finset V) (α M : ℝ) : Node V → Node V → ℝ
| .inl _, .inr (.inr (.inl _)) => 1
| .inr (.inr (.inl v)), .inr (.inr (.inr w)) => if v = w then α else 0
| .inr (.inr (.inr v)), .inr (.inr (.inl w)) => if G.Adj v w ∧ v ∉ W then M else 0
| .inr (.inr (.inr v)), .inr (.inl _) => if v ∈ W then M else 0
| _, _ => 0
noncomputable def row {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Finset V) (α M : ℝ) (C : Finset (Node V)) (x : Node V) : ℝ :=
if x ∈ C then ∑ y, if y ∉ C then capacity G W α M x y else 0 else 0
noncomputable def cut {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Finset V) (α M : ℝ) (C : Finset (Node V)) : ℝ :=
∑ x, row G W α M C x
end StableMSR.Recovery.SplitNetwork
Source
Dvorak and Norin, Treewidth of graphs with balanced separations, https://arxiv.org/pdf/1408.3869v2, Section 2.2, construction before Observation 5 (PDF p. 4). Finite M replaces infinite capacities for cuts below M.