what is easy for minor-excluded graphs?

Question

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.

Answer 1

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?

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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$.