Document Open Access Logo

Going Far From Degeneracy

Authors Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.47.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
Daniel Lokshtanov
  • Department of Computer Science, University of California Santa Barbara, USA
Fahad Panolan
  • Department of Computer Science and Engineering, IIT Hyderabad, India
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Meirav Zehavi
  • Ben-Gurion University, Beersheba, Israel

Funding

The research leading to these results has received funding from the Research Council of Norway via the projects "CLASSIS" and "MULTIVAL" and from the European Research Council (ERC) via grant LOPPRE, reference 819416.

Acknowledgements

We thank Nikolay Karpov for communicating to us the question of finding a path above the degeneracy bound and Proposition 15.

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Going Far From Degeneracy. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.47

Abstract

An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdős and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least d+1. The proof of Erdős and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d+1. But can we decide in polynomial time whether a graph contains a cycle of length at least d+2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d+k can be done in time 2^{O(k)}|V(G)|^O(1). In other words, deciding whether a 2-connected n-vertex G contains a cycle of length at least d+log{n} can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least d+1 is NP-complete. However, we prove that if graph G is connected, then deciding whether G contains a path of length at least d+k can be done in time 2^{O(k)}n^O(1). We complement these results by showing that the choice of degeneracy as the "above guarantee parameterization" is optimal in the following sense: For any epsilon>0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracy d has a path (cycle) of length at least (1+epsilon)d.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Longest path
  • longest cycle
  • fixed-parameter tractability
  • above guarantee parameterization

Metrics

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

Related Versions

References

  1. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Solving MAX-r-SAT Above a Tight Lower Bound. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 511-517. SIAM, 2010. Google Scholar
  2. Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding Detours is Fixed-parameter Tractable. CoRR, abs/1607.07737, 2016. URL: http://arxiv.org/abs/1607.07737,
  3. Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding Detours is Fixed-Parameter Tractable. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, volume 80 of LIPIcs, pages 54:1-54:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  4. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. CoRR, abs/1007.1161, 2010. URL: http://arxiv.org/abs/1007.1161.
  5. Hans L. Bodlaender. On Linear Time Minor Tests with Depth-First Search. J. Algorithms, 14(1):1-23, 1993. URL: https://doi.org/10.1006/jagm.1993.1001.
  6. Jianer Chen, Joachim Kneis, Songjian Lu, Daniel Mölle, Stefan Richter, Peter Rossmanith, Sing-Hoi Sze, and Fenghui Zhang. Randomized divide-and-conquer: improved path, matching, and packing algorithms. SIAM J. Comput., 38(6):2526-2547, 2009. URL: https://doi.org/10.1137/080716475.
  7. Jianer Chen, Songjian Lu, Sing-Hoi Sze, and Fenghui Zhang. Improved algorithms for path, matching, and packing problems. In Proceedings of the18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 298-307. SIAM, 2007. Google Scholar
  8. Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 24 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43-54, Dagstuhl, Germany, 2013. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  9. 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
  10. G. A. Dirac. Some theorems on abstract graphs. Proc. London Math. Soc. (3), 2:69-81, 1952. Google Scholar
  11. P. Erdős and T. Gallai. On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar, 10:337-356 (unbound insert), 1959. Google Scholar
  12. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: https://doi.org/10.1145/2886094.
  13. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Long directed (s, t)-path: FPT algorithm. Inf. Process. Lett., 140:8-12, 2018. URL: https://doi.org/10.1016/j.ipl.2018.04.018.
  14. Harold N. Gabow and Shuxin Nie. Finding a long directed cycle. ACM Transactions on Algorithms, 4(1), 2008. URL: https://doi.org/10.1145/1328911.1328918.
  15. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  16. Shivam Garg and Geevarghese Philip. Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above a Higher Guarantee. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1152-1166. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch80.
  17. Gregory Gutin, Eun Jung Kim, Michael Lampis, and Valia Mitsou. Vertex Cover Problem Parameterized Above and Below Tight Bounds. Theory of Computing Systems, 48(2):402-410, 2011. URL: https://doi.org/10.1007/s00224-010-9262-y.
  18. Gregory Gutin, Leo van Iersel, Matthias Mnich, and Anders Yeo. Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. J. Computer and System Sciences, 78(1):151-163, 2012. URL: https://doi.org/10.1016/j.jcss.2011.01.004.
  19. Gregory Z. Gutin and Viresh Patel. Parameterized Traveling Salesman Problem: Beating the Average. SIAM J. Discrete Math., 30(1):220-238, 2016. Google Scholar
  20. Gregory Z. Gutin, Arash Rafiey, Stefan Szeider, and Anders Yeo. The Linear Arrangement Problem Parameterized Above Guaranteed Value. Theory Comput. Syst., 41(3):521-538, 2007. URL: https://doi.org/10.1007/s00224-007-1330-6.
  21. Frank Harary. A characterization of block-graphs. Canad. Math. Bull., 6:1-6, 1963. Google Scholar
  22. Falk Hüffner, Sebastian Wernicke, and Thomas Zichner. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection. Algorithmica, 52(2):114-132, 2008. URL: https://doi.org/10.1007/s00453-007-9008-7.
  23. Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith. Divide-and-Color. In Proceedings of the 34th International Workshop Graph-Theoretic Concepts in Computer Science (WG), volume 4271 of Lecture Notes in Computer Science, pages 58-67. Springer, 2008. Google Scholar
  24. Ioannis Koutis. Faster Algebraic Algorithms for Path and Packing Problems. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), volume 5125 of Lecture Notes in Comput. Sci., pages 575-586. Springer, 2008. Google Scholar
  25. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster Parameterized Algorithms Using Linear Programming. ACM Trans. Algorithms, 11(2):15:1-15:31, 2014. URL: https://doi.org/10.1145/2566616.
  26. Meena Mahajan and Venkatesh Raman. Parameterizing above Guaranteed Values: MaxSat and MaxCut. J. Algorithms, 31(2):335-354, 1999. Google Scholar
  27. Meena Mahajan, Venkatesh Raman, and Somnath Sikdar. Parameterizing above or below guaranteed values. J. Computer and System Sciences, 75(2):137-153, 2009. URL: https://doi.org/10.1016/j.jcss.2008.08.004.
  28. David W. Matula and Leland L. Beck. Smallest-Last Ordering and clustering and Graph Coloring Algorithms. J. ACM, 30(3):417-427, 1983. URL: https://doi.org/10.1145/2402.322385.
  29. B. Monien. How to find long paths efficiently. In Analysis and design of algorithms for combinatorial problems (Udine, 1982), volume 109 of North-Holland Math. Stud., pages 239-254. North-Holland, Amsterdam, 1985. URL: https://doi.org/10.1016/S0304-0208(08)73110-4.
  30. Ingo Schiermeyer. Problems remaining NP-complete for sparse or dense graphs. Discussiones Mathematicae Graph Theory, 15(1):33-41, 1995. URL: https://doi.org/10.7151/dmgt.1004.
  31. Dekel Tsur. Faster deterministic parameterized algorithm for k-Path. CoRR, abs/1808.04185, 2018. URL: http://arxiv.org/abs/1808.04185.
  32. Ryan Williams. Finding Paths of Length k in O^*(2^k) Time. Inf. Process. Lett., 109(6):315-318, 2009. Google Scholar
  33. Meirav Zehavi. A randomized algorithm for long directed cycle. Inf. Process. Lett., 116(6):419-422, 2016. URL: https://doi.org/10.1016/j.ipl.2016.02.005.
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 About DROPS Imprint Privacy Contact