文章基本信息

标题：Planted Models for the Densest k-Subgraph Problem
本地全文：下载
作者：Yash Khanna ; Anand Louis
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：182
页码：1-18
DOI：10.4230/LIPIcs.FSTTCS.2020.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given an undirected graph G, the Densest k-subgraph problem (DkS) asks to compute a set S âS, V of cardinality S â¤ 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 ð'ª(n^{1/4 Îµ}) approximation in time n^{ð'ª(1/Îµ)}, 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.
关键词：Densest k-Subgraph; Semi-Random models; Planted Models; Semidefinite Programming; Approximation Algorithms; Beyond Worst Case Analysis