Prof. Meirav Zehavi

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| differ 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 fixed-parameter 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, k²) -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.