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.


5 Answers 5


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?

  • 1
    $\begingroup$ Interesting...I wonder what this treelike decomposition looks like for planar graphs $\endgroup$ Commented Oct 22, 2010 at 19:27
  • 2
    $\begingroup$ 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? $\endgroup$ Commented Oct 24, 2010 at 17:24
  • $\begingroup$ @Yaroslav : Could you give a reference for this once it is written up? Thanks. $\endgroup$
    – gphilip
    Commented Oct 29, 2010 at 17:12
  • 3
    $\begingroup$ Lol, I didn't actually discover it, I "found it" on on page 2 of Grohe's "Logic, Graphs, and Algorithms" $\endgroup$ Commented Oct 29, 2010 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.

  • 5
    $\begingroup$ 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. $\endgroup$ Commented Oct 23, 2010 at 7:07
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Oct 1, 2013 at 9:32
  • $\begingroup$ Minor-closed = minor-excluded. All non-trivial minor-closed graph families have bounded degeneracy. I should have added "non-trivial" to my original statement. $\endgroup$ Commented Oct 3, 2013 at 14:37
  • $\begingroup$ 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). $\endgroup$
    – Saeed
    Commented Oct 7, 2013 at 14:38
  • $\begingroup$ 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. $\endgroup$ Commented Oct 8, 2013 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.

  • $\begingroup$ any idea if separators help with counting the number of proper colorings? $\endgroup$ Commented Oct 23, 2010 at 3:18
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 23, 2010 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.

  • $\begingroup$ Thanks, that's pretty fascinating...I found a more accessible description of the decomposition algorithm in Grohe's "Logic, Graphs, and Algorithms" $\endgroup$ Commented Oct 23, 2010 at 19:07

Planar Graph is only a special case of minor-fee graphs($K_5$ and $K_{3,3}$ minor free), the NP-hardness on planar graphs can't give the conclusion that it is also hard for other minor-free graphs.

For example, Parameterized Complexity of Independent Set in $H$-Free Graphs can have different performances depending on the structure of $H$ [1].

Hadwiger’s Conjecture asserts that every $K_t$-minor-free graph has a proper $(t-1)$-colouring. For the most recent work,Heuvel and Wood [2] shows that every $K_t$-minor-free graph is $(t-1)$-colourable with monochromatic degree at most $t− 2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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