2026-09-08T01:22:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26453 2026-09-05T19:44:11Z ddc:004 open_access

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 Odd-minor treewidth parameterized algorithm graph minor structural graph theory Odd-Cycle-Packing-treewidth Maximum Independent Set problem 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 have entries in {-1,0,1} and can be "tree-decomposed" into totally Δ-modular matrices with at most two non-zero entries per row. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mujin Choi and Maximilian Gorsky and Gunwoo Kim and Caleb McFarland and Sebastian Wiederrecht 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.64 urn:nbn:de:0030-drops-264533 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.64 eng https://creativecommons.org/licenses/by/4.0/legalcode