文章基本信息

标题：A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs
本地全文：下载
作者：Jayakrishnan Madathil ; Roohani Sharma ; Meirav Zehavi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-14
DOI：10.4230/LIPIcs.MFCS.2019.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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, in general, is W-hard as it 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 on semicomplete digraphs is one of a handful of problems that admit sub-exponential time fixed-parameter 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 sub-exponential time algorithms via chromatic coding. To complement the above mentioned results, we prove that Minimum Directed Bisection is NP-hard on semicomplete digraphs, but polynomial time solvable on tournaments.
关键词：bisection; semicomplete digraph; tournament; fpt algorithm; chromatic coding; polynomial kernel; splitters