Detecting High Log-Densities – an O ( n 1 / 4 ) Approximation for Densest k -Subgraph
Detecting High Log-Densities – an O ( n 1 / 4 ) Approximation for Densest k -Subgraph
复制标题
DOI：
--
复制
发表时间：
2010
影响因子：
3.7
通讯作者：
Aditya Bhaskara;M. Charikar;E. Chlamtác;U. Feige;Aravindan Vijayaraghavan
中科院分区：
文献类型：
--
作者：
Aditya Bhaskara;M. Charikar;E. Chlamtác;U. Feige;Aravindan Vijayaraghavan
在Denmark-Subgraph问题中，给定一个图G和一个参数k，需要找到G在k个顶点上诱导的一个子图，该子图包含最大数量的边。该问题最为人所知的上限和下限之间存在显着差距。它是NP难的，并且没有PTAS，除非NP有次指数时间算法。另一方面，Feige，Kortsarz和Peleg [FKP 01]的当前最著名的算法，对于某些特定ε > 0给出了n 1 / 3 − ε的近似比（这些作者估计约为ε = 1 / 60）。我们提出了一个算法，对每个ε > 0，在时间nO（1 /ε）内以n1/ 4+ ε的比率逼近Denk-Subgraph问题.如果允许运行时间n O（log n），我们的算法实现了O（n 1 / 4）的近似比。我们的算法的灵感来自于研究一个平均情况下的版本的问题，其目标是区分随机图与随机图种植密集的子图-近似比，我们实现的一般情况下匹配的“区分比”，我们获得这个种植的问题。实现一个区别比O（N 1 / 4）的种植问题（在多项式时间）是超出了我们目前的技术。在高层次上，我们的算法涉及巧妙地计算G中适当定义的恒定大小的树，并使用这些计数来识别稠密子图的顶点。我们的算法基于以下原则。我们说一个图G（V，E）有对数密度α，如果它的平均度是Θ（|V| α）。我们结果的算法核心是一系列算法，
In the Densest k -Subgraph problem, given a graph G and a parameter k , one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg [FKP01], gives an approximation ratio of n 1 / 3 − ε for some specific ε > 0 (estimated by those authors at around ε = 1 / 60). We present an algorithm that for every ε > 0 approximates the Densest k -Subgraph problem within a ratio of n 1 / 4+ ε in time n O (1 /ε ) . If allowed to run for time n O (log n ) , our algorithm achieves an approximation ratio of O ( n 1 / 4 ). Our algorithm is inspired by studying an average-case version of the problem where the goal is to distinguish random graphs from random graphs with planted dense subgraphs – the approximation ratio we achieve for the general case matches the “distinguishing ratio” we obtain for this planted problem. Achieving a distinguishing ratio of o ( n 1 / 4 ) for the planted problem (in polynomial time) is beyond the reach of our current techniques. Atahigh level, our algorithms involve cleverly counting appropriately defined trees of constant size in G , and using these counts to identify the vertices of the dense subgraph. Our algorithm is based on the following principle. We say that a graph G ( V, E ) has log-density α if its average degree is Θ( | V | α ). The algorithmic core of our result is a family of algorithms that