Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite directed layouts, the directed spreading LP, oriented volumes, operational Algorithm 3 and the register gadget

Definition
GreedyRegionGrowing_Layouts_Supplement_Directed

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-algorithmsoptimizationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Finite directed layouts, the directed spreading LP, oriented volumes, operational Algorithm 3 and the register gadget. Graphs are finite relations on labelled vertices. Acyclicity excludes closed nonempty paths. Storage counts crossing arcs; registers count processed vertices with a successor outside. Minima range over every topological ordering. Rational quasi-metrics satisfy every constraint of (6.1), without symmetry. Directed volumes use the outgoing or incoming partial arc terms selected by a fixed sign. Run predicates specify maximizing centers, event-free minimizing radii and residual transitions, without assuming completion, radius or accounting bounds. The input/output codes extend the published binary graph, rational, list and set codecs. The gadget is the concrete two-copy graph with unit and epsilon arcs of Appendix B. These objects support the directed companion results.

Definition code
import Mathlib
import Definitions.Def_GreedyRegionGrowing_Layouts_Foundation

noncomputable section
open Finset QAlgorithms.Complexity

namespace GreedyRegionGrowing.Layouts.Supplement
attribute [local instance] Classical.propDecidable

/-- Finite simple directed graphs (§3): a relation, with acyclicity imposed separately. -/
abbrev ArcGraph (n : ℕ) := Fin n → Fin n → Prop

def Acyclic {n : ℕ} (G : ArcGraph n) : Prop :=
  (∀ v, ¬ G v v) ∧ ∀ v, ¬ Relation.TransGen G v v

def arcs {n : ℕ} (G : ArcGraph n) (U : Finset (Fin n)) :=
  (U ×ˢ U).filter (fun e => G e.1 e.2)

def arcCut {n : ℕ} (G : ArcGraph n) (U S : Finset (Fin n)) :=
  (arcs G U).filter (fun e => (e.1 ∈ S ∧ e.2 ∉ S) ∨ (e.2 ∈ S ∧ e.1 ∉ S))

def Topological {n : ℕ} (G : ArcGraph n) (U : Finset (Fin n)) (p : List (Fin n)) : Prop :=
  IsOrdering U p ∧ ∀ e ∈ arcs G U, p.idxOf e.1 < p.idxOf e.2

def storage {n : ℕ} (G : ArcGraph n) (p : List (Fin n)) : ℕ :=
  (range (p.length + 1)).sup (fun i => (arcCut G univ (orderingPrefix p i)).card)

def registers {n : ℕ} (G : ArcGraph n) (p : List (Fin n)) : ℕ :=
  (range (p.length + 1)).sup (fun i =>
    ((orderingPrefix p i).filter (fun u => ∃ v, G u v ∧ v ∉ orderingPrefix p i)).card)

def MS {n : ℕ} (G : ArcGraph n) : ℕ :=
  sInf {k | ∃ p, Topological G univ p ∧ storage G p = k}

def MRS {n : ℕ} (G : ArcGraph n) : ℕ :=
  sInf {k | ∃ p, Topological G univ p ∧ registers G p = k}

def weightedStorage {n : ℕ} (G : ArcGraph n) (w : Fin n → Fin n → ℚ)
    (p : List (Fin n)) : ℚ :=
  ((List.range (p.length + 1)).map (fun i =>
    ∑ e ∈ arcCut G univ (orderingPrefix p i), w e.1 e.2)).foldl max 0

def WMS {n : ℕ} (G : ArcGraph n) (w : Fin n → Fin n → ℚ) : ℝ :=
  sInf {r | ∃ p, Topological G univ p ∧ r = (weightedStorage G w p : ℝ)}

def dagCode {n : ℕ} (G : ArcGraph n) : Str :=
  List.replicate n true ++ [false] ++
    (List.finRange n).flatMap (fun u => (List.finRange n).map (fun v => decide (G u v)))

def matrixCode {n : ℕ} (d : Fin n → Fin n → ℚ) : Str :=
  (List.finRange n).flatMap (fun u => (List.finRange n).flatMap (fun v => ratCode (d u v)))

def weightedDagCode {n : ℕ} (G : ArcGraph n) (w : Fin n → Fin n → ℚ) : Str :=
  dagCode G ++ (List.finRange n).flatMap (fun u => ((List.finRange n).filter (fun v => decide (G u v))).flatMap (fun v => ratCode (w u v)))

/-- All constraints of (6.1), including the signed empty-set right side. -/
def DirectedFeasible {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ) : Prop :=
  (∀ x y, 0 ≤ d x y) ∧ (∀ x, d x x = 0) ∧
  (∀ x y z, d x z ≤ d x y + d y z) ∧
  (∀ x y, G x y → d y x = 0) ∧
  ∀ u (S : Finset (Fin n)), ((S.card : ℚ)^2 - 1)/4 ≤ ∑ v ∈ S, (d u v + d v u)

def directedObjective {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ) : ℚ :=
  ∑ e ∈ arcs G univ, d e.1 e.2

def DirectedOptimal {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ) : Prop :=
  DirectedFeasible G d ∧ ∀ d', DirectedFeasible G d' →
    directedObjective G d ≤ directedObjective G d'

def DLP {n : ℕ} (G : ArcGraph n) : ℝ :=
  sInf {r | ∃ d, DirectedFeasible G d ∧ r = (directedObjective G d : ℝ)}

def WeakConnected {n : ℕ} (G : ArcGraph n) : Prop :=
  ∀ u v, Relation.ReflTransGen (fun x y => G x y ∨ G y x) u v

def orientedDistance {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
    (u v : Fin n) : ℚ := if s u then d u v else d v u

def orientedBall {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
    (U : Finset (Fin n)) (u : Fin n) (r : ℝ) :=
  if r ≤ 0 then ∅ else U.filter (fun v => (orientedDistance d s u v : ℝ) < r)

def SmallSigns {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool) : Prop :=
  ∀ u, ((orientedBall d s univ u ((n : ℝ)/20)).card : ℝ) ≤ 3*(n : ℝ)/4

def directedSetVolume {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (S : Finset (Fin n)) : ℚ :=
  directedObjective G d * S.card / n + ∑ e ∈ arcs G S, d e.1 e.2

def directedVolume {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (s : Fin n → Bool) (U : Finset (Fin n)) (u : Fin n) (r : ℝ) : ℝ :=
  if r ≤ 0 then 0 else
  let B := orientedBall d s U u r
  (directedSetVolume G d B : ℝ) +
    ∑ e ∈ (arcs G U).filter (fun e => if s u then e.1 ∈ B ∧ e.2 ∉ B
      else e.1 ∉ B ∧ e.2 ∈ B),
      (if s u then r - (d u e.1 : ℝ) else r - (d e.2 u : ℝ))

def directedVolumeQ {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (s : Fin n → Bool) (U : Finset (Fin n)) (u : Fin n) (r : ℚ) : ℚ :=
  if r ≤ 0 then 0 else
  let B := orientedBall d s U u (r : ℝ)
  directedSetVolume G d B +
    ∑ e ∈ (arcs G U).filter (fun e => if s u then e.1 ∈ B ∧ e.2 ∉ B
      else e.1 ∉ B ∧ e.2 ∈ B),
      (if s u then r - d u e.1 else r - d e.2 u)

def directedEvents {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
    (U : Finset (Fin n)) (u : Fin n) : Finset ℚ := U.image (orientedDistance d s u)

/-- Algorithm 3, operational frame. No performance property is a field. -/
structure DirectedFrame (n : ℕ) where
  U : Finset (Fin n)
  rho : ℚ
  center : Fin n
  radius : ℚ

namespace DirectedFrame
variable {n : ℕ}
def K (f : DirectedFrame n) (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (s : Fin n → Bool) : ℚ :=
  ((f.U.sort (· ≤ ·)).map (fun u => directedVolumeQ G d s f.U u f.rho)).foldl max 0

def w (f : DirectedFrame n) (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (s : Fin n → Bool) : ℚ := n * f.K G d s / (320 * directedObjective G d)

def X (f : DirectedFrame n) (d : Fin n → Fin n → ℚ) (s : Fin n → Bool) :=
  orientedBall d s f.U f.center (f.radius : ℝ)

def W (f : DirectedFrame n) (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (s : Fin n → Bool) := directedVolume G d s f.U f.center (f.radius : ℝ)

def nextU (f : DirectedFrame n) (d : Fin n → Fin n → ℚ) (s : Fin n → Bool) :=
  f.U \ f.X d s

def Operational (f : DirectedFrame n) (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (s : Fin n → Bool) : Prop :=
  f.center ∈ f.U ∧
  (let a := f.rho - f.w G d s
   let E := directedEvents d s f.U f.center
   (∀ u ∈ f.U, directedVolumeQ G d s f.U u a ≤ directedVolumeQ G d s f.U f.center a) ∧
   a < f.radius ∧ f.radius < f.rho ∧ f.radius ∉ E ∧
   ∀ r : ℚ, a < r → r < f.rho → r ∉ E →
     (arcCut G f.U (f.X d s)).card ≤
       (arcCut G f.U (orientedBall d s f.U f.center (r : ℝ))).card)
end DirectedFrame

def DirectedRunFrom {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (s : Fin n → Bool) : Finset (Fin n) → ℚ → List (DirectedFrame n) → Prop
  | _, _, [] => True
  | U, rho, f::fs => f.U = U ∧ f.rho = rho ∧ f.Operational G d s ∧
      DirectedRunFrom G d s (f.nextU d s) (rho-f.w G d s) fs

def DirectedRun {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ)
    (s : Fin n → Bool) (fs : List (DirectedFrame n)) := DirectedRunFrom G d s univ (n/20) fs

def DirectedComplete {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
    (fs : List (DirectedFrame n)) : Prop :=
  match fs.getLast? with
  | none => n = 0
  | some f => f.nextU d s = ∅

def directedFrameCode {n : ℕ} (f : DirectedFrame n) : Str :=
  setCode f.U ++ ratCode f.rho ++ natCode f.center.val ++ ratCode f.radius

structure DirectedInput where
  n : ℕ
  G : ArcGraph n
  d : Fin n → Fin n → ℚ
  s : Fin n → Bool
  dag : Acyclic G
  connected : WeakConnected G
  size : 2 ≤ n
  optimal : DirectedOptimal G d
  signs : SmallSigns d s

def directedInputCode (I : DirectedInput) : Str :=
  dagCode I.G ++ matrixCode I.d ++ (List.finRange I.n).map I.s

def DirectedCarvingPolyTime : Prop :=
  ∃ F : (I : DirectedInput) → List (DirectedFrame I.n),
    PPSLattice.PolyTimeOn directedInputCode (fun I => listCode directedFrameCode (F I)) ∧
    ∀ I, DirectedRun I.G I.d I.s (F I) ∧ DirectedComplete I.d I.s (F I)

def twoEnded {n : ℕ} (s : Fin n → Bool) (fs : List (DirectedFrame n)) : List (DirectedFrame n) :=
  fs.filter (fun f => s f.center) ++ (fs.filter (fun f => !(s f.center))).reverse

/-- Any ordering by contiguous blocks in the required order. -/
def BlockOrdering {n : ℕ} (d : Fin n → Fin n → ℚ) (s : Fin n → Bool)
    (fs : List (DirectedFrame n)) (p : List (Fin n)) : Prop :=
  IsOrdering univ p ∧ ∃ blocks : List (List (Fin n)),
    blocks.length = fs.length ∧ blocks.flatten = p ∧
    ∀ i : Fin fs.length, IsOrdering ((fs.get i).X d s) (blocks[i.val]!)

/-- The concrete gadget of Appendix B; minus copies have tag false, plus copies true. -/
def gadget {n : ℕ} (G : ArcGraph n) : ArcGraph (2*n) := fun x y =>
  (∃ v : Fin n, x.val = v.val ∧ y.val = n+v.val) ∨
  (∃ u v : Fin n, G u v ∧ x.val = u.val ∧ y.val = v.val) ∨
  (∃ u v : Fin n, G u v ∧ x.val = v.val ∧ y.val = n+u.val)

def gadgetWeight {n : ℕ} (G : ArcGraph n) (x y : Fin (2*n)) : ℚ :=
  if ∃ v : Fin n, x.val = v.val ∧ y.val = n+v.val then 1
  else 1 / (10 * (arcs G univ).card)

def restrictMinus {n : ℕ} (p : List (Fin (2*n))) : List (Fin n) :=
  p.filterMap (fun x => if h : x.val < n then some ⟨x.val,h⟩ else none)

end GreedyRegionGrowing.Layouts.Supplement
Source
Aditya Anand, Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More, STOC 2027 submission #506 (October 2026). Citation basis: published (canonical held submission); 46 pages; printed page = PDF page throughout (offset 0); no arXiv version. §3.1–3.3 pp.17–19; §6 pp.29–33, Eq. (6.1), Algorithm 3; Appendix B p.42; Appendix D.1–D.2 pp.43–44

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me