Β§6, p. 354 β Schrijver's ring-family reduction: g of (26) is submodular (27), and minimizing g β c over 2^V yields a minimizer of f over π
ProvedSchrijverSFM.Ring.ring_family_reductionLet be a finite set and a ring family of subsets of , i.e. closed under union and intersection, normalized as in the paper so that , , and for all , where is the smallest set of containing . Let be submodular on :
For let be the largest set of not containing , let
as in (23), and . For let be the smallest set of containing and as in (26). Then:
- is submodular on all subsets of : for all (display (27));
- if minimizes over all subsets of , then and
that is, minimizes over .
Together these say that any algorithm minimizing submodular functions on all subsets of also minimizes a submodular function given only on a ring family: run it on the submodular function and take the closure of its output.
Formalization Note is a function on all of Finset V, but its values outside never enter , or the conclusion under the hypotheses. The hypotheses , and are the paper's normalization ("We can assume that , , and for all "); without the set in (23) may lie outside and the statement can fail. The paper allows any ordered field; we use . The running-time claims of Β§6 (computing with oracle calls, strongly polynomial time) are not formalized.
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Ring_Setting
namespace SchrijverSFM.Ring
theorem ring_family_reduction {V : Type} [Fintype V] [DecidableEq V]
(C : Set (Finset V)) (hC : IsRingFamily C) (hempty : β
β C) (huniv : Finset.univ β C)
(hM : β u v : V, u β v β M C u β M C v) (f : Finset V β β) (hf : SubmodularOn C f) :
NonmonotoneSubmod.Shared.Submodular (g C f) β§
β U : Finset V, (β W : Finset V, g C f U - csum C f U β€ g C f W - csum C f W) β
closure C U β C β§ β T β C, f (closure C U) β€ f T := by sorry
end SchrijverSFM.Ring
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.