Odd-Minors I: 排除小奇偶破裂 (Odd-Minors I: Excluding small parity breaks)

Given a graph class~$\mathcal{C}$, the $\mathcal{C}$-blind-treewidth of a graph~$G$ is the smallest integer~$k$ such that~$G$ has a tree-decomposition where every bag whose torso does not belong to~$\mathcal{C}$ has size at most~$k$. In this paper we focus on the class~$\mathcal{B}$ of bipartite graphs and the class~$\mathcal{P}$ of planar graphs together with the odd-minor relation. For each of the two parameters, $\mathcal{B}$-blind-treewidth and ${(\mathcal{B}\cup\mathcal{P})}$-blind-treewidth, we prove an analogue of the celebrated Grid Theorem under the odd-minor relation. As a consequence we obtain FPT-approximation algorithms for both parameters. We then provide FPT-algorithms for \textsc{Maximum Independent Set} on graphs of bounded $\mathcal{B}$-blind-treewidth and \textsc{Maximum Cut} on graphs of bounded ${(\mathcal{B}\cup\mathcal{P})}$-blind-treewidth.

翻译：给定一个图类~$\mathcal{C}$，一个图~$G$ 的 $\mathcal{C}$-盲树宽是指只要~$G$ 有一棵树分解，树分解的每个包袋——不属于~$\mathcal{C}$ 的躯干——都至多有~$k$ 个元素。在本文中，我们关注双分图类~$\mathcal{B}$ 和平面图类~$\mathcal{P}$ 然后结合在奇小子的约束下。对于以上两个参数 $\mathcal{B}$-盲树宽和 ${(\mathcal{B}\cup\mathcal{P})}$-盲树宽，我们证明了在奇小子约束下,奇数行列覆盖定理类似地推论出来。由此我们获得了对于这两个参数的 FPT-近似算法。然后我们提供了对于定界 $\mathcal{B}$-盲树宽的图的最大独立集问题和对于定界 ${(\mathcal{B}\cup\mathcal{P})}$-盲树宽的图的最大割问题的 FPT-算法。