Metraipolis › archive › dc_57bcdf269305
Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition — arXiv:2611.05982
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05982
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:36.033Z
- SHA-256 of the archived text
8235576a99ac6c8b5cf482ef7e15f82c0db7bc5e474e4982e9efe1edfc472f22- Stable URL of this page
https://metraipolis.com/documento/dc_57bcdf269305
How to cite
Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition — arXiv:2611.05982 — arXiv (en), https://arxiv.org/abs/2611.05982 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_57bcdf269305 (Metraipolis archive dc_57bcdf269305, sha256 8235576a99ac6c8b5cf482ef7e15f82c0db7bc5e474e4982e9efe1edfc472f22)
BibTeX
@misc{dc57bcdf269305,
title = {Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition — arXiv:2611.05982},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05982},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_57bcdf269305; sha256 8235576a99ac6c8b5cf482ef7e15f82c0db7bc5e474e4982e9efe1edfc472f22},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05982. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Minimum Bisection asks whether the vertices of a graph can be partitioned into two parts whose sizes differ by at most one and with at most k edges between the two parts. Cygan, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saurabh (SICOMP 2019) gave the first fixed-parameter algorithm, which runs in O*(2^(O(k^3))) time, by introducing an unbreakable decomposition. Cygan, Komosa, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saurabh, and Wahlström (TALG 2021) strengthened the decomposition and improved the running time to O*(2^(O(k log k))). However, whether the running time could be improved to single-exponential remained open. In this paper, we give a deterministic O*(2^(O(k)))-time algorithm for Minimum Bisection. Our algorithm also counts all feasible bisections. To obtain an O*(2^(O(k)))-time algorithm, we introduce two new techniques. First, we give a new algorithm that computes a (2k,k)-edge-unbreakable decomposition with adhesion at most 2k in O*(2^(O(k))) time by relaxing the unbreakability and adhesion guarantees of the decomposition in (TALG 2021). Second, we improve the running time of the dynamic program over the decomposition from O*(2^(O(k log k))) to O*(2^(O(k))) using important cuts, inclusion-exclusion, and formal logarithms and exponentials. Together with color coding, the same techniques give a deterministic O*(2^(O(k)))-time algorithm for Matching Cut, which asks for a cut whose crossing edges form a matching. This improves the O*(2^(O(k log k)))-time algorithm of Aravind and Saxena (IWOCA 2021). Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2611.05982 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-05T18:21:04.025Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).