Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918200357158912 |
|---|---|
| author | Choi, Mujin Gorsky, Maximilian Kim, Gunwoo McFarland, Caleb Wiederrecht, Sebastian |
| author_facet | Choi, Mujin Gorsky, Maximilian Kim, Gunwoo McFarland, Caleb Wiederrecht, Sebastian |
| contents | 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 implies bounded OCP-tw. This structural result is constructive and implies a 2^(poly(k))poly(n)-time parameterized poly(k)-approximation algorithm for OCP-tw.
Moreover, we show that the (weighted) Maximum Independent Set problem (MIS) can be solved in polynomial time on graphs of bounded OCP-tw. Finally, we lift the concept of OCP-tw to a parameter for matrices of integer programs. To this end, we show that our strategy can be applied to efficiently solve integer programs whose matrices can be "tree-decomposed" into totally delta-modular matrices with at most two non-zero entries per row. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_10019 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes Choi, Mujin Gorsky, Maximilian Kim, Gunwoo McFarland, Caleb Wiederrecht, Sebastian Combinatorics Discrete Mathematics 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 implies bounded OCP-tw. This structural result is constructive and implies a 2^(poly(k))poly(n)-time parameterized poly(k)-approximation algorithm for OCP-tw. Moreover, we show that the (weighted) Maximum Independent Set problem (MIS) can be solved in polynomial time on graphs of bounded OCP-tw. Finally, we lift the concept of OCP-tw to a parameter for matrices of integer programs. To this end, we show that our strategy can be applied to efficiently solve integer programs whose matrices can be "tree-decomposed" into totally delta-modular matrices with at most two non-zero entries per row. |
| title | Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2511.10019 |