9
$\begingroup$

I know that many graph problems can be solved very quickly on graphs of bounded degeneracy or arboricity. (It doesn't matter which one is bounded, since they're at most a factor of 2 apart.)

From Wikipedia's article on the clique problem I learnt that finding cliques of any constant size k takes linear time on graphs of bounded arboricity. That's pretty cool.

I wanted to know more examples of algorithms where the bounded arboricity condition helps. This might even be well-studied enough to have a survey article written on it. Unfortunately, I couldn't find much about my question. Can someone give me examples of such algorithms and references? Are there some commonly used algorithmic techniques that exploit this promise? How can I learn more about these results and the tools they use?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think the keyword you want is "parameterized complexity". $\endgroup$
    – Reid Barton
    Commented Jan 10, 2010 at 19:58
  • 1
    $\begingroup$ Or "fixed-parameter tractability". The standard text used to be "Parameterized Complexity" by Downey and Fellows, but the field progressed quickly so it might be a little dated by now. $\endgroup$
    – François G. Dorais
    Commented Jan 11, 2010 at 0:20
  • $\begingroup$ Thanks for the comments. I know there's a lot of work in parametrized complexity using tree width, but I don't know if that works for bounded arboricity too. $\endgroup$
    – Rune
    Commented Jan 11, 2010 at 3:34

4 Answers 4

Reset to default
11
$\begingroup$

Bounded degeneracy or arboricity just means that the graph is sparse (number of edges is proportional to number of vertices in all subgraphs).

Some ideas that have been used for fast algorithms on these graphs:

  • Order the vertices so that each vertex has only d neighbors that are later in the ordering, where d is the degeneracy. Then if one can similarly order the structure one is looking for, there are not too many different choices to try. For instance (though this is not the method of the Chiba & Nishizeki paper that you indirectly refer to) one can find all cliques by trying all subsets of later neighbors of each vertex. This idea also works to color these graphs with at most d+1 colors: just choose colors for vertices one at a time in the opposite of the above ordering. See e.g. Matula and Beck, JACM 1983.

  • Find a low degree vertex, do something to it to reduce the size of the graph while preserving its overall sparsity, and continue. This is how one finds an ordering as above (repeatedly remove the smallest degree vertex) and is also how many planar coloring algorithms work.

  • Find a big independent set (or a big independent set of bounded-degree vertices), do something on it, and repeat on the remaining smaller graph. This often leads to linear time algorithms because every graph of bounded degeneracy has an independent set of Ω(n) vertices, so the size of the graph goes down by a constant factor at each repetition and the total time can be bounded by a geometric series. This is a variation of the "low degree vertex" idea that works better in the parallel algorithms setting.

  • Observe that there can only be very few vertices with high degree (O(dk) vertices with degree greater than n/k) or else they would have too many edges. So if you are looking for a structure that needs high degree vertices you don't have many choices to try. See e.g. Alon and Gutner, Algorithmica 2009.

Improve this answer
$\endgroup$
3
$\begingroup$

I think you might want to look at the related/(same?) concept of treewidth. Its a much stronger sparseness requirement than constant degree, planar, etc, and if you have something like $\mathcal O(\log n)$ tree width, many NP-Hard problems on graphs become easy (such as computing graph cutes). Unfortunately in general computing a tree width decomposition is np hard

See the wikipedia page for details.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Tree width is actually a different concept. Planar graphs for instance have constant arboricity, but can have arbitrarily large tree width. $\endgroup$
    – Rune
    Commented Jan 11, 2010 at 3:33
  • $\begingroup$ well, then the question is are they related in some way? Also, It'd be more accurate I think to say that planar graphs can have tree width linear in the number of nodes rather than arbitrarily large (or is there a class of graphs that does worse than then NxN grid?) $\endgroup$
    – Carter Tazio Schonwald
    Commented Jan 11, 2010 at 4:54
  • $\begingroup$ By arbitrarily large I just meant that for any given k there exists a planar graph with tree width > k. Of course the tree width can never be more than the number of vertices, so that's always an upper bound on the tree width of a graph. $\endgroup$
    – Rune
    Commented Jan 14, 2010 at 5:03
1
$\begingroup$

One article that provides algorithms for the MDS problem on graphs of bounded arboricity is "Minimum Dominating Set Approximation in Graphs of Bounded Arboricity" by Lenzen and Wattenhofer http://www.disco.ethz.ch/publications/disc10_LW_204.pdf

Improve this answer
$\endgroup$
1
$\begingroup$

There is one more approach to solve problems like Max Clique on graphs of bounded degeneracy. You can look at the complement graph of a graph $G$ (i.e. every edge is a non-edge and every non-edge is an edge). Solving Max Clique on $G$ is the same as solving Max Independent set on the complement.

For the complement of bounded degeneracy graphs algorithms for many problems are known. E.g. Maximum Independent Set, Minimum Dominating Set, Perfect Code, k-Coloring, H- Cover, H-Homomorphism and H-Role Assignment are FPT parameterized by the degeneracy of the complement. See http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf (submitted to journal)

Some of these problems make sense to translate to the complement graph, such as:

Can G be colored with $k$ colors -> can the complement be covered by $k$ cliques? (fixed $k$)

Is there an $3$-regular induced subgraph of $G$ -> is there an induced $k$ regular subgraph of the complement on $k+4$ vertices?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .