文章基本信息

标题：Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
本地全文：下载
作者：Pranabendu Misra ; Saket Saurabh ; Roohani Sharma 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：122
页码：1-19
DOI：10.4230/LIPIcs.FSTTCS.2018.35
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Fradkin and Seymour [Journal of Combinatorial Graph Theory, Series B, 2015] defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk [ESA, 2013], where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is that the yes-instances of the problems above have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, an inductive argument and structural properties of the digraphs.
关键词：sub-exponential fixed-parameter tractable algorithms; directed feedback arc set; directed cutwidth; optimal linear arrangement; bounded independence n