Metric k-center is NP-hard to approximate within a factor below 2

A polynomial-time algorithm for metric k-center whose radius is always within a factor ρ < 2 of the optimum decides the NP-complete dominating set problem, so it gives P = NP ([WS11], Theorem 2.4, attributed there to [HN79]). A graph G becomes the k-center instance domMatrix G on its distinct declared vertices, at distance 0 from themselves, 1 from adjacent vertices and 2 from the other vertices. When G has a dominating set of at most k vertices the optimal radius is 1, and a radius below 2 · 1 is a radius of 1, so the centers that the algorithm chooses dominate G; this is the gap Cslib.Algorithms.Lean.KCenter.isDominatingSet_of_radius_le_mul. The decider checks whether they do. Gonzalez's algorithm (CslibFrontier.Algorithms.Lean.KCenter.Gonzalez) meets the hypotheses with ρ = 2 apart from running time, which is not certified there, so the factor 2 is the threshold.

Model

An instance is a matrix D of natural distances, given as a list of rows, and a number k of centers, both in binary: KCenter.encKCenter pairs the matrix encoding KCenter.encDistMatrix (a framed list of framed lists of binary entries) with encNat. The points are the row indices. The metric instances (KCenter.IsInstance) are the square matrices with zero diagonal, symmetric and satisfying the triangle inequality: the model of Section 2.2 of [WS11], with natural distances. The algorithm A returns a list of point indices; KCenter.centers D l is the set of points named by l, so out-of-range indices and repetitions are ignored.

The hypotheses on A are required only on metric instances with 1 ≤ k ≤ D.length, the instances of Section 2.2, where k centers are chosen among the points:

• it chooses at most k centers (implied by (A (D, k)).length ≤ k, see KCenter.card_centers_le); with k ≤ D.length points, adding centers does not increase the radius, so this matches the k centers of the source;
• its radius is at most ρ * r for every bound r on the optimal radius, with distances in ℝ. With k ≥ 1 the optimum is finite, so this is radius ≤ ρ · OPT, stated as in Cslib.Algorithms.Lean.KCenter.isDominatingSet_of_radius_le_mul without multiplication in WithTop ℝ.

Natural distances and these restrictions only weaken the hypotheses, so the theorem implies the corresponding statement for algorithms on instances with real distances and any k.

NP-hardness of dominating set on the library's encoded graphs is Cslib.Complexity.DominatingSet_npComplete, through a reduction from vertex cover; Williamson and Shmoys take it from the literature.

Main definitions

• Cslib.Complexity.KCenter.IsInstance: metric k-center instances.
• Cslib.Complexity.KCenter.centers: the centers named by a list of indices.
• Cslib.Complexity.KCenter.domMatrix: the {0, 1, 2} distance matrix of a graph.
• Cslib.Complexity.KCenter.decideDominatingSet: the decider built from a k-center algorithm.

Main results

• Cslib.Complexity.KCenter.isInstance_domMatrix, Cslib.Complexity.KCenter.computableInPolyTime_domMatrix: the distance matrix of a graph is a metric instance, computable in polynomial time.
• Cslib.Complexity.KCenter.decideDominatingSet_iff: the decider decides DominatingSet.
• Cslib.Complexity.KCenter.computableInPolyTime_decideDominatingSet: it is polynomial-time when the algorithm is.
• Cslib.Complexity.P_eq_NP_of_kCenter_approx: Theorem 2.4: a polynomial-time ρ-approximation algorithm for metric k-center with ρ < 2 gives P = NP.

References

• W.-L. Hsu and G. L. Nemhauser, Easy and hard bottleneck location problems
• D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Section 2.2.

@[reducible, inline]

abbrev Cslib.Complexity.KCenter.encDistMatrix : List (List ℕ) ↪ List Bool

A distance matrix: a framed list of rows, each a framed list of binary natural entries.

@[reducible, inline]

abbrev Cslib.Complexity.KCenter.encKCenter : List (List ℕ) × ℕ ↪ List Bool

A k-center instance: the distance matrix (encDistMatrix) paired with the binary number k of centers.

structure Cslib.Complexity.KCenter.IsInstance (D : List (List ℕ)) : Prop

A metric k-center instance: a square matrix of natural distances, with rows indexed by the points 0, …, D.length - 1, zero on the diagonal, symmetric and satisfying the triangle inequality ([WS11], Section 2.2).

• length_row (row : List ℕ) : row ∈ D → row.length = D.length

  Every row lists the distances to all the points.

• dist_self (i : ℕ) : i < D.length → TSP.dist D i i = 0

  Every point is at distance 0 from itself.

• isMetric : TSP.IsMetric D

  The distances are symmetric and satisfy the triangle inequality.

def Cslib.Complexity.KCenter.centers (D : List (List ℕ)) (l : List ℕ) : Finset (Fin D.length)

The centers chosen by a list l of indices: the points i of D with i ∈ l. Indices out of range are ignored.

@[simp]

theorem Cslib.Complexity.KCenter.mem_centers {D : List (List ℕ)} {l : List ℕ} {i : Fin D.length} : i ∈ centers D l ↔ ↑i ∈ l

theorem Cslib.Complexity.KCenter.card_centers_le (D : List (List ℕ)) (l : List ℕ) : (centers D l).card ≤ l.length

A list of indices names at most as many centers as its length.

def Cslib.Complexity.KCenter.domMatrix (G : Graph) : List (List ℕ)

The {0, 1, 2} distance matrix of a graph ([WS11], Theorem 2.4): the points are the distinct declared vertices, at distance 0 from themselves, 1 from adjacent vertices and 2 from the other vertices.

def Cslib.Complexity.KCenter.centerLabels (A : List (List ℕ) × ℕ → List ℕ) (G : Graph) (k : ℕ) : List ℕ

The vertices of G named by the indices that A returns on (domMatrix G, k).

def Cslib.Complexity.KCenter.decideDominatingSet (A : List (List ℕ) × ℕ → List ℕ) (x : DominatingSetInstance) : Bool

The decider for DominatingSet built from a k-center algorithm A: accept x when x.bound is at most the number of distinct vertices of x.graph, x.bound > 0 unless x.graph has no vertices, and the vertices named by the centers that A chooses on (domMatrix x.graph, x.bound) dominate x.graph.

@[simp]

theorem Cslib.Complexity.KCenter.length_domMatrix (G : Graph) : (domMatrix G).length = G.distinctVertices.length

theorem Cslib.Complexity.KCenter.isInstance_domMatrix (G : Graph) : IsInstance (domMatrix G)

The distance matrix of a graph is a metric k-center instance.

theorem Cslib.Complexity.KCenter.decideDominatingSet_iff {A : List (List ℕ) × ℕ → List ℕ} {ρ : ℝ} (hρ : ρ < 2) (hcard : ∀ (D : List (List ℕ)) (k : ℕ), IsInstance D → 0 < k → k ≤ D.length → (centers D (A (D, k))).card ≤ k) (hratio : ∀ (D : List (List ℕ)) (k : ℕ) [inst : NeZero D.length], IsInstance D → 0 < k → k ≤ D.length → ∀ (r : ℝ), Algorithms.Lean.KCenter.optRadius (fun (i j : Fin D.length) => ↑(TSP.finDist D i j)) k ≤ ↑r → Algorithms.Lean.KCenter.radius (fun (i j : Fin D.length) => ↑(TSP.finDist D i j)) (centers D (A (D, k))) ≤ ↑(ρ * r)) (x : DominatingSetInstance) : decideDominatingSet A x = true ↔ x ∈ DominatingSet

The decider is correct ([WS11], Theorem 2.4): if, on metric instances with 1 ≤ k ≤ D.length, A returns at most k centers with a radius within a factor ρ < 2 of the optimum, then decideDominatingSet A decides DominatingSet.

theorem Cslib.Complexity.KCenter.computableInPolyTime_domMatrix : Turing.MultiTapeTM.ComputableInPolyTime domMatrix encGraph encDistMatrix

The distance matrix of a graph is computable in polynomial time, with binary entries.

theorem Cslib.Complexity.KCenter.computableInPolyTime_decideDominatingSet {A : List (List ℕ) × ℕ → List ℕ} (hA : Turing.MultiTapeTM.ComputableInPolyTime A encKCenter (Turing.MultiTapeTM.encList Turing.MultiTapeTM.encNat)) : Turing.MultiTapeTM.ComputableInPolyTime (decideDominatingSet A) encDominatingSet Turing.MultiTapeTM.encBool

The decider built from a polynomial-time k-center algorithm is polynomial-time.

theorem Cslib.Complexity.P_eq_NP_of_kCenter_approx {A : List (List ℕ) × ℕ → List ℕ} {ρ : ℝ} (hρ : ρ < 2) (hA : Turing.MultiTapeTM.ComputableInPolyTime A KCenter.encKCenter (Turing.MultiTapeTM.encList Turing.MultiTapeTM.encNat)) (hcard : ∀ (D : List (List ℕ)) (k : ℕ), KCenter.IsInstance D → 0 < k → k ≤ D.length → (KCenter.centers D (A (D, k))).card ≤ k) (hratio : ∀ (D : List (List ℕ)) (k : ℕ) [inst : NeZero D.length], KCenter.IsInstance D → 0 < k → k ≤ D.length → ∀ (r : ℝ), Algorithms.Lean.KCenter.optRadius (fun (i j : Fin D.length) => ↑(TSP.finDist D i j)) k ≤ ↑r → Algorithms.Lean.KCenter.radius (fun (i j : Fin D.length) => ↑(TSP.finDist D i j)) (KCenter.centers D (A (D, k))) ≤ ↑(ρ * r)) {α : Type} (enc : α ↪ List Bool) : P enc = NP enc

No ρ-approximation for metric k-center with ρ < 2 unless P = NP ([WS11], Theorem 2.4; [HN79]). Let A be a polynomial-time algorithm that, on every metric instance (D, k) with 1 ≤ k ≤ D.length, chooses at most k centers whose radius is at most ρ times every bound on the optimal radius, with ρ < 2. Then P = NP. Distances are natural numbers in binary; see the module docstring for why the restrictions only strengthen the statement.