- If G excludes a fixed minor H, then G has O(n) edges
- If G excludes a fixed minor H, then G has O(\sqrt{n}) treewidth
- If G excludes a fixed minor H, then G has a nice decomposition into a few graphs of small treewidth
- If G excludes a fixed minor H, then G can be decomposed into a clique sum of graphs that are almost embeddable on surfaces of bounded genus.
(all of these and more in Jeff Erickson's excellent comp. topology notes).
In all these cases, the O() notation hides terms that depend on the excluded graph H. for example, if H is a clique on k vertices, then G has at most O(nk\sqrt{log k}) edges.
So the question is: given a graph G, what's the smallest graph H that G excludes ? This problem is almost certainly NP-hard, and probably at least somewhat hard to approximate, but some approximation of the smallest graph (measured by edges or vertices) might be useful.
I was asked this question during our algorithms seminar a few days ago, and didn't have an answer.
Oooooooh, parametric complexity!? A bunch of my colleagues in Jena were heavily into these things!
ReplyDeleteIt's definitely NP-hard to find the smallest excluded minor if you measure "smallest" by number of vertices: http://arxiv.org/abs/0807.0007
ReplyDeleteFor a fixed H, there is a polynomial time algorithm via Robertson-Seymour (n^3 time and dependence on |H| is terrible) that checks if G excludes H. Thus, for a fixed constant k, one can in polynomial time check whether G excludes any H-minor with |V(H)| <= k. Basically try all graphs of size <= k. Essentially the problem is fixed parameter tractable.
ReplyDeleteOn the other hand, the general problem where one wants to find the smallest H that is excluded in G is as hard as clique. More precisely, it is NP-Hard to distinguish whether a given graph has a clique of size n^{1-\eps} or less than n^{\eps}. If G has a clique of size n^{1-\eps} then it includes a minor for every graph of size n^{1-\eps}. If G has no clique of size more than n^{\eps} than clearly G excludes a clique of this size. So the problem is hard to approximate to within n^{1-\eps} for every \eps > 0.
Chandra: true, although I was asking because someone actually wanted an algorithm :). the RS route is hopeless.
ReplyDeleteregarding the approximability though, see David's link above. The problem of finding a largest clique *minor* is actually easier than finding a largest clique subgraph. In his paper, he cites a paper by Alon, Lingas and Wahlen that shows a sqrt{n} approximation for this number (called the Hadwiger number)