The Hardness and Approximation of the Densest k-Subgraph Problem in Parameterized Metric Graphs
Shih‐Chia Chang, Li-Hsuan Chen, Ling-Ju Hung, Shih-Shun Kao, Ralf Klasing · 2020
A complete weighted graph G = (V, E, w) is called Δβ-metric, for some β ≥ 1/2, if G satisfies the β-triangle inequality, i.e., w(u, v) ≤ β · (w(u, x) + w(x, v)) for all vertices u, v, x ∈ V . Given a Δβ-metric graph G = (V, E, w), the Δβ-WEIGHTED DENSEST k-SUBGRAPH (Δβ-WDkS) problem is to find an induced subgraph G[C] with exactly k vertices such that the total edge weight of G[C] is maximized. For β = 1, this problem, Δ-WDkS, is known NP-hard and admits a 1/2-approximation algorithms. In this paper, we show that for any β > 1/2, Δβ-WDkS is NP-hard. We also show how to modify any α-approximation algorithm for Δ-WDkS to obtain a δα,β-approximation algorithm for Δβ-WDkS with δα,β> α for every ββ-WDkS can be approximated to within a factor 1/2β for any β 1/2.