Algorithm for $\mathcal{B}$-partitions, parameterized complexity of the matrix determinant and permanent

Abstract

Every square matrix $A=(a_{uv})\in {\mathcal{C}}^{n\times n}$ can be represented as a digraph having $n$ vertices. In the digraph, a block (or 2-connected component) is a maximally connected subdigraph that has no cut-vertex. The determinant and the permanent of a matrix can be calculated in terms of the determinant and the permanent of some specific induced subdigraphs of the blocks in the digraph. Interestingly, these induced subdigraphs are vertex-disjoint and they partition the digraph. Such partitions of the digraph are called the $\mathcal{B}$-partitions. In this paper, first, we develop an algorithm to find the $\mathcal{B}$-partitions. Next, we analyze the parameterized complexity of matrix determinant and permanent, where, the parameters are the sizes of blocks and the number of cut-vertices of the digraph. We give a class of combinations of cut-vertices and block sizes for which the parametrized complexities beat the state of art complexities of the determinant and the permanent.

arXiv admin note: text overlap with arXiv:1701.04420