# what is easy for minor-excluded graphs?

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.

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?

• Interesting...I wonder what this treelike decomposition looks like for planar graphs – Yaroslav Bulatov Oct 22 '10 at 19:27
• 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
• 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.

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

• any idea if separators help with counting the number of proper colorings? – Yaroslav Bulatov Oct 23 '10 at 3:18
• 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.

• 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

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

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  shows that every $$K_t$$-minor-free graph is $$(t-1)$$-colourable with monochromatic degree at most $$t− 2$$.