论文标题
最密集的$ k $ -subgraph问题的种植模型
Planted Models for the Densest $k$-Subgraph Problem
论文作者
论文摘要
给定无向图$ g $，密集的$ k $ -subgraph问题（DKS）要求计算一个$ s \ subset v $ of Cardinality $ \ left \ left \ lvert \ lvert s \ right \ rvert \ rvert \ rvert \ leq k $，以使$ s $内部的边缘的重量最大化。这是一个基本的NP硬性问题，尽管有数十年的研究，但尚待解决，其近似性尚待解决。由于Bhaskara等人而引起的当前最著名的近似算法。 （2010）计算$ \ MATHCAL {O} \ left（{n^{1/4 +ε}}} \ right）$近似时间$ n^{\ Mathcal {o} \ left（1/am phoft（1/am^\ oright）} $，对于任何$ε> 0 $。 我们问这个问题的一些“容易”的实例是什么？我们提出了一些具有种植稠密子图的实例的天然半随机模型，并研究了用于计算其中最密集子图的近似算法。这些模型的灵感来自针对各种其他图形问题（例如独立集问题，图形分区问题等）研究的半随机模型。对于这些模型的大量参数，我们获得了浓密的$ k $ -subgraph问题的更好近似因素。此外，我们的算法恢复了种植溶液的很大一部分。
Given an undirected graph $G$, the Densest $k$-subgraph problem (DkS) asks to compute a set $S \subset V$ of cardinality $\left\lvert S\right\rvert \leq k$ such that the weight of edges inside $S$ is maximized. This is a fundamental NP-hard problem whose approximability, inspite of many decades of research, is yet to be settled. The current best known approximation algorithm due to Bhaskara et al. (2010) computes a $\mathcal{O}\left({n^{1/4 + ε}}\right)$ approximation in time $n^{\mathcal{O}\left(1/ε\right)}$, for any $ε> 0$. We ask what are some "easier" instances of this problem? We propose some natural semi-random models of instances with a planted dense subgraph, and study approximation algorithms for computing the densest subgraph in them. These models are inspired by the semi-random models of instances studied for various other graph problems such as the independent set problem, graph partitioning problems etc. For a large range of parameters of these models, we get significantly better approximation factors for the Densest $k$-subgraph problem. Moreover, our algorithm recovers a large part of the planted solution.
