Dense subgraph

Dense subgraph
An example of a graph G with density dG = 1.375 and it's densest subgraph induced by the vertices b,c,d and h in red with density 1.4

In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let G = (E,V) be an undirected graph and let S = (ES,VS) be a subgraph of G. Then the density of S is defined to be  d_S = {|E_S|\over|V_S|} .

The densest subgraph problem is that of finding a subgraph of maximum density. In 1984, A. V. Goldberg developed a polynomial time algorithm to find the maximum density subgraph using a max flow technique.

Contents

Densest k subgraph

There are many variations on the densest subgraph problem. There is the densest k subgraph problem, where the objective is to find the maximum density subgraph on exactly k vertices. This problem is known to be NP-Hard by a reduction from the clique problem. The densest k subgraph problem is NP-Complete even in planar graphs by a reduction from the connected vertex cover problem on planar graphs with maximum degree 4. There does not exist a polynomial-time approximation scheme (PTAS) for the densest k subgraph problem this is by a reduction from the Minimum Distance of Code problem.

Densest at most k subgraph

The objective of the densest at most k problem is to find the maximum density subgraph on at most k vertices. Anderson and Chellapilla showed that if there exists an α approximation for this problem then that will lead to an Θ(α2) approximation for the densest k subgraph problem.

Densest at least k subgraph

The densest at least k problem is defined similarly to the densest at most k subgraph problem. There is a 2-approximation due to Anderson. But the complexity of this problem is still unknown.

References

  • Goldberg, A. V. (1984), "Finding a maximum density subgraph", Technical report .
  • Feige, U.; Kortsarz, G.; Peleg, D. (1997), "The dense k-subgraph problem", Algorithmica 29: 410–421 .
  • Keil, J.; Brecht, T. (1991), "The complexity of clustering in planar graphs", The Journal of Combinatorial Mathematics and Combinatorial Computing 9: 155–159 .
  • Khot, S. (2006), "Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique", SIAM Journal of Computing 36: 1025–1071 .
  • Anderson, R.; Chellapilla, K. (2009), "Finding dense subgraphs with size bounds", WAW: 25–36 .
  • Anderson, R. (2007), "Finding large and small dense subgraphs", CoRR .
  • Khuller, S.; Saha, B. (2009), "On finding dense subgraphs", The International Colloquium on Automata, Languages and Programming .

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Dense graph — In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and… …   Wikipedia

  • Arboricity — The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning trees needed to cover all the edges of the graph.ExampleThe figure shows the… …   Wikipedia

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

  • Maximal independent set — This article is about the combinatorial aspects of maximal independent sets of vertices in a graph. For other aspects of independent vertex sets in graph theory, see Independent set (graph theory). For other kinds of independent sets, see… …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

  • Paley graph — infobox graph name = Paley graph image caption = The Paley graph of order 13 namesake = Raymond Paley vertices = edges = chromatic number = chromatic index = properties = Strongly regularIn mathematics, and specifically graph theory, Paley graphs …   Wikipedia

  • Prim's algorithm — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Community structure — In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into (potentially overlapping) sets of nodes such that each set of nodes is densely connected internally. In the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”