Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
Tuukka Korhonen, Daniel Lokshtanov · Society for Industrial and Applied Mathematics eBooks · 2024
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 , where the OH(·)-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 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.