I problemet Densest k- Subgraph, givet en graf G och en parameter k, måste man hitta en subgraf av G som induceras på k hörn som innehåller det största antalet kanter. Det finns en betydande skillnad mellan de mest kända övre och nedre gränserna för detta problem. Det är NP-hård, och har inte en PTAS om inte NP har subexponentiella tid algoritmer. Å andra sidan ger den nuvarande mest kända algoritmen för Feige, Kortsarz och Peleg [10] ett approximationsförhållande på n 1/3−ε för vissa fasta ε > 0 (senare uppskattat till cirka ε = 1/90). Vi presenterar en algoritm som för varje ε > 0 approximerar Densest k-Subgraph problem inom ett förhållande på n 1/4+ε i tid n O(1/ε). Om tillåtet att köra för tid n O(log n), algoritmen uppnår en approximation förhållande av O(n 1/4 ). Vår algoritm är inspirerad av att studera en genomsnittlig-fall-version av problemet där målet är att skilja slumpmässiga grafer från slumpmässiga grafer med planterade täta subgrafer - approximationsförhållandet vi uppnår för det allmänna fallet matchar "skiljande förhållande" vi får för detta planterade problem. lämpligt definierade träd av konstant storlek i G, och med hjälp av dessa räknas för att identifiera hörnen i den täta subgrafen. Vi säger att en graf G(V, E) har log-densitet α om dess genomsnittliga grad är  på  på (-V -α ). Den algoritmiska kärnan i vårt resultat är ett förfarande för att mata ut en k-subgraf av 'nontrivial' densitet när den tätaste k-subgrafens log-densitet är större än värdgrafens log-densitet. Vi skisserar en förlängning till vår approximationsalgoritm som uppnår en O(n 1/4−ε )-uppskattning i O(2 n O(ε) ) tid. Vi visar också att för vissa parameterintervall, eigen value och SDP-baserade tekniker kan överträffa vår grundläggande särskiljande algoritm för slumpmässiga fall (i polynom tid), men utan att förbättra på O(n 1/4 ) garanti totalt.
Den nuvarande mest kända approximationen för DkS är O(n 1/4+ ) för godtyckligt liten konstant > 0, på grund av Bhaskara et al. Hoppa över det.
Detecting high log-densities: an O(n¼) approximation for densest k-subgraph
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}