2026-07-22T14:20:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2456 2024-03-06T10:33:22Z ddc:004 open_access

Log-space Algorithms for Paths and Matchings in k-trees Das, Bireswar Datta, Samir Nimbhorkar, Prajakta k-trees reachability matching log-space Reachability and shortest path problems are \NLC\ for general graphs. They are known to be in \Log\ for graphs of tree-width $2$ \cite{JT07}. However, for graphs of tree-width larger than $2$, no bound better than \NL\ is known. In this paper, we improve these bounds for $k$-trees, where $k$ is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed $k$-trees, and for computation of shortest and longest paths in directed acyclic $k$-trees. Besides the path problems mentioned above, we consider the problem of deciding whether a $k$-tree has a perfect macthing (decision version), and if so, finding a perfect matching (search version), and prove that these problems are \Log-complete. These problems are known to be in \Ptime\ and in \RNC\ for general graphs, and in \SPL\ for planar bipartite graphs \cite{DKR08}. Our results settle the complexity of these problems for the class of $k$-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of divide-and-conquer approach in log-space, along with some ideas from \cite{JT07} and \cite{LMR07}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bireswar Das and Samir Datta and Prajakta Nimbhorkar 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2456 urn:nbn:de:0030-drops-24563 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2456 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode