Madathil, JayakrishnanJayakrishnanMadathilSharma, RoohaniRoohaniSharmaZehavi, MeiravMeiravZehavi2025-08-312025-08-312021-06-0110.1007/s00453-021-00806-x2-s2.0-85100707821https://d8.irins.org/handle/IITG2025/25420Given 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.falseBisection | Chromatic coding | FPT Algorithm | Polynomial kernel | Semicomplete digraph | Splitters | TournamentArticle143205411861-1884June 20211arJournal0