Densest -Subgraph objective, reduction parameters and hardness assumptions
DefinitionDataValidation_Supplement_DkSapproximation-hardnessdensest-k-subgraphp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexity
For a simple undirected graph and , the Densest -Subgraph objective is the maximum number
of edges induced by a -vertex set. The DVP reduction uses the exact parameters
and loses the factor for when sampling back to vertices.
The module defines uniform encoded DkS algorithms and explicitly packages the two clique-promise DkS inapproximability statements cited as consequences of Almost-ETH and SPCH in Proposition 6. These propositions are assumptions imported from the cited literature, not new claims of this paper.
Formalization Note The objective is an edge count; dividing by gives the paper's density and does not change approximation ratios. The zero-optimum and cases are totalized separately.
Definition code
import Mathlib
import Definitions.Def_Clique_Language
import Definitions.Def_DataValidation_reductionInstance
import Definitions.Def_DataValidation_Supplement_Algorithms
set_option autoImplicit false
open Filter Topology
namespace DataValidation.Supplement
/-- The number of edges of `H` induced by the vertex set `S`. -/
def inducedEdgeCount (H : NPGraph.Graph) (S : Finset (Fin H.order)) : ℕ :=
((Finset.univ : Finset (Fin (DataValidation.hEdges H).length)).filter fun j =>
((DataValidation.hEdges H).get j).1 ∈ S ∧ ((DataValidation.hEdges H).get j).2 ∈ S).card
/-- The Densest `k`-Subgraph optimum `m*`, measured as the maximum number of induced edges.
The value is `0` when no `k`-vertex set exists; all uses below assume `k ≤ |V(H)|`. -/
noncomputable def dksOpt (H : NPGraph.Graph) (k : ℕ) : ℕ :=
sSup {r : ℕ | ∃ S : Finset (Fin H.order), S.card = k ∧ r = inducedEdgeCount H S}
/-- Density `|F[S]| / binom(k,2)` of a `k`-vertex set. -/
noncomputable def density (H : NPGraph.Graph) (k : ℕ) (S : Finset (Fin H.order)) : ℝ :=
(inducedEdgeCount H S : ℝ) / Nat.choose k 2
/-- Membership-vector encoding of a vertex set. -/
def encodeVertexSet (n : ℕ) (S : Finset (Fin n)) : List Bool :=
(List.finRange n).map fun u => decide (u ∈ S)
/-- A uniform encoded algorithm for Densest `k`-Subgraph. -/
structure DkSAlgorithm where
run : (H : NPGraph.Graph) → (k : ℕ) → Finset (Fin H.order)
time : NPGraph.Graph → ℕ → ℕ
machine : CookLevin.Machine
tapes : ℕ
alphabet : ℕ
wf : CookLevin.TuringMachine tapes alphabet machine
computes : ∀ H k, OutputsIn machine tapes (NPGraph.encodeInstance H k)
(encodeVertexSet H.order (run H k)) (time H k)
/-- The exact sampling loss in the proof of Theorem 2. For `k ≥ 2` it is
`2(2k-1)/(k-1) = 4 + 2/(k-1)`. The value `1` at `k < 2` supplies the trivial small cases. -/
noncomputable def samplingLoss (k : ℕ) : ℝ :=
if k < 2 then 1 else 2 * (2 * (k : ℝ) - 1) / ((k : ℝ) - 1)
/-- The paper's exact choice `D = ceil(m*/k)`. -/
noncomputable def reductionD (H : NPGraph.Graph) (k : ℕ) : ℕ :=
(dksOpt H k + k - 1) / k
/-- The paper's exact reduction budget `T = kD + m*`. -/
noncomputable def reductionT (H : NPGraph.Graph) (k : ℕ) : ℕ :=
k * reductionD H k + dksOpt H k
/-- `B` is the DkS approximation obtained from the unit-instance DVP approximation `A` in
Theorem 2. On a feasible DkS input it returns exactly `k` vertices. If `m* > 0`, its induced edge
count is within the factor `samplingLoss k * α(T,m,n)` after applying `A` to the exact instance
`G_H` with `D = ceil(m*/k)` and `T = kD + m*`. If `m* = 0`, every `k`-set is optimal and the DVP
algorithm need not be called. -/
def IsDkSApproxFrom (_A : PolicyAlgorithm) (α : ℕ → ℕ → ℕ → ℝ)
(B : DkSAlgorithm) : Prop :=
∀ (H : NPGraph.Graph) (k : ℕ), NPGraph.IsSimple H → 1 ≤ k → k ≤ H.order →
(B.run H k).card = k ∧
(dksOpt H k = 0 ∨
let I := DataValidation.reductionInstance H (reductionD H k) (reductionT H k)
(dksOpt H k : ℝ) ≤
samplingLoss k * α I.T I.E.card I.n * inducedEdgeCount H (B.run H k))
/-- The explicit DkS consequence customarily called Almost-ETH in Proposition 6(i): on a graph
containing a `k`-clique, no polynomial-time algorithm always returns a `k`-set of density strictly
larger than `2^{-(log n)^{1-ε}}`. It is an assumption imported from Manurangsi, not a result this
paper proves. -/
def AlmostETHDkSHardness : Prop :=
∀ ε : ℝ, 0 < ε → ε < 1 →
¬ ∃ (A : DkSAlgorithm) (c d : ℕ),
(∀ (H : NPGraph.Graph) (k : ℕ),
A.time H k ≤ c * (H.order + 1) ^ d) ∧
(∀ (H : NPGraph.Graph) (k : ℕ), NPGraph.IsSimple H → 2 ≤ k → k ≤ H.order →
CliqueNP.HasClique H k → (A.run H k).card = k ∧
(2 : ℝ) ^ (-((Real.logb 2 H.order) ^ (1 - ε))) < density H k (A.run H k))
/-- The explicit DkS consequence customarily called SPCH in Proposition 6(ii): for every positive
`f(k)=o(k)` and every parameter function `g`, no `g(k)n^{O(1)}` algorithm always finds density at
least `1/f(k)` on the clique promise. It is an imported assumption, not a claim of this paper. -/
def SPCHDkSHardness : Prop :=
∀ f : ℕ → ℝ, (∀ k, 1 ≤ f k) →
Tendsto (fun k : ℕ => f k / (k : ℝ)) atTop (nhds 0) →
∀ g : ℕ → ℕ,
¬ ∃ (A : DkSAlgorithm) (d : ℕ),
(∀ (H : NPGraph.Graph) (k : ℕ),
A.time H k ≤ g k * (H.order + 1) ^ d) ∧
(∀ (H : NPGraph.Graph) (k : ℕ), NPGraph.IsSimple H → 2 ≤ k → k ≤ H.order →
CliqueNP.HasClique H k → (A.run H k).card = k ∧
1 / f k ≤ density H k (A.run H k))
/-- The factor `2^{(log n)^{1-δ}}` in Theorem 2(1), with base-two logarithm. -/
noncomputable def almostFactor (δ : ℝ) (n : ℕ) : ℝ :=
(2 : ℝ) ^ ((Real.logb 2 n) ^ (1 - δ))
/-- A polynomial-time unit-instance DVP approximation with the factor in Theorem 2(1). -/
def IsAlmostETHForbiddenDVP (δ : ℝ) (A : PolicyAlgorithm) : Prop :=
IsPolicyApproximation A (fun I => almostFactor δ I.n) Instance.IsUnit ∧
∃ c d : ℕ, ∀ I, I.IsValid → 0 < I.T → I.IsUnit →
A.time I ≤ c * (I.n + 1) ^ d
/-- A unit-instance DVP approximation of factor `a(T)` in time `g(T)n^{O(1)}`. -/
def IsSPCHForbiddenDVP (a : ℕ → ℝ) (g : ℕ → ℕ) (A : PolicyAlgorithm) : Prop :=
IsPolicyApproximation A (fun I => a I.T) Instance.IsUnit ∧
∃ d : ℕ, ∀ I, I.IsValid → 0 < I.T → I.IsUnit →
A.time I ≤ g I.T * (I.n + 1) ^ d
/-- The encoded Densest `k`-Subgraph optimization interface used in Theorem 2, bundled with the
algorithm whose output is a `k`-vertex set. This is the public entry point of the DkS definition
module; the objective, exact reduction parameters and hardness assumptions are defined above. -/
structure DkS where
algorithm : DkSAlgorithm
end DataValidation.Supplement
Source
Tinguely, van der Heijden, Approximation and Hardness for the Data Validation Problem, arXiv:2611.06773 (sha256 6595f819…), §2, pp.3–6, especially Proposition 6 and proof of Theorem 2