Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs

Florian Barbero 1 Christophe Paul 1 Michał Pilipczuk 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A simple digraph is semicomplete 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 semicomplete digraphs: cutwidth and optimal linear arrangement (Ola). We prove the following: (1) 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; (2) The cutwidth parameter admits a quadratic Turing kernel, whereas it does not admit any polynomial kernel unless NP ⊆ coNP/poly. By contrast, Ola admits a linear kernel. These results essentially complete the complexity analysis of computing cutwidth and Ola on semicomplete digraphs (with respect to standard parameters). Our techniques also can be used to analyze the sizes of minimal obstructions for having a small cutwidth under the induced subdigraph relation.
Type de document :
Article dans une revue
ACM Transactions on Algorithms, Association for Computing Machinery, 2018, 14 (3), pp.#38. 〈10.1145/3196276〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01919000
Contributeur : Christophe Paul <>
Soumis le : lundi 12 novembre 2018 - 10:10:57
Dernière modification le : samedi 16 février 2019 - 11:48:01

Lien texte intégral

Identifiants

Données associées

Collections

Citation

Florian Barbero, Christophe Paul, Michał Pilipczuk. Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs. ACM Transactions on Algorithms, Association for Computing Machinery, 2018, 14 (3), pp.#38. 〈10.1145/3196276〉. 〈lirmm-01919000〉

Partager

Métriques

Consultations de la notice

39