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}.
展开▼
机译：对于一般图形，可到达性和最短路径问题为 NLC 。已知它们在 Log 中显示树宽$ 2 $ cite {JT07}。但是，对于树宽大于$ 2 $的图，没有比 NL 更好的绑定了。在本文中，我们改善了$ k $ -tree的边界，其中$ k $是一个常数。特别是，本文的主要结果是对数空间算法，用于有向$ k $-树中的可达性，以及对有向无环$ k $-树中最短和最长路径的计算。除了上面提到的路径问题外，我们还考虑确定$ k $ -tree是否具有理想的方法（决策版本），如果是，则寻找理想的匹配条件（搜索版本），并证明这些问题是 Log -完成。对于一般图形，这些问题已知在 Ptime 和 RNC 中，对于平面二部图形 cite {DKR08}在 SPL 中已知。我们的结果解决了$ k $ -trees类的这些问题的复杂性。当给出树分解作为输入时，结果也适用于有界树宽图。我们算法的核心技术是在日志空间中仔细实施分而治之方法，以及来自 cite {JT07}和 cite {LMR07}的一些思想。
展开▼
