arXiv preprint ·
Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Minimum Bisection problem asks whether an $n$-vertex graph can be split into two halves with at most $k$ edges between them. We give a single exponential time algorithm for minimum bisection, running in time $2^{O(k)}n^{O(1)}$. This improves the previous bound of $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 $2^{O(k)}n^{O(1)}$ a tree decomposition with adhesions of size at most $2k$ whose bags are $(3k,k)$-edge-unbreakable inside their own subtrees.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quadratic-Time Barriers from Self-Referential SAT
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
GreedTok is a Constant-Factor Approximation for Partition-Cover Tokenization
Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant
Constant-Factor Approximation Algorithms for Weighted Budgeted Multisensor Sweep Coverage
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.