Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded graphs?

Update 10/24 It seems to follow Grohe's results that formula that is FPT to test on bounded-treewidth graphs is FPT to test on minor excluded graphs. Now the question is -- how does it relate to tractability of counting satisfying assignments of such formula?

The above statement is false. MSOL is FPT on bounded tree-width graphs, however 3-colorability is NP-complete on planar graphs which are minor-excluded.

share|improve this question
    
I was putting off accepting some answers because I was planning to verify them experimentally, but I'll accept them now to keep things moving –  Yaroslav Bulatov Oct 26 '10 at 5:34

4 Answers 4

up vote 21 down vote accepted

The most general result known is by Grohe. A summary was presented in July 2010:

  • Martin Grohe, Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors, LICS 2010. (PDF)

In short, any statement that is expressible in fixed-point logic with counting has a polynomial-time algorithm on classes of graphs with at least one excluded minor. (FP+C is first-order logic augmented with a fixed-point operator and a predicate that gives the cardinality of definable sets of vertices). The key idea is that excluding a minor allows the graphs in the class to have ordered treelike decompositions that are definable in fixed-point logic (without counting).

So a large class of answers to your question can be obtained by considering properties that are definable in FP+C but that are hard to count.


Edit: I'm not sure this actually answers your question, even less so for your update. The pointer to and statement of Grohe's result are correct, but I don't think the struck out text is relevant for your question. (Thanks to Stephan Kreutzer for pointing this out.) It might be worth clarifying: do you want a counting problem that is difficult in general but easy on minor-excluded classes, or a decision problem?

share|improve this answer
1  
Interesting...I wonder what this treelike decomposition looks like for planar graphs –  Yaroslav Bulatov Oct 22 '10 at 19:27
2  
A useful theorem I found is that property is expressible in FP+C iff it is decidable in polynomial time on bounded tw graph. Now the question is -- how does complexity of FP+C decision problems relate to complexity of analogous counting problems? –  Yaroslav Bulatov Oct 24 '10 at 17:24
    
@Yaroslav : Could you give a reference for this once it is written up? Thanks. –  gphilip Oct 29 '10 at 17:12
2  
Lol, I didn't actually discover it, I "found it" on on page 2 of Grohe's "Logic, Graphs, and Algorithms" –  Yaroslav Bulatov Oct 29 '10 at 20:29

An interesting property of minor-closed graph families is that they have bounded degeneracy. This means that all problems that are easy on graphs of bounded degeneracy are easy on graphs from a minor-closed family.

So, for example, finding if a graph contains a clique of size k is usually a hard problem and the best algorithms are like $O(n^k)$. However, if we know that the degeneracy is a constant, then k-cliques can be found in linear time, i.e., O(n) time. Wikipedia's article on the clique problem gives some information on this too. (The precise running time is something like $O(k d(G)^k n)$.) This algorithm is by Chiba and Nishizeki.

Other examples can be found in this answer by David Eppstein on MathOverflow to a similar question about graphs with bounded degeneracy.

share|improve this answer
4  
My paper arxiv.org/abs/1006.5440 has some more recent results on listing cliques with low degeneracy including the somewhat better runtime $O(dn3^{d/3})$ for listing all maximal cliques. –  David Eppstein Oct 23 '10 at 7:07
    
I cannot see what is a relation between minor-closed (your answer), and minor-excluded graphs (question). Also set of all complete graphs is minor closed, but they are not of bounded degeneracy. –  Saeed Oct 1 '13 at 9:32
    
Minor-closed = minor-excluded. All non-trivial minor-closed graph families have bounded degeneracy. I should have added "non-trivial" to my original statement. –  Robin Kothari Oct 3 '13 at 14:37
    
First of all minor closed != excluded minor (instead excluded minor $\subset$ minor closed), otherwise you can provide many new approximation and parametrized algorithms for many dense class of graphs. Also what is the non-trivial minor closed graphs? e.g graphs of treewidth at most f(|G|) are trivial or non-trivial? or class of dense graphs (which are minor closed and well quasi ordered), are trivial minor closed or non-trivial? Your definition is not clear, and reader cannot guess what's in your mind (and some part of your definitions are wrong as I stated at start). –  Saeed Oct 7 '13 at 14:38
    
I can tell you what I mean by a minor-closed graph family. $H$ is a minor of $G$ if $H$ can be obtained from $G$ by deleting edges, deleting isolated vertices or contracting edges. A graph family is a set of undirected unlabeled graphs $F$ (usually an infinite set). $F$ is a minor-closed family if for all $G$ in $F$, all minors of $G$ are also in $F$. A family is non-trivial if it is not the set of all graphs. Graphs of treewidth $k$ (for constant $k$) are minor-closed but graphs of treewidth $f(|G|)$ are not in general minor-closed. This is how I understand it. I could be mistaken of course. –  Robin Kothari Oct 8 '13 at 17:31

As a supplement, another useful property for algorithms on minor-excluded graphs is that these graphs have small separators. More precisely, due to

A linear time algorithm to find a separator in a graph excluding a minor, Bruce Reed and David R. Wood, ACM Transactions on Algorithms, 2009,

there is a linear time algorithm to find a separator of size $O(n^{2/3})$, or an $O(n^{3/2} + m)$ time algorithm to find a separator of size $O(n^{1/2})$.

Separators are good for dynamic programming techniques, and many NP-complete problems are shown to have fast algorithms with good approximation ratio, say the solution is within a constant factor of the optimal one, or even a PTAS. Planar graphs, and in general, bounded genus graphs are good starting points when trying to solve problems on minor-excluded graphs.

share|improve this answer
    
any idea if separators help with counting the number of proper colorings? –  Yaroslav Bulatov Oct 23 '10 at 3:18
1  
not really, maybe the paper mentioned by Ian helps better. An extension of the result is in "Approximation Algorithms via Contraction Decomposition" by the same authors in SODA '07. –  Hsien-Chih Chang 張顯之 Oct 23 '10 at 13:13

There are a number of papers showing various NP-hard problems can be approximated significantly better (either $O(1)$ or PTAS) on excluded-minor graphs than on general graphs. See, for instance:

Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring by Demaine, Hajiaghayi, and Kawarabayashi

This paper gives an algorithmic version of a certain (somewhat complex to explain) decomposition for excluded-minor graphs guaranteed by the Robertson & Seymour theorem, which yields a number of these improved approximation results. Also check out the references therein.

share|improve this answer
    
Thanks, that's pretty fascinating...I found a more accessible description of the decomposition algorithm in Grohe's "Logic, Graphs, and Algorithms" –  Yaroslav Bulatov Oct 23 '10 at 19:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.