Izumi, Taisuke ;
Otachi, Yota
SublinearSpace Lexicographic DepthFirst Search for Bounded Treewidth Graphs and Planar Graphs
Abstract
The lexicographic depthfirst search (LexDFS) is one of the first basic graph problems studied in the context of spaceefficient algorithms. It is shown independently by Asano et al. [ISAAC 2014] and Elmasry et al. [STACS 2015] that LexDFS admits polynomialtime algorithms that run with O(n)bit working memory, where n is the number of vertices in the graph. LexDFS is known to be Pcomplete under logspace reduction, and giving or ruling out polynomialtime sublinearspace algorithms for LexDFS on general graphs is quite challenging. In this paper, we study LexDFS on graphs of bounded treewidth. We first show that given a tree decomposition of width O(n^(1ε)) with ε > 0, LexDFS can be solved in sublinear space. We then complement this result by presenting a spaceefficient algorithm that can compute, for w ≤ √n, a tree decomposition of width O(w √nlog n) or correctly decide that the graph has a treewidth more than w. This algorithm itself would be of independent interest as the first spaceefficient algorithm for computing a tree decomposition of moderate (small but nonconstant) width. By combining these results, we can show in particular that graphs of treewidth O(n^(1/2  ε)) for some ε > 0 admits a polynomialtime sublinearspace algorithm for LexDFS. We can also show that planar graphs admit a polynomialtime algorithm with O(n^(1/2+ε))bit working memory for LexDFS.
BibTeX  Entry
@InProceedings{izumi_et_al:LIPIcs:2020:12474,
author = {Taisuke Izumi and Yota Otachi},
title = {{SublinearSpace Lexicographic DepthFirst Search for Bounded Treewidth Graphs and Planar Graphs}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {67:167:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12474},
URN = {urn:nbn:de:0030drops124745},
doi = {10.4230/LIPIcs.ICALP.2020.67},
annote = {Keywords: depthfirst search, space complexity, treewidth}
}
29.06.2020
Keywords: 

depthfirst search, space complexity, treewidth 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 