Theorem 5.2 — the Assignable Subgraph Polytope of a digraph
ProvedDisjunctive.ExtendedFormulations.assignable_subgraph_polytopeThis is Theorem 5.2 of Balas's Disjunctive Programming, the digraph analogue of Theorem 5.1: the Assignment Problem's natural extension to subsets that admit a cycle decomposition.
For a digraph , the Assignable Subgraph Polytope (the convex hull of incidence vectors of vertex sets such that admits a cycle decomposition) is defined by
where is the out-neighborhood of . As with Theorem 5.1, projection is used to prove this fractional system already describes an integral polytope, without needing to verify a totally-unimodular lift by hand for every instance.
Formalization Note. A : V → V → Prop is a general digraph relation (not required
irreflexive or asymmetric, matching the book's unrestricted notion of a digraph); IsAssignable
uses Equiv.Perm on the subtype {v // v ∈ W}, since any permutation of a finite set decomposes
into disjoint cycles by definition.
import Mathlib import Definitions.Def_Disjunctive_ExtendedFormulations_Basic
namespace Disjunctive.ExtendedFormulations
/-- Theorem 5.2 (Balas §5.2.2, p. 75, [13]): the Assignable Subgraph Polytope of a digraph `G`
is defined by the system `0 ≤ x_i ≤ 1`, `x(S \ Γ(S)) − x(Γ(S) \ S) ≤ 0`, `S ⊆ V`. -/
theorem assignable_subgraph_polytope {V : Type*} [Fintype V] [DecidableEq V] (A : V → V → Prop)
[DecidableRel A] :
AssignableSubgraphPolytope A =
{x : V → ℝ | (∀ i, 0 ≤ x i ∧ x i ≤ 1) ∧
∀ S : Finset V, xSum x (S \ GammaOut A S) - xSum x (GammaOut A S \ S) ≤ 0} := by sorry
end Disjunctive.ExtendedFormulations
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.