The Hardness and Approximation of the Densest k-Subgraph Problem in Parameterized Metric Graphs
The Hardness and Approximation of the Densest k-Subgraph Problem in Parameterized Metric Graphs
复制标题
参数化度量图中最稠k子图问题的难度和逼近
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
R. Klasing
中科院分区：
文献类型：
--
作者：
Shi;Li;Ling;Shih;R. Klasing
一个完全赋权图G =（V，E，w）称为Δβ-度量，其中β ≥ 1/2，如果G满足β-三角不等式，即，对于所有顶点u，v，x ∈ V，w（u，v）≤ β ·（w（u，x）+ w（x，v））.给定一个Δβ-度量图G =（V，E，w），Δβ-加权稠密k-子图（Δβ-WDkS）问题是寻找一个恰好有k个顶点的导出子图G[C]，使得G[C]的总边权最大化.当β = 1时，该问题Δ-WDkS是NP-困难的，并有一个$frac{1}{2}$-近似算法.本文证明了对任意β > 1/2，Δβ-WDkS是NP-难的.我们还展示了如何修改Δ-WDkS的任何α-近似算法，以获得Δβ-WDkS的δα，β-近似算法，其中对于每个β < 1，δα，β > α。此外，我们还证明了Δβ-WDkS可以近似到因子$frac{1}{{2eta }}$对于任何$eta > frac{1}{2}$。
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 $frac{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 β < 1. Moreover, we prove that Δβ-WDkS can be approximated to within a factor $frac{1}{{2eta }}$ for any $eta > frac{1}{2}$.
影响因子：
0.5
作者：
Chang, Maw-Shang;Chen, Li-Hsuan;Wu, Guan-Han
通讯作者：
Wu, Guan-Han