Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes
Mujin Choi, Maximilian Gorsky, Gunwoo Kim, Caleb McFarland, Sebastian Wiederrecht
我们引入了基于树分解的图形参数Odd-Cycle-Packing-treewidth(OCP-tw)作为宽度参数,要求将给定的图形分解成边界奇循环包装号的碎片。 OCP-tw参数在奇数关系下是单调的,我们为OCP-tw的Robertson和Seymour的著名网格定理提供了一个类似物。 也就是说,我们确定了两个网格状图形的无限家族,它们作为奇数微小的存在意味着大型OCP-tw,并证明它们的缺失意味着有边界的OCP-tw。 这种结构结果是建设性的,意味着OCP-tw的2^(poly(k))poly(n)-时间参数化poly(k)-近似算法。 此外,我们表明(加权)最大独立设置问题(MIS)可以在有边界的OCP-tw的图形上的多项式时间解决。 最后,我们将 OCP-tw 的概念提升为整数程序矩阵的参数。 为此,我们表明,我们的策略可以应用于有效地解决整数程序,这些矩阵可以“树分解”成完全delta-modular矩阵,每行最多两个非零条目。
We introduce the tree-decomposition-based graph parameter Odd-Cycle-Packing-treewidth (OCP-tw) as a width parameter that asks to decompose a given graph into pieces of bounded odd cycle packing number. The parameter OCP-tw is monotone under the odd-minor-relation and we provide an analogue to the celebrated Grid Theorem of Robertson and Seymour for OCP-tw. That is, we identify two infinite families of grid-like graphs whose presence as odd-minors implies large OCP-tw and prove that their absence...
