Bounded treewidth and space-efficient linear algebra

DOI10.1007/978-3-319-17142-5_26MaRDI QIDQ2948475zbMATH OpenOpenAlexFDO

Authors Nikhil Balaji, Samir Datta

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.2470

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: Motivated by a recent result of Elberfeld, Jakoby and Tantau showing that $mathsfMSO$ 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 $mathsfMSO$-property nor counts the number of solutions of an $mathsfMSO$-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 $mathsfL$-hardness of the problems of computing the determinant, and of powering a bounded tree-width matrix. We also show the $mathsfGapL$-hardness of Iterated Matrix Multiplication where each matrix has bounded tree-width.

Recommendations

• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• scientific article; zbMATH DE number 4060712
• Balancing Bounded Treewidth Circuits
• Restricted space algorithms for isomorphism on bounded treewidth graphs

Cites work

• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Algebraic Combinatorics
• Counting quantifiers, successor relations, and logarithmic space
• Exact counting of Euler tours for generalized series-parallel graphs
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• Log-space algorithms for paths and matchings in k-trees
• Modern computer algebra
• On computing the determinant in small parallel time using a small number of processors
• On the ordered conjecture
• On Unicursal Paths in a Network of Degree 4
• Parametrized complexity theory.
• Planarity, determinants, permanents, and (unique) matchings
• The complexity of matrix rank and feasible systems of linear equations
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(5)

• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• An efficient tree decomposition method for permanents and mixed discriminants

This page was built for publication: Bounded treewidth and space-efficient linear algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948475)