Document Open Access Logo

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

Authors Florian Barbero, Christophe Paul, Michal Pilipczuk

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2017.70.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • cutwidth
  • OLA
  • tournament
  • semi-complete digraph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Florian Barbero, Christophe Paul, and Michal Pilipczuk. Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.70

Author Details

Florian Barbero
Christophe Paul
Michal Pilipczuk

References

  1. Jørgen Bang-Jensen and Gregory Gutin. Digraphs - theory, algorithms and applications. Springer, 2002. Google Scholar
  2. Daniel Binkele-Raible, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Kernel(s) for problems with no kernel: On out-trees with many leaves. ACM Transactions on Algorithms, 8(4):38, 2012. Google Scholar
  3. Maria Chudnovsky, Alexandra Fradkin, and Paul Seymour. Tournament immersion and cutwidth. Journal of Combinatorial Theory, Series B, 102(1):93-101, 2012. Google Scholar
  4. Maria Chudnovsky and Paul Seymour. A well-quasi-order for tournaments. Journal of Combinatorial Theory, Series B, 101(1):47-53, 2011. Google Scholar
  5. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  7. Andrew Drucker. New limits to classical and quantum instance compression. SIAM journal of Computing, 44(5):1443-1479, 2015. Google Scholar
  8. Fedor V. Fomin and Michał Pilipczuk. Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. In ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 505-516. Springer, 2013. Google Scholar
  9. Alexandra Fradkin. Forbidden structures and algorithms in graphs and digraphs. PhD thesis, Princeton University, 2011. Google Scholar
  10. Alexandra Ovetsky Fradkin and Paul D. Seymour. Edge-disjoint paths in digraphs with bounded independence number. Journal of Combinatorial Theory, Series B, 110:19-46, 2015. Google Scholar
  11. Valentin Garnero and Mathias Weller. Parameterized certificate dispersal and its variants. Theoretical Computer Science, 622:66-78, 2016. Google Scholar
  12. Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: obstructions and algorithmic aspects. CoRR, abs/1606.05975, 2016. To appear in Proceedings of IPEC 2016. Google Scholar
  13. Danny Hermelin, Stefan Kratsch, Karolina Sołtys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (Turing) kernelization. Algorithmica, 71(3):702-730, 2015. Google Scholar
  14. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  15. Bart M. P. Jansen. Turing kernelization for finding long paths and cycles in restricted graph classes. Journal of Computer and System Sciences, 85:18-37, 2017. Google Scholar
  16. Michał Pilipczuk. Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. In STACS 2013, volume 20 of LIPIcs, pages 197-208. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. Google Scholar
  17. Michał Pilipczuk. Tournaments and optimality: new results in parameterized complexity. PhD thesis, University of Bergen, Norway, 2013. Google Scholar
  18. Alexander Schäfer, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. Parameterized computational complexity of finding small-diameter subgraphs. Optimization Letters, 6(5):883-891, 2012. Google Scholar
  19. Thomas J. Shaefer. The complexity of satisfiability problems. In STOC 1978, pages 216-226. ACM, 1978. Google Scholar
  20. Robin Thomas. A menger-like property of tree-width: the finite case. Journal of Combinatorial Theory Series B, 48(1):67-76, 1990. Google Scholar
  21. Stéphan Thomassé, Nicolas Trotignon, and Kristina Vušković. A polynomial Turing-kernel for Weighted Independent Set in bull-free graphs. Algorithmica, 77(3):619-641, 2017. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact