2014/12/08 by Nikhil Balaji, Balaji, Nikhil, Samir Datta +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph theory and applications #cs.CC
paper · pdf · doi:10.48550/arxiv.1412.2470
Replaces http://arxiv.org/abs/1312.7468
arxiv created 2014/12/08 · openalex publication_date 2014/12/08 · arxiv updated 2014/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by a recent result of Elberfeld, Jakoby and Tantau showing that MSO properties are Logspace computable on graphs of bounded tree-width, we consider the complexity of computing the determinant of the adjacency matrix of a bounded tree-width graph and as our main result prove that it is in Logspace. It is important to notice that the determinant is neither an MSO-property nor counts the number of solutions of an MSO-predicate. This technique yields Logspace algorithms for counting the number of spanning arborescences and directed Euler tours in bounded tree-width digraphs. We demonstrate some linear algebraic applications of the determinant algorithm by describing Logspace procedures for the characteristic polynomial, the powers of a weighted bounded tree-width graph and feasibility of a system of linear equations where the underlying bipartite graph has bounded tree-width. Finally, we complement our upper bounds by proving L-hardness of the problems of computing the determinant, and of powering a bounded tree-width matrix. We also show the GapL-hardness of Iterated Matrix Multiplication where each matrix has bounded tree-width.