2026-07-24T06:45:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12474 2024-03-06T10:50:14Z ddc:004 open_access

Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs Izumi, Taisuke Otachi, Yota depth-first search space complexity treewidth The lexicographic depth-first search (Lex-DFS) is one of the first basic graph problems studied in the context of space-efficient algorithms. It is shown independently by Asano et al. [ISAAC 2014] and Elmasry et al. [STACS 2015] that Lex-DFS admits polynomial-time algorithms that run with O(n)-bit working memory, where n is the number of vertices in the graph. Lex-DFS is known to be P-complete under logspace reduction, and giving or ruling out polynomial-time sublinear-space algorithms for Lex-DFS on general graphs is quite challenging. In this paper, we study Lex-DFS on graphs of bounded treewidth. We first show that given a tree decomposition of width O(n^(1-ε)) with ε > 0, Lex-DFS can be solved in sublinear space. We then complement this result by presenting a space-efficient 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 space-efficient algorithm for computing a tree decomposition of moderate (small but non-constant) width. By combining these results, we can show in particular that graphs of treewidth O(n^(1/2 - ε)) for some ε > 0 admits a polynomial-time sublinear-space algorithm for Lex-DFS. We can also show that planar graphs admit a polynomial-time algorithm with O(n^(1/2+ε))-bit working memory for Lex-DFS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Taisuke Izumi and Yota Otachi 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.67 urn:nbn:de:0030-drops-124745 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.67 eng https://creativecommons.org/licenses/by/3.0/legalcode