跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

The Minimum Bisection problem asks whether an nn-vertex graph can be split into two halves with at most kk edges between them. We give a single exponential time algorithm for minimum bisection, running in time 2O(k)nO(1)2^{O(k)}n^{O(1)}. This improves the previous bound of 2O(klog⁡k)nO(1)2^{O(k\log k)}n^{O(1)} 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 2O(k)nO(1)2^{O(k)}n^{O(1)} a tree decomposition with adhesions of size at most 2k2k whose bags are (3k,k)(3k,k)-edge-unbreakable inside their own subtrees.

AI 论文解读

基于摘要 · 非全文审阅

作者提出一个运行时间为 2^{O(k)}n^{O(1)} 的最小二分参数化算法,并能在不可分解分解上计数解。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 nn-vertex graph can be split into two halves with at most kk edges between them. We give a single exponential time algorithm for minimum bisection, running in time 2O(k)nO(1)2^{O(k)}n^{O(1)}. This improves the previous bound of 2O(klog⁡k)nO(1)2^{O(k\log k)}n^{O(1)} 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 2O(k)nO(1)2^{O(k)}n^{O(1)} a tree decomposition with adhesions of size at most 2k2k whose bags are (3k,k)(3k,k)-edge-unbreakable inside their own subtrees.

查看此版本解读 →查看此版本原文 ↗