Document Open Access Logo

Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs

Authors Archontia C. Giannopoulou, George B. Mertzios, Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.102.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Author Details

Archontia C. Giannopoulou
George B. Mertzios
Rolf Niedermeier

Cite As Get BibTex

Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 102-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.102

Abstract

We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. 
The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: Longest Path; it is NP-hard in general but known to be solvable in O(n^4) time on n-vertex interval graphs. We show how to solve Longest Path on Interval Graphs, parameterized by vertex deletion number k to proper interval graphs, in O(k^9n) time. Notably, Longest Path is trivially solvable in linear time on proper interval graphs, and the parameter value k can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis for polynomial-time solvable problems offers a very fertile ground for future studies for all sorts of algorithmic problems. It may enable a refined understanding of efficiency aspects for polynomial-time solvable problems, similarly to what classical parameterized complexity analysis does for NP-hard problems.

Subject Classification

Keywords
  • fixed-parameter algorithm
  • preprocessing
  • data reduction
  • polynomial-time algorithm
  • longest path problem
  • interval graphs
  • proper interval vertex del

Metrics

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

References

  1. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1681-1697, 2015. Google Scholar
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS), pages 434-443, 2014. Google Scholar
  3. Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016. To appear. Google Scholar
  4. Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato Fonseca F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 782-793, 2010. Google Scholar
  5. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. of ACM, 42(4):844-856, 1995. Google Scholar
  6. Amihood Amir, Moshe Lewenstein, and Ely Porat. Faster algorithms for string matching with k mismatches. Journal of Algorithms, 50(2):257-275, 2004. Google Scholar
  7. Alan A. Bertossi. Finding Hamiltonian circuits in proper interval graphs. Information Processing Letters, 17(2):97-101, 1983. Google Scholar
  8. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. on Comp., 25(6):1305-1317, 1996. Google Scholar
  9. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of the 55th IEEE Symp. on Foundations of Computer Science (FOCS), pages 661-670, 2014. Google Scholar
  10. Sergio Cabello and Christian Knauer. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational Geometry, 42(9):815-824, 2009. Google Scholar
  11. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. Google Scholar
  12. Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Homology flows, cohomology cuts. SIAM J. on Comput., 41(6):1605-1634, 2012. Google Scholar
  13. Jianer Chen, Songjian Lu, Sing-Hoi Sze, and Fenghui Zhang. Improved algorithms for path, matching, and packing problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 298-307, 2007. Google Scholar
  14. Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul Seymour, and Kristina Vušković. Recognizing Berge graphs. Combinatorica, 25(2):143-186, 2005. Google Scholar
  15. Peter Damaschke. Paths in interval graphs and circular arc graphs. Discrete Mathematics, 112(1-3):49-64, 1993. Google Scholar
  16. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  17. Michael R. Fellows, Bart M. P. Jansen, and Frances A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European Journal of Combinatorics, 34(3):541-566, 2013. Google Scholar
  18. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  19. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Computational Geometry, 5:165-185, 1995. Google Scholar
  20. Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC), pages 162-173, 2004. Google Scholar
  21. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. Journal of Computer and System Sciences, 57(3):366-375, 1998. Google Scholar
  22. Jan M. Hochstein and Karsten Weihe. Maximum s-t-flow with k crossings in O(k³ n log n) time. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 843-847, 2007. Google Scholar
  23. K. Ioannidou, George B. Mertzios, and Stavros D. Nikolopoulos. The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61(2):320-341, 2011. Google Scholar
  24. Ken-ichi Kawarabayashi and Bruce A. Reed. Computing crossing number in linear time. In Proceedings of the 39th ACM Symp. on Th. of Comp. (STOC), pages 382-390, 2007. Google Scholar
  25. J. M. Keil. Finding Hamiltonian circuits in interval graphs. Information Processing Letters, 20:201-206, 1985. Google Scholar
  26. Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith. Divide-and-color. In Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 58-67, 2006. Google Scholar
  27. Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for SDD linear systems. In Proceedings of the IEEE 52nd Symposium on Foundations of Computer Science (FOCS), pages 590-598, 2011. Google Scholar
  28. Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114-127, 1984. Google Scholar
  29. George B. Mertzios and Derek G. Corneil. A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM J. on Discr. Math., 26(3):940-963, 2012. Google Scholar
  30. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, 2006. Google Scholar
  31. James B. Orlin, Kamesh Madduri, K. Subramani, and Matthew D. Williamson. A faster algorithm for the single source shortest path problem with few distinct positive lengths. Journal of Discrete Algorithms, 8(2):189-198, 2010. Google Scholar
  32. F. S. Roberts. Indifference graphs. In F. Harary, editor, Proof Techniques in Graph Theory, pages 139-146. Academic Press, New York, 1969. Google Scholar
  33. R. Uehara and Y. Uno. On computing longest paths in small graph classes. International Journal of Foundations of Computer Science, 18(5):911-930, 2007. Google Scholar
  34. René van Bevern. Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications. PhD thesis, Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Germany, 2014. Google Scholar
  35. Ryan Williams. Finding paths of length k in O^*(2^k) time. Information Processing Letters, 109(6):315-318, 2009. 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 About DROPS Imprint Privacy Contact