← 研踪 PaperTrailarXiv:2611.08202 · v1
Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection
计数不可分解分解:最小二分问题的单指数参数化算法
首次提交 2026-11-05 23:54
版本更新 2026-11-05 23:54
雷达观测 2026-11-06 12:09
摘要
The Minimum Bisection problem asks whether an -vertex graph can be split into two halves with at most edges between them. We give a single exponential time algorithm for minimum bisection, running in time . This improves the previous bound of due to Cygan, Komosa, Lokshtanov, Pilipczuk, Pilipczuk, Saurabh, and Wahlström (TALG 2021). Our algorithm counts solutions instead of only finding if one exists. We show that our dynamic program can be implemented on top of an unbreakable decomposition using algebraic techniques. Along the way, we compute in time a tree decomposition with adhesions of size at most whose bags are -edge-unbreakable inside their own subtrees.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 23:54 · 最新观测版本
Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection
The Minimum Bisection problem asks whether an -vertex graph can be split into two halves with at most edges between them. We give a single exponential time algorithm for minimum bisection, running in time . This improves the previous bound of due to Cygan, Komosa, Lokshtanov, Pilipczuk, Pilipczuk, Saurabh, and Wahlström (TALG 2021). Our algorithm counts solutions instead of only finding if one exists. We show that our dynamic program can be implemented on top of an unbreakable decomposition using algebraic techniques. Along the way, we compute in time a tree decomposition with adhesions of size at most whose bags are -edge-unbreakable inside their own subtrees.
查看此版本解读 →查看此版本原文 ↗