On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.
From MaRDI portal
Publication:4601909
DOI10.4230/LIPICS.STACS.2016.57zbMATH Open1388.68133arXiv1509.05896OpenAlexW2963401228MaRDI QIDQ4601909FDOQ4601909
Marcin Wrochna, Michał Pilipczuk
Publication date: 24 January 2018
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, '14], we investigate whether this space complexity explosion is unavoidable. Using the idea of reparameterization of Cai and Juedes [J. Comput. Syst. Sci., '03], 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.
Full work available at URL: https://arxiv.org/abs/1509.05896
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Internet topics (68M11)
Cited In (6)
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Space-efficient algorithms for longest increasing subsequence
- Space-Efficient Algorithms for Longest Increasing Subsequence
- Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
This page was built for publication: On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601909)
