Document Open Access Logo

On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs

Authors Michal Pilipczuk, Marcin Wrochna

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.57.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Michal Pilipczuk
Marcin Wrochna

Cite AsGet BibTex

Michal Pilipczuk and Marcin Wrochna. On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.57

Abstract

Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its drawbacks is that the space usage is exponential in the decomposition's width. Following the work of Allender et al. [Theory of Computing, 2014], we investigate whether this space complexity explosion is unavoidable. Using the idea of reparameterization of Cai and Juedes [J. Comput. Syst. Sci., 2003], we prove that the question is closely related to a conjecture that the Longest Common Subsequence problem parameterized by the number of input strings does not admit an algorithm that simultaneously uses XP time and FPT space. Moreover, we complete the complexity landscape sketched for pathwidth and treewidth by Allender et al. by considering the parameter tree-depth. We prove that computations on tree-depth decompositions correspond to a model of non-deterministic machines that work in polynomial time and logarithmic space, with access to an auxiliary stack of maximum height equal to the decomposition's depth. Together with the results of Allender et al., this describes a hierarchy of complexity classes for polynomial-time non- deterministic machines with different restrictions on the access to working space, which mirrors the classic relations between treewidth, pathwidth, and tree-depth.
Keywords
  • tree decomposition
  • LCS
  • tree-depth
  • NAuxSA
  • Savitch’s theorem

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59-78. IEEE Computer Society, 2015. Google Scholar
  2. Dmitri Akatov. Exploiting parallelism in decomposition methods for constraint satisfaction. PhD thesis, University of Oxford, 2010. Google Scholar
  3. Dmitri Akatov and Georg Gottlob. Balanced queries: Divide and conquer. In Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6281 of Lecture Notes in Computer Science, pages 42-54. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15155-2_6.
  4. Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang. Width-parametrized SAT: time-space tradeoffs. Theory of Computing, 10:297-339, 2014. URL: http://dx.doi.org/10.4086/toc.2014.v010a012.
  5. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12(2):308-340, 1991. Google Scholar
  6. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jussi Määttä. Space-time tradeoffs for subset sum: An improved worst case algorithm. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 45-56. Springer, 2013. Google Scholar
  7. Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 41(1):153-180, 1994. URL: http://dx.doi.org/10.1145/174644.174650.
  8. Marina Barsky, Ulrike Stege, Alex Thomo, and Chris Upton. Shortest path approaches for the longest common subsequence of a set of strings. In Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE 2007, October 14-17, 2007, Harvard Medical School, Boston, MA, USA, pages 327-333. IEEE Computer Society, 2007. URL: http://dx.doi.org/10.1109/BIBE.2007.4375584.
  9. 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.
  10. Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza. Rankings of graphs. SIAM J. Discrete Math., 11(1):168-181, 1998. URL: http://dx.doi.org/10.1137/S0895480195282550.
  11. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Harold T. Wareham. The parameterized complexity of sequence alignment and consensus. Theor. Comput. Sci., 147(1&2):31-54, 1995. URL: http://dx.doi.org/10.1016/0304-3975(94)00251-D.
  12. Liming Cai and David W. Juedes. On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci., 67(4):789-807, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00074-6.
  13. Hubie Chen and Moritz Müller. One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries. In Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS'14, Vienna, Austria, July 14-18, 2014, pages 32:1-32:10. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603107.
  14. Bruno Courcelle. The Monadic Second-Order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  15. 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
  16. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs. J. ACM, 52(6):866-893, 2005. Google Scholar
  17. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  18. Jeff Edmonds, Chung Keung Poon, and Dimitris Achlioptas. Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput., 28(6):2257-2284, 1999. URL: http://dx.doi.org/10.1137/S0097539795295948.
  19. Michael Elberfeld, Martin Grohe, and Till Tantau. Where first-order and monadic second-order logic coincide. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25-28, 2012, pages 265-274. IEEE Computer Society, 2012. Google Scholar
  20. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of bodlaender and courcelle. Electronic Colloquium on Computational Complexity (ECCC), 17:62, 2010. Extended abstract included in the proceedings of FOCS 2010. Google Scholar
  21. Michael Elberfeld, Christoph Stockhusen, and Till Tantau. On the space and circuit complexity of parameterized problems: Classes and completeness. Algorithmica, 71(3):661-701, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9944-y.
  22. J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1 edition, 2006. Google Scholar
  23. Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Parameterized single-exponential time polynomial space algorithm for Steiner Tree. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 494-505. Springer, 2015. Google Scholar
  24. Martin Fürer and Huiwen Yu. Space saving by dynamic algebraization. In Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings, volume 8476 of Lecture Notes in Computer Science, pages 375-388. Springer, 2014. Google Scholar
  25. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  26. Georg Gottlob, Nicola Leone, and Francesco Scarcello. The complexity of acyclic conjunctive queries. J. ACM, 48(3):431-498, 2001. URL: http://dx.doi.org/10.1145/382780.382783.
  27. Sylvain Guillemot. Parameterized complexity and approximability of the longest compatible sequence problem. Discrete Optimization, 8(1):50-60, 2011. URL: http://dx.doi.org/10.1016/j.disopt.2010.08.003.
  28. Meir Katchalski, William McCuaig, and Suzanne M. Seager. Ordered colourings. Discrete Mathematics, 142(1-3):141-154, 1995. Google Scholar
  29. Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. URL: http://dx.doi.org/10.1007/BFb0045375.
  30. Alexander Langer, Felix Reidl, Peter Rossmanith, and Somnath Sikdar. Practical algorithms for MSO model-checking on tree-decomposable graphs. Computer Science Review, 13-14:39-74, 2014. URL: http://dx.doi.org/10.1016/j.cosrev.2014.08.001.
  31. Richard J Lipton. Savitch’s theorem. In The P=NP Question and Gödel’s Lost Letter, pages 135-138. Springer, 2010. Google Scholar
  32. Richard J. Lipton and Robert Endre Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. Google Scholar
  33. Daniel Lokshtanov, Matthias Mnich, and Saket Saurabh. Planar k-path in subexponential time and polynomial space. In Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers, volume 6986 of Lecture Notes in Computer Science, pages 262-270. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25870-1_24.
  34. Daniel Lokshtanov and Jesper Nederlof. Saving space by algebraization. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 321-330. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806735.
  35. Pinyan Lu, Jialin Zhang, Chung Keung Poon, and Jin-yi Cai. Simulating undirected st-connectivity algorithms on uniform jags and nnjags. In Algorithms and Computation, 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, volume 3827 of Lecture Notes in Computer Science, pages 767-776. Springer, 2005. URL: http://dx.doi.org/10.1007/11602613_77.
  36. Burkhard Monien and Ivan Hal Sudborough. Bandwidth constrained NP-complete problems. Theor. Comput. Sci., 41:141-167, 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90068-4.
  37. Jesper Nederlof. Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica, 65(4):868-884, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9630-x.
  38. J. Nešetřil and P. Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  39. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet Shortest Common Supersequence and Longest Common Subsequence problems. J. Comput. Syst. Sci., 67(4):757-771, 2003. Google Scholar
  40. Alex Pothen. The complexity of optimal elimination trees, 1988. Technical Report CS 88-16, Pennsylvania State University. Google Scholar
  41. Neil Robertson and Paul D. Seymour. Graph Minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309-322, 1986. Google Scholar
  42. Walter L. Ruzzo. Tree-size bounded alternation. J. Comput. Syst. Sci., 21(2):218-235, 1980. URL: http://dx.doi.org/10.1016/0022-0000(80)90036-7.
  43. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. Google Scholar
  44. V. Vinay and V. Chandru. The expressibility of nondeterministic auxiliary stack automata and its relation to treesize bounded alternating auxiliary pushdown automata. In Foundations of Software Technology and Theoretical Computer Science, Tenth Conference, Bangalore, India, December 17-19, 1990, Proceedings, volume 472 of Lecture Notes in Computer Science, pages 104-114. Springer, 1990. URL: http://dx.doi.org/10.1007/3-540-53487-3_38.
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