Finite directed layouts, the directed spreading LP, oriented volumes, operational Algorithm 3 and the register gadget
DefinitionGreedyRegionGrowing_Layouts_Supplement_DirectedFinite 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.
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