Section 1, p. 70 — a minimum-weight cut-tree edge gives a minimum cut-set for all pairs of odd nodes
ProvedPadbergRao.OddCut.min_tree_edge_min_odd_pair_cutcombinatorial-optimizationgraph-theoryp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite undirected graph with edge weights , and let be a nonempty set of odd-labelled nodes with even. Let be a Gomory–Hu cut-tree of for the odd nodes, with edge weights . Let be an edge of minimum weight,
and let be the node set of corresponding to the subtree containing after is removed. Then is a minimum cut-set with respect to all pairs of odd nodes in .
The minimum is taken over all tree edges, with no parity condition. This is the bridge that lets Lemma 1.1 be applied to the cut-tree.
Formalization Note The cut-tree is IsOddCutTree c odd H π; is shore H π r s and is treeEdgeWeight. Minimality of is stated against every ordered adjacent pair r' s'.
Preamble
import Mathlib import Definitions.Def_PadbergRao_OddCut_cutCapacity import Definitions.Def_PadbergRao_OddCut_IsMinOddPairCut import Definitions.Def_PadbergRao_OddCut_IsOddCutTree
Formal statement
namespace PadbergRao.OddCut
/-- Section 1, p. 70 (Padberg–Rao 1982). Removing a minimum-weight edge `f* = [r, s]` of the
cut-tree `G_T` (minimum over all tree edges) yields a set `M` such that `(M : V − M)` is a
minimum cut-set with respect to all pairs of odd nodes of `G`. -/
theorem min_tree_edge_min_odd_pair_cut {V : Type*} [Fintype V] [DecidableEq V]
(c : V → V → ℝ) (hc_symm : ∀ i j, c i j = c j i) (hc_nonneg : ∀ i j, 0 ≤ c i j)
(odd : Finset V) (hodd_ne : odd.Nonempty) (hodd_even : Even odd.card)
(H : SimpleGraph {v // v ∈ odd}) (π : V → {v // v ∈ odd})
(hT : IsOddCutTree c odd H π)
(r s : {v // v ∈ odd}) (hrs : H.Adj r s)
(hmin : ∀ r' s' : {v // v ∈ odd}, H.Adj r' s' →
treeEdgeWeight c H π r s ≤ treeEdgeWeight c H π r' s') :
IsMinOddPairCut c odd (shore H π r s) := by sorry
end PadbergRao.OddCut
Source
Padberg, Rao, Odd Minimum Cut-Sets and b-Matchings, Math. Oper. Res. 7 (1982), p. 70, Section 1 (unnumbered claim before Theorem 1.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.