Claim 12 — if Algorithm 1 reaches Line 11 then
ProvedLovaszECCKernel.claim_12edge-clique-covergraph-theorykernelizationlovasz-boundp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexity
Claim 12. Let be a finite simple graph with vertices and edges, and . If Algorithm 1 reaches Line 11, i.e. neither Line 2 (if then return ) nor Line 5 (if and then return ) returned, then
So after preprocessing the graph is dense, , and the Cluster Editing approximation runs in time .
Differences from the source:
- reading: A reaches Line 11 → ¬(m ≤ Lb(G) − k) and ¬(k ≥ m ∧ k ≥ n) for the input graph G; reason: Lines 2 and 5 are the only returns before Line 11, and the proof of the claim uses exactly these two tests on the input's n and m
- encoding: m ≥ n·(n − 3)/6 → compared in ℝ, the test of Line 2 in ℤ; reason: no truncated subtraction or division
Preamble
import Mathlib import Definitions.Def_LovaszECCKernel_nonEdges import Definitions.Def_LovaszECCKernel_Lb set_option autoImplicit false
Formal statement
namespace LovaszECCKernel
/-- **Claim 12** (Fomin, Golovach, Khargeliia, Sagunov, Simonov, *Stability Meets Kernelization: Algorithmic
Extensions of the Lovász and Erdős–Goodman–Pósa Theorems*, STOC 2027 submission (manuscript
sha256 a9d53ab8…), Claim 12, p.42 (= PDF p.42)): "If A reaches Line 11, then
m ≥ n · (n − 3)/6." Algorithm 1 (p.42) reaches Line 11 when neither Line 2 ("if m ≤ Lb(G) − k then
return Y") nor Line 5 ("if k ≥ m and k ≥ n then return (G, k)") returned.
**Formalization Note** `n` and `m` are the vertex and edge counts of the input graph `G`, the graph
tested in Lines 2 and 5 (the proof of the claim uses exactly these two tests). The test of Line 2 is
compared in `ℤ`; the conclusion in `ℝ`. -/
theorem claim_12 {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ)
(h₂ : ¬ ((edgeCount G : ℤ) ≤ (Lb G : ℤ) - k))
(h₅ : ¬ (edgeCount G ≤ k ∧ Fintype.card V ≤ k)) :
(Fintype.card V : ℝ) * ((Fintype.card V : ℝ) - 3) / 6 ≤ edgeCount G := by sorry
end LovaszECCKernel
Source
Fomin, Golovach, Khargeliia, Sagunov, Simonov, Stability Meets Kernelization: Algorithmic Extensions of the Lovász and Erdős–Goodman–Pósa Theorems, STOC 2027 submission (manuscript sha256 a9d53ab8…), Claim 12 and Algorithm 1, p.42 (= PDF p.42)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.