Madathil, Jayakrishnan ;
Sharma, Roohani ;
Zehavi, Meirav
A SubExponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs
Abstract
Given an nvertex digraph D and a nonnegative 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, in general, is Whard as it is known to be NPhard even when k=0. We investigate the parameterized complexity of this problem on semicomplete digraphs. We show that Minimum Directed Bisection on semicomplete digraphs is one of a handful of problems that admit subexponential time fixedparameter tractable algorithms. That is, we show that the problem admits a 2^{O(sqrt{k} log k)}n^{O(1)} time 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^2)splitters. To the best of our knowledge, this is the first time such pseudorandom objects have been used in the design of kernels. We believe that the framework of designing kernels using splitters could be applied to more problems that admit subexponential time algorithms via chromatic coding. To complement the above mentioned results, we prove that Minimum Directed Bisection is NPhard on semicomplete digraphs, but polynomial time solvable on tournaments.
BibTeX  Entry
@InProceedings{madathil_et_al:LIPIcs:2019:10972,
author = {Jayakrishnan Madathil and Roohani Sharma and Meirav Zehavi},
title = {{A SubExponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {28:128:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10972},
URN = {urn:nbn:de:0030drops109721},
doi = {10.4230/LIPIcs.MFCS.2019.28},
annote = {Keywords: bisection, semicomplete digraph, tournament, fpt algorithm, chromatic coding, polynomial kernel, splitters}
}
20.08.2019
Keywords: 

bisection, semicomplete digraph, tournament, fpt algorithm, chromatic coding, polynomial kernel, splitters 
Seminar: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Issue date: 

2019 
Date of publication: 

20.08.2019 