The Dense k -Subgraph Problem

By Uriel Feige, G. Kortsarz, David Peleg. Algorithmica, 2001

625 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/49bfad37cb0c2d82b85fa3c4cb333767ac5c49a6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Discovering Large Dense Subgraphs in Massive Graphs (2005, background): “Unfortunately, ﬁnding bipartite cliques and dense subgraphs are notoriously hard combinatorial problems, even to solve approximately (see, e.g., [13]).”
Collective annotation of Wikipedia entities in web text (2009, background): “In continuing work, we are trying to cast the annotation problem as special cases of quadratic assignment that can be approximated well [6, 16] or show that even approximation is difficult [10, 16].”
Greedy approximation algorithms for finding dense components in a graph (2000, background): “Problem, where the goal is to find an induced subgraph of k vertices of maximum average degree [1,2, 4 ,5].”
Community detection in graphs (2009, background): “(14) Since the only contributions to the sum come from vertex pairs belonging to the same cluster, we can group these contributions together and rewrite the sum over the vertex pairs as a sum over the clusters Q = nc∑ c=1 [ lc m − ( dc 2m )2 ] .”
Truncated power method for sparse eigenvalue problems (2011, methodology): “nd repeatedly adds a vertex to the current subgraph to maximize the weight of the resulting new subgraph; this process is repeated until k vertices are chosen. The other greedy method is developed by Feige et al. (2001, Procedure 2) which is referred as Greedy-Feige in our experiments. The procedure”
On the Bursty Evolution of Blogspace (2003, background): “Unfortunately, finding the densest subgraph in an undirected graph is NP-hard and appears notoriously difficult to even solve approximately [ 8 ].”
The community-search problem and how to plan a successful cocktail party (2010, background): “When adding size constraints, and asking to find a subgraph of size exactly k the problem becomes NP-hard, while the best algorithm for this problem has an approximation guarantee of O(n), where α < 1 3 [11].”
A model of Internet topology using k-shell decomposition (2006, methodology): “ absence of a link. Bar et al. [24] suggested to look for loose cliques, but unlike [21, 22] used the graph topology without side information. They used the dense k-subgraph heuristic of Feige et al. [25] to ﬁnd for each size l the densest subgraph of this size. The result is a series of clusters, o”
Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees (2013, background): “H̊astad [20] shows that, unless P = NP, there cannot be any polynomial time algorithm that approximates the maximum clique within a factor better thanO(n1−ǫ), for any ǫ > 0.”
Entity Linking meets Word Sense Disambiguation: a Unified Approach (2014, background): “The problem of identifying the densest subgraph of size at least k is NP-hard (Feige et al., 1999).”