Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes

Mujin Choi ​ Department of Mathematical Sciences, KAIST, Daejeon, South Korea Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Maximilian Gorsky ​ Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Gunwoo Kim ​ School of Computing, · 2025

Read Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes by Mujin Choi ​ Department of Mathematical Sciences, KAIST, Daejeon, South Korea Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Maximilian Gorsky ​ Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Gunwoo Kim ​ School of Computing, (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-10019.txt.

Introduction

Mujin Choi, Maximilian Gorsky, Gunwoo Kim, Caleb McFarland, and Sebastian Wiederrecht introduce a new graph width parameter based on packing odd cycles. Treewidth measures how tree-like a graph is; their variant decomposes a graph into pieces whose odd cycle packing number stays bounded. The parameter is monotone under odd minors, the natural containment relation for this setting, which makes a grid theorem plausible.

The authors prove that analogue of the Robertson-Seymour grid theorem: two families of grid-like graphs force large width when present as odd minors, and their absence bounds the width. The structural result is constructive and yields a fast parameterized approximation algorithm. As a payoff, maximum independent set becomes polynomial-time solvable on graphs of bounded width, and the idea extends to integer programming matrices.

Catalog record

CREATORMujin Choi ​ Department of Mathematical Sciences, KAIST, Daejeon, South Korea Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Maximilian Gorsky ​ Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Gunwoo Kim ​ School of Computing,
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE372 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-10019

Browse the full library · About the Tower of Babel