Minimum bisection split found faster with improved counting method

Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection

Data Structures and Algorithms

Summary

The minimum bisection problem asks if a large network can be split into two equal parts with only a few connections crossing between them. The authors developed a new method that solves this problem much faster than before, using a clever way to count possible splits instead of just checking if one exists. They built a special structure that breaks the network into pieces that are hard to split further, allowing their method to work efficiently. This improvement may help solve similar problems in graph analysis more quickly.

What this means in practice

  • For network engineers: Efficiently partition large communication networks into balanced halves with minimal link disruption using faster minimum bisection algorithms.
  • For parallel computing teams: Divide large computational tasks modeled as graphs evenly to minimize inter-process communication overhead using improved minimum bisection methods.

A theory result. No direct application yet.

Authors

Aditya Anand, Evangelos Kipouridis, Karol Węgrzycki

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.