TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
 
Options

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Citation Link: https://doi.org/10.15480/882.14875
Publikationstyp
Journal Article
Date Issued
2025
Sprache
English
Author(s)
Bergougnoux, Benjamin  
Chekan, Vera  
Kanté, Mamadou Moustapha
Mnich, Matthias  orcid-logo
Algorithmen und Komplexität E-11  
Oum, Sang-il  
Pilipczuk, Michał  
Leeuwen, Erik Jan van  
TORE-DOI
10.15480/882.14875
TORE-URI
https://hdl.handle.net/11420/54699
Journal
ACM Transactions on Computation Theory  
Citation
ACM Transactions on Computation Theory (2025)
ArXiv ID
2307.01285v1
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone.
Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth.
We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels,
- Independent Set can be solved in time 2O(dk) ·nO(1) using O(dk2logn) space; and
- Max Cut can be solved in time nO(dk) using O(dklogn) space; and
- Dominating Set can be solved in time 2O(dk) · nO(1) using nO(1) space via a randomized
algorithm.
We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.
Subjects
Parameterized complexity
shrubdepth
space complexity
algebraic methods
DDC Class
004: Computer Sciences
005.1: Programming
510: Mathematics
519: Applied Mathematics, Probabilities
Publication version
publishedVersion
Lizenz
https://creativecommons.org/licenses/by/4.0/
Loading...
Thumbnail Image
Name

2307.01285v1.pdf

Size

1.97 MB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback