Lemma 6.9 — Two-ended prefix accounting
OpenGreedyRegionGrowing.Layouts.Supplement.lemma_6_9combinatoricsgraph-algorithmsoptimizationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Under the Section 6.2 assumptions, take a complete run of Algorithm 3 and any vertex ordering listing its pieces as contiguous blocks in the two-ended order. Let P be a nonempty prefix whose last vertex lies in X_i. Every crossing arc that is not internal to G[X_i] belongs to the boundary of some piece X_j with removal index j≤i, and the cardinality bound below also holds. Internal block order need not be topological.
This is a supporting result for Theorem 6.1.
Differences from the source:
- encoding: finite labelled graphs, ordered iterations and polynomial-time algorithms → Fin n carriers, zero-based trace indices, fixed binary codes and deterministic TM2 polynomial time; reason: labels and iteration shifts change no source instance; the codes include all vertices and rational data, and the machine condition records the full runtime claim
Preamble
import Mathlib import Definitions.Def_GreedyRegionGrowing_Layouts_Foundation noncomputable section open Finset QAlgorithms.Complexity
Formal statement
namespace GreedyRegionGrowing.Layouts.Supplement
attribute [local instance] Classical.propDecidable
/-- Finite simple directed graphs (§3): a relation, with acyclicity imposed separately. -/
private abbrev ArcGraph (n : ℕ) := Fin n → Fin n → Prop
private def Acyclic {n : ℕ} (G : ArcGraph n) : Prop :=
(∀ v, ¬ G v v) ∧ ∀ v, ¬ Relation.TransGen G v v
private def arcs {n : ℕ} (G : ArcGraph n) (U : Finset (Fin n)) :=
(U ×ˢ U).filter (fun e => G e.1 e.2)
private 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))
private 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
private def storage {n : ℕ} (G : ArcGraph n) (p : List (Fin n)) : ℕ :=
(range (p.length + 1)).sup (fun i => (arcCut G univ (orderingPrefix p i)).card)
private 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)
private def MS {n : ℕ} (G : ArcGraph n) : ℕ :=
sInf {k | ∃ p, Topological G univ p ∧ storage G p = k}
private def MRS {n : ℕ} (G : ArcGraph n) : ℕ :=
sInf {k | ∃ p, Topological G univ p ∧ registers G p = k}
private 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
private def WMS {n : ℕ} (G : ArcGraph n) (w : Fin n → Fin n → ℚ) : ℝ :=
sInf {r | ∃ p, Topological G univ p ∧ r = (weightedStorage G w p : ℝ)}
private 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)))
private 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)))
private 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. -/
private 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)
private def directedObjective {n : ℕ} (G : ArcGraph n) (d : Fin n → Fin n → ℚ) : ℚ :=
∑ e ∈ arcs G univ, d e.1 e.2
private 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'
private def DLP {n : ℕ} (G : ArcGraph n) : ℝ :=
sInf {r | ∃ d, DirectedFeasible G d ∧ r = (directedObjective G d : ℝ)}
private def WeakConnected {n : ℕ} (G : ArcGraph n) : Prop :=
∀ u v, Relation.ReflTransGen (fun x y => G x y ∨ G y x) u v
private 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
private 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)
private 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
private 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
private 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 : ℝ))
private 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)
private 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. -/
private structure DirectedFrame (n : ℕ) where
U : Finset (Fin n)
rho : ℚ
center : Fin n
radius : ℚ
namespace DirectedFrame
variable {n : ℕ}
private 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
private 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)
private def X (f : DirectedFrame n) (d : Fin n → Fin n → ℚ) (s : Fin n → Bool) :=
orientedBall d s f.U f.center (f.radius : ℝ)
private 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 : ℝ)
private def nextU (f : DirectedFrame n) (d : Fin n → Fin n → ℚ) (s : Fin n → Bool) :=
f.U \ f.X d s
private 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
private 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
private 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
private 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 = ∅
private def directedFrameCode {n : ℕ} (f : DirectedFrame n) : Str :=
setCode f.U ++ ratCode f.rho ++ natCode f.center.val ++ ratCode f.radius
private 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
private def directedInputCode (I : DirectedInput) : Str :=
dagCode I.G ++ matrixCode I.d ++ (List.finRange I.n).map I.s
private 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)
private 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. -/
private 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. -/
private 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)
private 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)
private 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)
/-- Aditya Anand, STOC 2027 submission #506 (October 2026), lemma 6 9. -/
theorem lemma_6_9 (I : DirectedInput) (fs : List (DirectedFrame I.n))
(hr : DirectedRun I.G I.d I.s fs) (hc : DirectedComplete I.d I.s fs)
(p : List (Fin I.n)) (hp : BlockOrdering I.d I.s (twoEnded I.s fs) p)
(i : Fin fs.length) (k : ℕ) (hk : 0 < k ∧ k ≤ p.length)
(hlast : ∃ v, (p.take k).getLast? = some v ∧ v ∈ (fs.get i).X I.d I.s) :
(∀ e ∈ arcCut I.G univ (orderingPrefix p k), e ∉ arcs I.G ((fs.get i).X I.d I.s) →
∃ j : Fin fs.length, j ≤ i ∧ e ∈ arcCut I.G univ ((fs.get j).X I.d I.s)) ∧
(((arcCut I.G univ (orderingPrefix p k)) \ arcs I.G ((fs.get i).X I.d I.s)).card : ℕ) ≤
((fs.take (i.val+1)).map (fun f => (arcCut I.G univ (f.X I.d I.s)).card)).sum := by sorry
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. Lemma 6.9, p. 33 (PDF p. 33).