Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability

Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh +1

In the Minimum Bisection problem, input is a graph $G$ and the goal is to partition the vertex set into two parts $A$ and $B$, such that $||A|-|B||\le 1$ and the number $k$ of edg…