AFTD Auto-Formalizing Theoretical Domains

online_cycle_augmentation_reduction_to_tl_hitting_set

theoremverifiedformalization

Let n be a natural number, L a finite set of pairs (i, j) of integers satisfying 0 ≤ i < j < n, w a real cost function on pairs, and α a real number. If an online algorithm Alg maintaining subsets of L irrevocably (Alg reqs ⊆ L and Alg reqs ⊆ Alg (reqs ++ [r])) is feasible and α-competitive for hitting arriving TL-rectangles ((p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2)) for all valid cut sequences (1 ≤ c.1 ≤ c.2 < n), then Alg is also feasible and α-competitive for covering all arriving cuts ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2)) in Online Cycle Augmentation.

Statement

open Finset BigOperators in
theorem online_cycle_augmentation_reduction_to_tl_hitting_set (n : ℕ) (L : Finset (ℤ × ℤ))
    (hL : ∀ p ∈ L, 0 ≤ p.1 ∧ p.1 < p.2 ∧ p.2 < (n : ℤ))
    (w : (ℤ × ℤ) → ℝ) (α : ℝ)
    (Alg : List (ℤ × ℤ) → Finset (ℤ × ℤ))
    (h_online : (∀ reqs, Alg reqs ⊆ L) ∧ (∀ reqs r, Alg reqs ⊆ Alg (reqs ++ [r])))
    (h_tl_hit : ∀ reqs, (∀ c ∈ reqs, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) →
      ∀ c ∈ reqs, ∃ p ∈ Alg reqs,
        (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2))
    (h_tl_comp : ∀ reqs, (∀ c ∈ reqs, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) →
      ∀ F ⊆ L, (∀ c ∈ reqs, ∃ p ∈ F,
        (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2)) →
        ∑ p ∈ Alg reqs, w p ≤ α * ∑ p ∈ F, w p) :
    ((∀ cuts, (∀ c ∈ cuts, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) →
      ∀ c ∈ cuts, ∃ p ∈ Alg cuts,
        ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2))) ∧
    ∀ cuts, (∀ c ∈ cuts, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) →
      ∀ F ⊆ L, (∀ c ∈ cuts, ∃ p ∈ F,
        ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2))) →
        ∑ p ∈ Alg cuts, w p ≤ α * ∑ p ∈ F, w p)
Formalizes
arXiv:2611.08570 Theorem 1.10
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • cycle_link_crosses_cut_iff_tl_rectFor integers i, j, a, b, n satisfying 0 ≤ i < j < n and 1 ≤ a ≤ b < n, candidate link (i, j) crosses cycle cut [a, b] (meaning (a ≤ i ∧ i…
  • card_candidate_links_le_sqFor every natural number n and every finite set L of pairs of integers (i, j) satisfying 0 ≤ i < j < n, the cardinality of L is at most n…

Read back from the Lean

Given: - a natural number n, - a finite set of integer pairs L : Finset (ℤ × ℤ) such that for every p ∈ L, 0 ≤ p.1 < p.2 < n, - a weight function w : (ℤ × ℤ) → ℝ, - a real number α, - an algorithm Alg : List (ℤ × ℤ) → Finset (ℤ × ℤ), - a hypothesis h_online asserting that for every list reqs, Alg reqs ⊆ L, and for every list reqs and pair r, Alg reqs ⊆ Alg (reqs ++ [r]), - a hypothesis h_tl_hit asserting that for every list reqs of integer pairs, if every c ∈ reqs satisfies 1 ≤ c.1 ≤ c.2 < n, then for every c ∈ reqs, there exists p ∈ Alg reqs such that either (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) or (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2), - a hypothesis h_tl_comp asserting that for every list reqs where every c ∈ reqs satisfies 1 ≤ c.1 ≤ c.2 < n, and for every sub-finset F ⊆ L, if for every c ∈ reqs there exists p ∈ F satisfying (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2), then ∑ p ∈ Alg reqs, w p ≤ α * ∑ p ∈ F, w p, the theorem asserts that: 1. For every list cuts, if every c ∈ cuts satisfies 1 ≤ c.1 ≤ c.2 < n, then for every c ∈ cuts, there exists p ∈ Alg cuts such that (c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2) (that is, exactly one of p.1, p.2 lies in [c.1, c.2]), and 2. For every list cuts, if every c ∈ cuts satisfies 1 ≤ c.1 ≤ c.2 < n, then for every F ⊆ L, if every c ∈ cuts has some p ∈ F satisfying (c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2), then ∑ p ∈ Alg cuts, w p ≤ α * ∑ p ∈ F, w p.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem reduces Online Cycle Augmentation to the online hitting set problem for top-left (TL) rectangles. The reduction relies on lemma cycle_link_crosses_cut_iff_tl_rect, which establishes that a cycle link crosses an interval cut if and only if the link hits the cut's corresponding TL-rectangle. Feasibility holds because the online algorithm hits every arriving TL-rectangle, which translates directly to crossing every arriving cut. Competitiveness follows because any valid offline cut cover is also a valid hitting set for the TL-rectangles, transferring the competitive ratio directly.

  1. Alg is feasible for Online Cycle Augmentation: for any valid cut sequence, every cut is crossed by an edge chosen by Alg.

    The theorem splits into two parts: feasibility and competitiveness. For feasibility, consider any valid cut sequence and cut c. By the TL-hitting feasibility assumption (h_tl_hit), Alg selects an edge p hitting the TL-rectangle of c. Since Alg only purchases edges from the pool L (by h_online), p satisfies the bounds 0 ≤ p.1 < p.2 < n. By lemma cycle_link_crosses_cut_iff_tl_rect, hitting the TL-rectangle is equivalent to crossing the cut c, so p crosses c.

    lines 22–30

    uses cycle_link_crosses_cut_iff_tl_rect

      constructor
      · intro cuts hcuts c hc
        obtain ⟨p, hp, h_rect⟩ := h_tl_hit cuts hcuts c hc
        have hpL : p ∈ L := h_online.1 cuts hp
        have hp_valid := hL p hpL
        have hc_valid := hcuts c hc
        have h_equiv := cycle_link_crosses_cut_iff_tl_rect p.1 p.2 c.1 c.2 (n : ℤ) hp_valid hc_valid
        refine ⟨p, hp, ?_⟩
        exact h_equiv.mpr h_rect
  2. Alg is α-competitive for Online Cycle Augmentation: its cost on any cut sequence is at most α times the cost of any feasible cut-covering edge set F ⊆ L.

    Let F ⊆ L be any offline edge set that covers all cuts in the sequence. For each cut c, some edge p ∈ F crosses c. Because p ∈ L, lemma cycle_link_crosses_cut_iff_tl_rect implies that p also hits the TL-rectangle of c. Thus F is a feasible hitting set for all arriving TL-rectangles. We then apply the assumed α-competitiveness of Alg for hitting TL-rectangles (h_tl_comp) against F to conclude that the total weight of edges chosen by Alg is at most α times the total weight of F.

    lines 31–42

    uses cycle_link_crosses_cut_iff_tl_rect

      · intro cuts hcuts F hFL hF_cross
        have hF_tl : ∀ c ∈ cuts, ∃ p ∈ F,
            (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2) := by
          intro c hc
          obtain ⟨p, hp, h_cross⟩ := hF_cross c hc
          have hpL : p ∈ L := hFL hp
          have hp_valid := hL p hpL
          have hc_valid := hcuts c hc
          have h_equiv := cycle_link_crosses_cut_iff_tl_rect p.1 p.2 c.1 c.2 (n : ℤ) hp_valid hc_valid
          refine ⟨p, hp, ?_⟩
          exact h_equiv.mp h_cross
        exact h_tl_comp cuts hcuts F hFL hF_tl
cycle_link_crosses_cut_iff_tl_rect
An edge (i, j) with 0 ≤ i < j < n crosses an interval cut [a, b] with 1 ≤ a ≤ b < n (that is, exactly one endpoint lies in [a, b]) if and only if (i, j) hits the top-left (TL) rectangle: either i ≤ a - 1 ∧ a ≤ j ≤ b, or a ≤ i ≤ b ∧ b + 1 ≤ j.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Finset BigOperators in/-- Theorem 1.10: An α-competitive online algorithm for TL-rectangle hitting set yields an α-competitive online algorithm for Online Cycle Augmentation. -/theorem online_cycle_augmentation_reduction_to_tl_hitting_set (n : ℕ) (L : Finset (ℤ × ℤ))    (hL : ∀ p ∈ L, 0 ≤ p.1 ∧ p.1 < p.2 ∧ p.2 < (n : ℤ))    (w : (ℤ × ℤ) → ℝ) (α : ℝ)    (Alg : List (ℤ × ℤ) → Finset (ℤ × ℤ))    (h_online : (∀ reqs, Alg reqs ⊆ L) ∧ (∀ reqs r, Alg reqs ⊆ Alg (reqs ++ [r])))    (h_tl_hit : ∀ reqs, (∀ c ∈ reqs, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) →      ∀ c ∈ reqs, ∃ p ∈ Alg reqs,        (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2))    (h_tl_comp : ∀ reqs, (∀ c ∈ reqs, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) →      ∀ F ⊆ L, (∀ c ∈ reqs, ∃ p ∈ F,        (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2)) →        ∑ p ∈ Alg reqs, w p ≤ α * ∑ p ∈ F, w p) :    ((∀ cuts, (∀ c ∈ cuts, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) →      ∀ c ∈ cuts, ∃ p ∈ Alg cuts,        ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2))) ∧    ∀ cuts, (∀ c ∈ cuts, 1 ≤ c.1 ∧ c.1 ≤ c.2 ∧ c.2 < (n : ℤ)) →      ∀ F ⊆ L, (∀ c ∈ cuts, ∃ p ∈ F,        ((c.1 ≤ p.1 ∧ p.1 ≤ c.2) ↔ ¬(c.1 ≤ p.2 ∧ p.2 ≤ c.2))) →        ∑ p ∈ Alg cuts, w p ≤ α * ∑ p ∈ F, w p) := by  constructor  · intro cuts hcuts c hc    obtain ⟨p, hp, h_rect⟩ := h_tl_hit cuts hcuts c hc    have hpL : p ∈ L := h_online.1 cuts hp    have hp_valid := hL p hpL    have hc_valid := hcuts c hc    have h_equiv := cycle_link_crosses_cut_iff_tl_rect p.1 p.2 c.1 c.2 (n : ℤ) hp_valid hc_valid    refine ⟨p, hp, ?_⟩    exact h_equiv.mpr h_rect  · intro cuts hcuts F hFL hF_cross    have hF_tl : ∀ c ∈ cuts, ∃ p ∈ F,        (p.1 ≤ c.1 - 1 ∧ c.1 ≤ p.2 ∧ p.2 ≤ c.2) ∨ (c.1 ≤ p.1 ∧ p.1 ≤ c.2 ∧ c.2 + 1 ≤ p.2) := by      intro c hc      obtain ⟨p, hp, h_cross⟩ := hF_cross c hc      have hpL : p ∈ L := hFL hp      have hp_valid := hL p hpL      have hc_valid := hcuts c hc      have h_equiv := cycle_link_crosses_cut_iff_tl_rect p.1 p.2 c.1 c.2 (n : ℤ) hp_valid hc_valid      refine ⟨p, hp, ?_⟩      exact h_equiv.mp h_cross    exact h_tl_comp cuts hcuts F hFL hF_tl
See it in the graphDiscuss this resultChallenge it