Name
Abstract | ||
|---|---|---|
Motivated by a recent result of Elberfeld, Jakoby and Tantau [EJT10] showing that MSO properties are Logspace computable on graphs of bounded treewidth, we consider the complexity of computing the determinant of the adjacency matrix of a bounded treewidth 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 treewidth 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 treewidth graph and feasibility of a system of linear equations where the underlying bipartite graph has bounded treewidth. Finally, we complement our upper bounds by proving L-hardness of the problems of computing the determinant, and of powering a bounded treewidth matrix. We also show the GapL-hardness of Iterated Matrix Multiplication where each matrix has bounded treewidth. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-17142-5_26 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Journal | 9076 | 0302-9743 |
Citations | PageRank | References |
1 | 0.35 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Balaji | 1 | 9 | 4.24 |
| Samir Datta | 2 | 9 | 1.21 |