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
| CREATOR | 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, |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 372 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-10019