English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the Densest k-Subgraph problem, given a graph G and a parameter k, oneneeds to find a subgraph of G induced on k vertices that contains the largestnumber of edges. There is a significant gap between the best known upper andlower bounds for this problem. It is NP-hard, and does not have a PTAS unlessNP has subexponential time algorithms. On the other hand, the current bestknown algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio ofn^(1/3-epsilon) for some specific epsilon > 0 (estimated at around 1/60).  We present an algorithm that for every epsilon > 0 approximates the Densestk-Subgraph problem within a ratio of n^(1/4+epsilon) in time n^O(1/epsilon). Inparticular, our algorithm achieves an approximation ratio of O(n^1/4) in timen^O(log n). Our algorithm is inspired by studying an average-case version ofthe problem where the goal is to distinguish random graphs from graphs withplanted dense subgraphs. The approximation ratio we achieve for the generalcase matches the distinguishing ratio we obtain for this planted problem.  At a high level, our algorithms involve cleverly counting appropriatelydefined trees of constant size in G, and using these counts to identify thevertices of the dense subgraph. Our algorithm is based on the followingprinciple. We say that a graph G(V,E) has log-density alpha if its averagedegree is Theta(|V|^alpha). The algorithmic core of our result is a family ofalgorithms that output k-subgraphs of nontrivial density whenever thelog-density of the densest k-subgraph is larger than the log-density of thehost graph.

Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph