Odd-Minors I: Excluding small parity breaks
share
Given an annotated graph class 𝒞, the 𝒞-blind-treewidth of a graph G is the smallest integer k such that G has a tree-decomposition where, for every t∈ V(T), if the annotated graph (G,β(t)) does not belong to 𝒞, then β(t) has size at most k. In this paper we focus on the annotated class ℬ of “globally bipartite” subgraphs and the class 𝒫 of “globally planar” subgraphs together with the relation. For each of the two parameters, ℬ-blind-treewidth and (ℬ∪𝒫)-blind-treewidth, we prove an analogue of the celebrated Grid Theorem under the relation. As a consequence we obtain FPT-approximation algorithms for both parameters. We then provide FPT-algorithms for Maximum Independent Set on graphs of bounded ℬ-blind-treewidth and Maximum Cut on graphs of bounded (ℬ∪𝒫)-blind-treewidth.
READ FULL TEXT