A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs

Abstract

Given an n-vertex digraph D and a non-negative integer k, the Minimum Directed Bisection problem asks if the vertices of D can be partitioned into two parts, say L and R, such that |L| and |R| difer by at most 1 and the number of arcs from R to L is at most k. This problem is known to be NP-hard even when k = 0. We investigate the parameterized complexity of this problem on semicomplete digraphs. We show that Minimum Directed Bisection admits a sub-exponential time fxedparameter tractable algorithm on semicomplete digraphs. We also show that Minimum Directed Bisection admits a polynomial kernel on semicomplete digraphs. To design the kernel, we use (n, k, k2)-splitters, which, to the best of our knowledge, have never been used before in the design of kernels. We also prove that Minimum Directed Bisection is NP-hard on semicomplete digraphs, but polynomial time solvable on tournaments.