Document Open Access Logo

Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number

Authors Pranabendu Misra, Saket Saurabh, Roohani Sharma, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.35.pdf
  • Filesize: 0.7 MB
  • 19 pages

Document Identifiers

Author Details

Pranabendu Misra
  • University of Bergen, Norway
Saket Saurabh
  • Institute of Mathematical Sciences, HBNI, India
Roohani Sharma
  • Institute of Mathematical Sciences, HBNI, India
Meirav Zehavi
  • Ben-Gurion University, Beersheba, Israel

Cite AsGet BibTex

Pranabendu Misra, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.35

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • sub-exponential fixed-parameter tractable algorithms
  • directed feedback arc set
  • directed cutwidth
  • optimal linear arrangement
  • bounded independence number digraph

Metrics

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

References

  1. Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5):23:1-23:27, 2008. Google Scholar
  2. Noga Alon. Ranking Tournaments. SIAM J. Discrete Math., 20(1):137-142, 2006. Google Scholar
  3. Noga Alon, Daniel Lokshtanov, and Saket Saurabh. Fast FAST. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, pages 49-58, 2009. Google Scholar
  4. Jørgen Bang-Jensen and Carsten Thomassen. A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs. SIAM J. Discrete Math., 5(3):366-376, 1992. Google Scholar
  5. 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, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 70:1-70:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  6. Pierre Charbit, Stéphan Thomassé, and Anders Yeo. The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments. Combinatorics, Probability & Computing, 16(1):1-4, 2007. Google Scholar
  7. Maria Chudnovsky, Alexandra Ovetsky Fradkin, and Paul D. Seymour. Tournament immersion and cutwidth. J. Comb. Theory, Ser. B, 102(1):93-101, 2012. Google Scholar
  8. Maria Chudnovsky and Paul D. Seymour. A well-quasi-order for tournaments. J. Comb. Theory, Ser. B, 101(1):47-53, 2011. Google Scholar
  9. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  10. Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truß. Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms, 8(1):76-86, 2010. Google Scholar
  11. Uriel Feige. Faster FAST(Feedback Arc Set in Tournaments). CoRR, abs/0911.5094, 2009. URL: http://arxiv.org/abs/0911.5094.
  12. Fedor V. Fomin and Michal Pilipczuk. Jungles, bundles, and fixed parameter tractability. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 396-413, 2013. Google Scholar
  13. Fedor V. Fomin and Michal Pilipczuk. Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 505-516, 2013. Google Scholar
  14. Alexandra Ovetsky Fradkin and Paul D. Seymour. Tournament pathwidth and topological containment. J. Comb. Theory, Ser. B, 103(3):374-384, 2013. Google Scholar
  15. Alexandra Ovetsky Fradkin and Paul D. Seymour. Edge-disjoint paths in digraphs with bounded independence number. J. Comb. Theory, Ser. B, 110:19-46, 2015. Google Scholar
  16. T Gallai and AN Milgram. Verallgemeinerung eines graphentheoretischen Satzes von Rédei. Acta Sc. Math, 21:181-186, 1960. Google Scholar
  17. Marek Karpinski and Warren Schudy. Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, pages 3-14, 2010. Google Scholar
  18. Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 95-103, 2007. Google Scholar
  19. Mithilesh Kumar and Daniel Lokshtanov. Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 49:1-49:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  20. Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh. A 7/3-Approximation for Feedback Vertex Sets in Tournaments. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 67:1-67:14, 2016. Google Scholar
  21. Michal Pilipczuk. Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. In 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, volume 20 of LIPIcs, pages 197-208. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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