文章基本信息

标题：Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs
本地全文：下载
作者：Florian Barbero ; Christophe Paul ; Michal Pilipczuk 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：70:1-70:13
DOI：10.4230/LIPIcs.ICALP.2017.70
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A simple digraph is semi-complete if for any two of its vertices u and v, at least one of the arcs (u,v) and (v,u) is present. We study the complexity of computing two layout parameters of semi-complete digraphs: cutwidth and optimal linear arrangement (OLA). We prove that: -Both parameters are NP-hard to compute and the known exact and parameterized algorithms for them have essentially optimal running times, assuming the Exponential Time Hypothesis. - The cutwidth parameter admits a quadratic Turing kernel, whereas it does not admit any polynomial kernel unless coNP/poly contains NP. By contrast, OLA admits a linear kernel. These results essentially complete the complexity analysis of computing cutwidth and OLA on semi-complete digraphs. Our techniques can be also used to analyze the sizes of minimal obstructions for having small cutwidth under the induced subdigraph relation.
关键词：cutwidth; OLA; tournament; semi-complete digraph