Document Open Access Logo

Parameterization Above a Multiplicative Guarantee

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

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.39.pdf
  • Filesize: 0.72 MB
  • 13 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
  • University of California, Santa Barbara, USA
Fahad Panolan
  • Indian Institute of Technology Hyderabad, India
Saket Saurabh
  • Department of Informatics, University of Bergen, Norway
  • The Institute of Mathematical Sciences, HBNI and IRL 2000 ReLaX, Chennai, India
Meirav Zehavi
  • Ben-Gurion University of the Negev, Beersheba, Israel

Funding

  • Fomin, Fedor V.: Research Council of Norway via the project MULTIVAL.
  • Golovach, Petr A.: Research Council of Norway via the project MULTIVAL.
  • Lokshtanov, Daniel: European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant no. 715744), and United States - Israel Binational Science Foundation grant no. 2018302.
  • Saurabh, Saket: European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant no. 819416), and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.
  • Zehavi, Meirav: Israel Science Foundation grant no. 1176/18, and United States - Israel Binational Science Foundation grant no. 2018302.

Cite AsGet BibTex

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Parameterization Above a Multiplicative Guarantee. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.39

Abstract

Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (at most) k+g(I). Here, g(I) is usually a lower bound (resp. upper bound) on the maximum (resp. minimum) size of a solution. Since its introduction in 1999 for Max SAT and Max Cut (with g(I) being half the number of clauses and half the number of edges, respectively, in the input), analysis of parameterization above a guarantee has become a very active and fruitful topic of research. We highlight a multiplicative form of parameterization above a guarantee: Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (resp. at most) k ⋅ g(I). In particular, we study the Long Cycle problem with a multiplicative parameterization above the girth g(I) of the input graph, and provide a parameterized algorithm for this problem. Apart from being of independent interest, this exemplifies how parameterization above a multiplicative guarantee can arise naturally. We also show that, for any fixed constant ε>0, multiplicative parameterization above g(I)^(1+ε) of Long Cycle yields para-NP-hardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of algorithms for other problems parameterized multiplicatively above girth.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Parameterized Complexity
  • Above-Guarantee Parameterization
  • Girth

Metrics

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

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. 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
  3. E. Birmelé, J. A. Bondy, and B. A. Reed. Brambles, Prisms and Grids. In Adrian Bondy, Jean Fonlupt, Jean-Luc Fouquet, Jean-Claude Fournier, and Jorge L. Ramírez Alfonsín, editors, Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge, pages 37-44. Birkhäuser Basel, Basel, 2007. 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. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  7. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-Approximation Algorithm for Treewidth. SIAM J. Comput., 45(2):317-378, 2016. URL: https://doi.org/10.1137/130947374.
  8. 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.
  9. 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
  10. Robert Crowston, Michael R. Fellows, Gregory Z. Gutin, Mark Jones, Eun Jung Kim, Fran Rosamond, Imre Z. Ruzsa, Stéphan Thomassé, and Anders Yeo. Satisfying more than half of a system of linear equations over GF(2): A multivariate approach. J. Comput. Syst. Sci., 80(4):687-696, 2014. Google Scholar
  11. 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
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  13. Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, third edition, 2005. Google Scholar
  14. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  15. 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
  16. P Erdős and L Pósa. On independent circuits contained in a graph. Canad. J. Math., 17:347–352, 1965. Google Scholar
  17. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Going Far From Degeneracy. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1-47:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.47.
  18. 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.
  19. 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. Google Scholar
  20. 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. Google Scholar
  21. F.V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2018. Google Scholar
  22. 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.
  23. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  24. 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.
  25. 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.
  26. Gregory Z. Gutin and Viresh Patel. Parameterized Traveling Salesman Problem: Beating the Average. SIAM J. Discrete Math., 30(1):220-238, 2016. Google Scholar
  27. 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. Google Scholar
  28. Gregory Z. Gutin, Stefan Szeider, and Anders Yeo. Fixed-Parameter Complexity of Minimum Profile Problems. Algorithmica, 52(2):133-152, 2008. Google Scholar
  29. 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.
  30. 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
  31. 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
  32. Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh, and Meirav Zehavi. Packing Cycles Faster Than Erdos-Posa. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 71:1-71:15, 2017. Google Scholar
  33. Meena Mahajan and Venkatesh Raman. Parameterizing above Guaranteed Values: MaxSat and MaxCut. J. Algorithms, 31(2):335-354, 1999. Google Scholar
  34. 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.
  35. 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.
  36. Maria J. Serna and Dimitrios M. Thilikos. Parameterized Complexity for Graph Layout Problems. Bulletin of the EATCS, 86:41-65, 2005. Google Scholar
  37. Dekel Tsur. Faster deterministic parameterized algorithm for k-Path. CoRR, abs/1808.04185, 2018. URL: http://arxiv.org/abs/1808.04185.
  38. Ryan Williams. Finding Paths of Length k in O^*(2^k) Time. Inf. Process. Lett., 109(6):315-318, 2009. Google Scholar
  39. Meirav Zehavi. Mixing Color Coding-Related Techniques. In ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 1037-1049. Springer, 2015. Google Scholar
  40. 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 Imprint Privacy Contact