Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable DecompositionResearch Paper
Minimum Bisection asks whether the vertex set of a graph can be split into two halves, up to one vertex, with at most edges between them. It is the unweighted two-part case of the graph-partitioning problem of Kernighan and Lin (1970) and is NP-complete (Garey, Johnson and Stockmeyer, 1976). Parameterized by the cut size , it became a test case for the…