Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
share
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 O(min(|V(H)|^2, log n) ·√(|V(H)|+|E(H)|)·√(m)). 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/3log 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/3log 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.
READ FULL TEXT