Skip to Main content Skip to Navigation
Conference papers

Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02021567
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Wednesday, June 30, 2021 - 12:53:42 PM
Last modification on : Monday, October 11, 2021 - 1:24:09 PM
Long-term archiving on: : Friday, October 1, 2021 - 6:30:01 PM

File

LIPIcs-ICALP-2017-70.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Florian Barbero, Christophe Paul, Michał Pilipczuk. Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Jul 2017, Warsaw, Poland. pp.70:1--70:13, ⟨10.4230/LIPIcs.ICALP.2017.70⟩. ⟨lirmm-02021567⟩

Share

Metrics

Record views

215

Files downloads

30