Document Open Access Logo

Dynamic Parameterized Problems and Algorithms

Authors Josh Alman, Matthias Mnich, Virginia Vassilevska Williams

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.41.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Josh Alman
Matthias Mnich
Virginia Vassilevska Williams

Cite AsGet BibTex

Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams. Dynamic Parameterized Problems and Algorithms. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.41

Abstract

Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet, so far those algorithms have been largely restricted to static inputs. In this paper we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems which are known to have f(k)n^{1+o(1)} time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g(k)n^{o(1)}; such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that Feedback Vertex Set and k-Path admit dynamic algorithms with f(k)log O(1) n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, Directed Feedback Vertex Set and Directed k-Path do not admit dynamic algorithms with n^{o(1) } update and query times even for constant solution sizes k <= 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, Directed Feedback Vertex Set cannot be solved with update time that is purely a function of k.
Keywords
  • Dynamic algorithms
  • fixed-parameter algorithms

Metrics

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

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. FOCS 2014, pages 434-443, 2014. Google Scholar
  2. Faisal N. Abu-Khzam, Judith Egan, Michael R. Fellows, Frances A. Rosamond, and Peter Shaw. On the parameterized complexity of dynamic problems with connectivity constraints. In Proc. COCOA 2014, volume 8881 of Lecture Notes Comput. Sci., pages 625-636, 2014. Google Scholar
  3. Faisal N. Abu-Khzam, Judith Egan, Michael R. Fellows, Frances A. Rosamond, and Peter Shaw. On the parameterized complexity of dynamic problems. Theor. Comput. Sci., 607:426-434, 2015. Google Scholar
  4. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4), 1995. Google Scholar
  5. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O(log n) update time. SIAM J. Comput., 44(1):88-113, 2015. Google Scholar
  6. Ann Becker, Reuven Bar-Yehuda, and Dan Geiger. Randomized algorithms for the loop cutset problem. J. Artif. Intelligence Res., 12:219-234, 2000. Google Scholar
  7. Aaron Bernstein and Liam Roditty. Improved dynamic algorithms for maintaining approximate shortest paths under deletions. In Proc. SODA 2011, pages 1355-1365, 2011. Google Scholar
  8. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In Proc. SODA 2015, pages 785-804, 2015. Google Scholar
  9. Hans L. Bodlaender. Dynamic algorithms for graphs with treewidth 2. In Proc. WG 1993, volume 790 of Lecture Notes Comput. Sci., pages 112-124, 1993. Google Scholar
  10. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. Google Scholar
  11. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^kn 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. Google Scholar
  12. S. Buss. private communication. Google Scholar
  13. Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. In Proc. IPEC 2006, volume 4169 of Lecture Notes Comput. Sci., pages 239-250, 2006. Google Scholar
  14. Liming Cai, Jianer Chen, Rodney G. Downey, and Michael R. Fellows. Advice classes of parameterized tractability. Ann. Pure Applied Logic, 84(1):119-138, 1997. Google Scholar
  15. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theoret. Comput. Sci., 411(40):3736-3756, 2010. Google Scholar
  16. Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5), 2008. Google Scholar
  17. Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh. Parameterized streaming: Maximal matching and vertex cover. In Proc. SODA 2015, pages 1234-1251, 2015. Google Scholar
  18. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  19. Marek Cygan. Deterministic parameterized connected vertex cover. In Proc. SWAT 2012, volume 7357 of Lecture Notes Comput. Sci., pages 95-106, 2012. Google Scholar
  20. Marek Cygan, Fedor Fomin, Bart M.P. Jansen, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Open problems for FPT school 2014. URL: http://fptschool.mimuw.edu.pl/opl.pdf.
  21. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, Cham, 2015. Google Scholar
  22. Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Magnus Wahlström. Clique cover and graph separation: New incompressibility results. ACM Trans. Comput. Theory, 6(2):6:1-6:19, 2014. Google Scholar
  23. Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM J. Comput., 45(1):67-83, 2016. Google Scholar
  24. Jean Daligault, Gregory Gutin, Eun Jung Kim, and Anders Yeo. FPT algorithms and kernels for the directed k-leaf problem. J. Comput. Syst. Sci., 76(2):144-152, 2010. Google Scholar
  25. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM, 61(4):23:1-23:27, 2014. Google Scholar
  26. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM, 51(6):968-992, 2004. Google Scholar
  27. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Incompressibility through colors and IDs. In Proc. ICALP 2009, volume 5555 of Lecture Notes Comput. Sci., pages 378-389, 2009. Google Scholar
  28. Frederic Dorn. Planar subgraph isomorphism revisited. In Proc. STACS 2010, volume 5 of Leibniz Int. Proc. Informatics, pages 263-274, 2010. Google Scholar
  29. Zdeněk Dvořák, Martin Kupec, and Vojtěch Tůma. A dynamic data structure for MSO properties in graphs with bounded tree-depth. In Proc. ESA 2014, volume 8737 of Lecture Notes Comput. Sci., pages 334-345, 2014. Google Scholar
  30. Zdeněk Dvořák and Vojtěch Tůma. A dynamic data structure for counting subgraphs in sparse graphs. In Proc. WADS 2013, volume 8037 of Lecture Notes Comput. Sci., pages 304-315, 2013. Google Scholar
  31. Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, and Frances A. Rosamond. FPT is P-time extremal structure I. In Proc. ACiD 2005, pages 1-41, 2005. Google Scholar
  32. Michael Etscheid and Matthias Mnich. Linear kernels and linear time algorithms for finding large cuts. In Proc. ISAAC 2016, volume 64 of Leibniz Int. Proc. Informatics, pages 31:1-31:13, 2016. Google Scholar
  33. Stefan Fafianie and Stefan Kratsch. A shortcut to (sun)flowers: Kernels in logarithmic space or linear time. In Proc. MFCS 2015, volume 9235 of Lecture Notes Comput. Sci., pages 299-310, 2015. Google Scholar
  34. Henning Fernau. Edge dominating set: Efficient enumeration-based exact algorithms. In Proc. IPEC 2006, volume 4169 of Lecture Notes Comput. Sci., pages 142-153, 2006. Google Scholar
  35. Anka Gajentaan and Mark H. Overmars. On a class of problems in computational geometry. Comput. Geom., 45(4):140-152, 2012. Google Scholar
  36. François Le Gall. Powers of tensors and fast matrix multiplication. In Proc. ISSAC 2014, pages 296-303, 2014. Google Scholar
  37. David Gibb, Bruce Kapron, Valerie King, and Nolan Thorn. Dynamic graph connectivity with improved worst case update time and sublinear space, 2015. URL: https://arxiv.org/abs/1509.06464.
  38. Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Data reduction and exact algorithms for clique cover. J. Exp. Algorithmics, 13:2:2.2-2:2.15, 2009. Google Scholar
  39. Manoj Gupta and Richard Peng. Fully dynamic (1+ε)-approximate matchings. In Proc. FOCS 2013, pages 548-557, 2013. Google Scholar
  40. Andras Gyárfás. A simple lower bound on edge coverings by cliques. Discrete Math., 85(1):103-104, 1990. Google Scholar
  41. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved algorithms for decremental single-source reachability on directed graphs. In Proc. ICALP 2015, volume 9134 of Lecture Notes Comput. Sci., pages 725-736, 2015. Google Scholar
  42. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM J. Comput., 45(3):947-1006, 2016. Google Scholar
  43. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. FOCS 2015, pages 21-30, 2015. Google Scholar
  44. Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM, 46(4):502-516, 1999. Google Scholar
  45. Monika Rauch Henzinger and Valerie King. Maintaining minimum spanning forests in dynamic graphs. SIAM J. Comput., 31(2):364-374, 2001. Google Scholar
  46. Monika Rauch Henzinger and Mikkel Thorup. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Struct. Algorithms, 11(4):369-379, 1997. Google Scholar
  47. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. Google Scholar
  48. Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. Fully dynamic connectivity in O(log n(log log n)²) amortized expected time, 2016. URL: http://arxiv.org/abs/1609.05867.
  49. Ken Iwaide and Hiroshi Nagamochi. An improved algorithm for parameterized edge dominating set problem. J. Graph Algorithms Appl., 20(1):23-58, 2016. Google Scholar
  50. Yoichi Iwata. A linear time kernelization for feedback vertex set, 2016. URL: https://arxiv.org/abs/1608.01463.
  51. Yoichi Iwata and Keigo Oka. Fast dynamic graph algorithms for parameterized problems. In Proc. SWAT 2014, volume 8503 of Lecture Notes Comput. Sci., pages 241-252, 2014. Google Scholar
  52. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. Linear-time FPT algorithms via network flow. In Proc. SODA 2014, pages 1749-1761, 2014. Google Scholar
  53. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proc. SODA 2013, pages 1131-1142, 2013. Google Scholar
  54. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In Proc. SODA 2016, pages 1272-1287, 2016. Google Scholar
  55. Stefan Kratsch, Geevarghese Philip, and Saurabh Ray. Point line cover: The easy kernel is essentially tight. ACM Trans. Algorithms, 12(3):40:1-40:16, 2016. Google Scholar
  56. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In Proc. FOCS 2012, pages 450-459, 2012. Google Scholar
  57. 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. Google Scholar
  58. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. Linear time parameterized algorithms for subset feedback vertex set. In Proc. ICALP 2015, volume 9134 of Lecture Notes Comput. Sci., pages 935-946, 2015. Google Scholar
  59. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. A linear time parameterized algorithm for directed feedback vertex set, 2016. URL: https://arxiv.org/abs/1609.04347.
  60. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Proc.FOCS 2013, pages 253-262, 2013. Google Scholar
  61. Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover. In Proc. STOC 2010, pages 457-464, 2010. Google Scholar
  62. Mihai Pǎtraşcu. Towards polynomial lower bounds for dynamic problems. In Proc. STOC 2010, pages 603-610, 2010. Google Scholar
  63. Mihai Pǎtraşcu. Unifying the landscape of cell-probe lower bounds. SIAM J. Comput., 40(3):827-847, 2011. Google Scholar
  64. Mihai Pǎtraşcu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput., 35(4):932-963, 2006. Google Scholar
  65. Mihai Pǎtraşcu and Mikkel Thorup. Don't rush into a union: take time to find your roots. In Proc. STOC 2011, pages 559-568, 2011. Google Scholar
  66. Shay Solomon. Fully dynamic maximal matching in constant update time. In Proc. FOCS 2016, pages 325-334, 2016. Google Scholar
  67. Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In Proc. STOC 2000, pages 343-350, 2000. Google Scholar
  68. René van Bevern. Towards optimal and expressive kernelization for d-hitting set. Algorithmica, 70(1):129-147, 2014. Google Scholar
  69. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proc. STOC 2012, pages 887-898, 2012. Google Scholar
  70. Magnus Wahlström. Half-integrality, LP-branching and FPT algorithms. In Proc. SODA 2014, pages 1762-1781, 2014. Google Scholar
  71. Christian Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Proc. SODA 2013, pages 1757-1769, 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