Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition

A graph G contains a graph H as an induced minor if H can be obtained from G by vertex deletions and edge contractions. The class of H-induced-minor-free graphs generalizes the class of H-minor-free graphs, but unlike H-minor-free graphs, it can contain dense graphs. We show that if an n-vertex m-edge graph G does not contain a graph H as an induced minor, then it has a balanced vertex separator of size O H ( √ m), where the O H (•)notation hides factors depending on H. More precisely, our upper bound for the size of the balanced separator is

We give an algorithm for finding either an induced minor model of H in G or such a separator in randomized polynomial-time. We apply this to obtain subexponential 2 O H (n 2/3 log n) time algorithms on H-induced-minor-free graphs for a large class of problems including maximum independent set, minimum feedback vertex set, 3-coloring, and planarization.

For graphs H where every edge is incident to a vertex of degree at most 2, our results imply a 2 O H (n 2/3 log n) time algorithm for testing if G contains H as an induced minor. Our second main result is that there exists a fixed tree T , so that there is no 2 o(n/ log 3 n) time algorithm for testing if a given n-vertex graph contains T as an induced minor unless the Exponential Time Hypothesis (ETH) fails. Our reduction also gives NP-hardness, which solves an open problem asked by Fellows, Kratochvíl, Middendorf, and Pfeiffer [Algorithmica, 1995], who asked if there exists a fixed planar graph H so that testing for H as an induced minor is NP-hard.