<p>An interesting property of minor-closed graph families is that they have bounded <a href="http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29" rel="nofollow noreferrer">degeneracy</a>. This means that all problems that are easy on graphs of bounded degeneracy are easy on graphs from a minor-closed family. </p>

<p>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. <a href="http://en.wikipedia.org/wiki/Clique_problem" rel="nofollow noreferrer">Wikipedia's article on the clique problem</a> gives some information on this too. (The precise running time is something like $O(k d(G)^k n)$.) This algorithm is by <a href="http://dx.doi.org/10.1137/0214017" rel="nofollow noreferrer">Chiba and Nishizeki</a>. </p>

<p>Other examples can be found in <a href="https://mathoverflow.net/questions/10468/algorithms-on-graphs-of-bounded-degeneracy-arboricity/11374#11374">this answer by David Eppstein</a> on MathOverflow to a similar question about graphs with bounded degeneracy.</p>

CC BY-SA 3.0
2013-10-01T09:32:13.917Z
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
CC BY-SA 3.0
2013-10-03T14:37:36.750Z
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
CC BY-SA 3.0
2013-10-07T14:38:31.117Z
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
CC BY-SA 3.0
2013-10-08T17:31:15.623Z
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
CC BY-SA 3.0
2013-10-10T12:44:24.537Z
OK, may be is better to say it in another way, by robertson and seymour result, every minor closed class of finite graphs, excludes finite set as obstruction, but there are two points: first their result is for finite graphs, and the class that I mentioned (tw < f(|G|)) is not necessary class of finite graph (class is infinite,and the graph *size* can also be infinite), On the other hand even if we consider just classes of finite graphs, their result causes to non-deterministic algorithm, while if we know (deterministically), something excludes a minor we can have deterministic approx, FPT,...
Saeed
CC BY-SA 2.5
2010-10-23T07:07:43.947Z
My paper http://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
CC BY-SA 2.5
2010-10-22T22:53:24.117Z
2010-10-22T22:53:24.117Z
2017-04-13T12:57:54.777Z
Robin Kothari
<p>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:</p>

<blockquote>
  <p><a href="http://www-math.mit.edu/~hajiagha/graphminoralgorithm.pdf" rel="noreferrer">Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring</a> by Demaine, Hajiaghayi, and Kawarabayashi</p>
</blockquote>

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

CC BY-SA 2.5
2010-10-23T19:07:10.083Z
Thanks, that's pretty fascinating...I found a more accessible description of the decomposition algorithm in Grohe's "Logic, Graphs, and Algorithms"
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-23T06:11:43.297Z
2010-10-23T06:11:43.297Z
Ian
<p>As a supplement, another useful property for algorithms on minor-excluded graphs is that these graphs have <strong>small separators</strong>. More precisely, due to </p>

<blockquote>
  <p><a href="http://www.ms.unimelb.edu.au/~woodd/papers/ReedWood-Separators.pdf" rel="noreferrer">A linear time algorithm to find a separator in a graph excluding a minor</a>,
  Bruce Reed and David R. Wood, ACM Transactions on Algorithms, 2009,</p>
</blockquote>

<p>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})$.</p>

<p>Separators are good for <em>dynamic programming</em> 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. 
<em>Planar graphs</em>, and in general, bounded genus graphs are good starting points when trying to solve problems on minor-excluded graphs.</p>

CC BY-SA 2.5
2010-10-23T03:18:36.267Z
any idea if separators help with counting the number of proper colorings?
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-23T13:13:58.290Z
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 張顯之
CC BY-SA 2.5
2010-10-23T02:42:22.830Z
2010-10-23T02:42:22.830Z
Hsien-Chih Chang 張顯之
<p>The most general result known is by Grohe.  A summary was presented in July 2010:</p>

<ul>
<li>Martin Grohe, <em>Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors</em>, LICS 2010.  (<a href="http://www2.informatik.hu-berlin.de/~grohe/pub/gro10.pdf" rel="nofollow">PDF</a>)</li>
</ul>

<p>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).</p>

<p><strike>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.</strike></p>

<hr>

<p><em>Edit:</em> 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?</p>

CC BY-SA 2.5
2010-10-22T19:27:41.050Z
Interesting...I wonder what this treelike decomposition looks like for planar graphs
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-24T17:24:55.520Z
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
CC BY-SA 2.5
2010-10-29T17:12:17.797Z
@Yaroslav : Could you give a reference for this once it is written up? Thanks.
gphilip
CC BY-SA 2.5
2010-10-29T20:29:38.217Z
Lol, I didn't actually discover it, I "found it" on on page 2 of Grohe's "Logic, Graphs, and Algorithms"
Yaroslav Bulatov
CC BY-SA 3.0
2010-10-22T19:21:59.707Z
2011-04-24T19:42:50.450Z
2011-04-24T19:42:50.450Z
András Salamon
<p>Approximating number of colorings seems to be easy on minor-excluded graphs using <a href="http://books.nips.cc/papers/files/nips20/NIPS2007_0781.pdf" rel="noreferrer">algorithm</a> by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded graphs?</p>

<p><b>Update 10/24</b>
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?</p>

<p> 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. </p>

<ds.algorithms><graph-theory><graph-minor>
what is easy for minor-excluded graphs?
Yaroslav Bulatov
# what is easy for minor-excluded graphs?

(Asked by: username_0 on 2010-10-22)

Approximating number of colorings seems to be easy on minor-excluded graphs using [algorithm](http://books.nips.cc/papers/files/nips20/NIPS2007_0781.pdf) 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.

**Tags:** ds.algorithms, graph-theory, graph-minor

---

## 4 answers

### Answer by username_6 on 2010-10-22. Score: 23 | Accepted answer

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](http://www2.informatik.hu-berlin.de/~grohe/pub/gro10.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?

> **Comments:**
> **username_0**: Interesting...I wonder what this treelike decomposition looks like for planar graphs  
> **username_0**: 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?  
> **username_7**: @Yaroslav : Could you give a reference for this once it is written up? Thanks.  
> **username_0**: Lol, I didn't actually discover it, I "found it" on on page 2 of Grohe's "Logic, Graphs, and Algorithms"  

---

### Answer by username_1 on 2010-10-22. Score: 18

An interesting property of minor-closed graph families is that they have bounded [degeneracy](http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29). 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](http://en.wikipedia.org/wiki/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](http://dx.doi.org/10.1137/0214017).

Other examples can be found in [this answer by David Eppstein](https://mathoverflow.net/questions/10468/algorithms-on-graphs-of-bounded-degeneracy-arboricity/11374#11374) on MathOverflow to a similar question about graphs with bounded degeneracy.

> **Comments:**
> **username_3**: My paper http://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.  
> **username_2**: 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.  
> **username_1**: Minor-closed = minor-excluded. All non-trivial minor-closed graph families have bounded degeneracy. I should have added "non-trivial" to my original statement.  
> **username_2**: 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).  
> **username_1**: 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.  
> **username_2**: OK, may be is better to say it in another way, by robertson and seymour result, every minor closed class of finite graphs, excludes finite set as obstruction, but there are two points: first their result is for finite graphs, and the class that I mentioned (tw < f(|G|)) is not necessary class of finite graph (class is infinite,and the graph *size* can also be infinite), On the other hand even if we consider just classes of finite graphs, their result causes to non-deterministic algorithm, while if we know (deterministically), something excludes a minor we can have deterministic approx, FPT,...  

---

### Answer by username_4 on 2010-10-23. Score: 15

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](http://www-math.mit.edu/~hajiagha/graphminoralgorithm.pdf) 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.

> **Comments:**
> **username_0**: Thanks, that's pretty fascinating...I found a more accessible description of the decomposition algorithm in Grohe's "Logic, Graphs, and Algorithms"  

---

### Answer by username_5 on 2010-10-23. Score: 15

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](http://www.ms.unimelb.edu.au/~woodd/papers/ReedWood-Separators.pdf),
> 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.

> **Comments:**
> **username_0**: any idea if separators help with counting the number of proper colorings?  
> **username_5**: 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.  

---

