×

Parameterized complexity of determinant and permanent. (English) Zbl 1454.68060

Summary: Every square matrix \(A = (a_{u v}) \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.

MSC:

68Q27 Parameterized complexity, tractability and kernelization
05C20 Directed graphs (digraphs), tournaments
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
15A15 Determinants, permanents, traces, other special matrix functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdollahi, Alireza, Determinants of adjacency matrices of graphs, Trans. Comb., 1, 4, 9-16 (2012) · Zbl 1272.05107
[2] Aho, Alfred V.; Hopcroft, John E., The Design and Analysis of Computer Algorithms (1974), Pearson Education India · Zbl 0326.68005
[3] Bapat, Ravindra B., Graphs and Matrices, vol. 27 (2010), Springer
[4] Bapat, R. B.; Beg, M. I., Order statistics for nonidentically distributed variables and permanents, Sankhya, Ser. A, 79-93 (1989) · Zbl 0672.62060
[5] Bapat, R. B.; Roy, Souvik, On the adjacency matrix of a block graph, Linear Multilinear Algebra, 62, 3, 406-418 (2014) · Zbl 1296.05118
[6] Bareiss, Erwin H., Sylvester’s identity and multistep integer-preserving Gaussian elimination, Math. Comput., 22, 103, 565-578 (1968) · Zbl 0187.09701
[7] Bibak, Khodakhast, On the determinant of bipartite graphs, Discrete Math., 313, 21, 2446-2450 (2013) · Zbl 1279.05044
[8] Bibak, Khodakhast; Tauraso, Roberto, Determinants of grids, tori, cylinders and Möbius ladders, Discrete Math., 313, 13, 1436-1440 (2013) · Zbl 1279.05061
[9] Coppersmith, Don; Winograd, Shmuel, Matrix multiplication via arithmetic progressions, J. Symb. Comput., 9, 3, 251-280 (1990) · Zbl 0702.65046
[10] Davie, Alexander Munro; Stothers, Andrew James, Improved bound for complexity of matrix multiplication, Proc. R. Soc. Edinb., Sect. A, Math., 143, 02, 351-369 (2013) · Zbl 1276.65024
[11] Farrell, E. J.; Kennedy, J. W.; Quintas, L. V., Permanents and determinants of graphs: a cycle polynomial approach, J. Comb. Math. Comb. Comput., 32, 129-138 (2000) · Zbl 0953.05043
[12] Greenman, J. V., Graphs and determinants, Math. Gaz., 60, 414, 241-246 (1976) · Zbl 0438.15014
[13] Gutman, Ivan; Borovicanin, Bojana, Nullity of graphs: an updated survey, Zb. Rad. (Beogr.), 14, 22, 137-154 (2011) · Zbl 1289.05287
[14] Harary, Frank, The determinant of the adjacency matrix of a graph, SIAM Rev., 4, 3, 202-210 (1962) · Zbl 0113.17406
[15] Harary, Frank, Determinants, permanents and bipartite graphs, Math. Mag., 42, 3, 146-148 (1969) · Zbl 0273.15006
[16] Helton, J. William; Klep, Igor; Gomez, Raul, Determinant expansions of signed matrices and of certain Jacobians, SIAM J. Matrix Anal. Appl., 31, 2, 732-754 (2009) · Zbl 1191.15023
[17] Hopcroft, John E.; Tarjan, Robert E., Efficient Algorithms for Graph Manipulation (1971)
[18] Huang, Lingling; Yan, Weigen, On the determinant of the adjacency matrix of a type of plane bipartite graphs, MATCH Commun. Math. Comput. Chem., 68, 931-938 (2012) · Zbl 1289.05293
[19] Hwang, Suk-Geun; Zhang, Xiao-Dong, Permanents of graphs with cut vertices, Linear Multilinear Algebra, 51, 4, 393-404 (2003) · Zbl 1036.05031
[20] Le Gall, François, Powers of tensors and fast matrix multiplication, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (2014), ACM), 296-303 · Zbl 1325.65061
[21] Lee, Shyi-Long; Li, Chiuping, Chemical signed graph theory, Int. J. Quant. Chem., 49, 5, 639-648 (1994)
[22] Leskovec, Jure; Huttenlocher, Daniel; Kleinberg, Jon, Signed networks in social media, (Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (2010), ACM), 1361-1370
[23] Minc, Henryk, Permanents. Number 6 (1984), Cambridge University Press · Zbl 0543.15005
[24] Pragel, Daniel, Determinants of box products of paths, Discrete Math., 312, 10, 1844-1847 (2012) · Zbl 1242.05168
[25] Ranveer, Singh, Parameterized complexity of the matrix determinant and permanent, (Book of Abstracts (2018), University of Lódz), 49
[26] Rote, Günter, Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches, (Computational Discrete Mathematics (2001), Springer), 119-135 · Zbl 1010.65022
[27] Singh, Ranveer; Bapat, Ravindra B., B-partitions, determinant and permanent of graphs, Trans. Comb., 7, 3, 37-54 (2018) · Zbl 1474.05325
[28] Singh, Ranveer; Bapat, R. B., On characteristic and permanent polynomials of a matrix, Spec. Matrices, 5, 97-112 (2017) · Zbl 1392.15014
[29] Valiant, Leslie G., The complexity of computing the permanent, Theor. Comput. Sci., 8, 2, 189-201 (1979) · Zbl 0415.68008
[30] Von Collatz, Lothar; Sinogowitz, Ulrich, Spektren endlicher grafen, (Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 21 (1957), Springer), 63-77 · Zbl 0077.36704
[31] Wanless, Ian M., Permanents of matrices of signed ones, Linear Multilinear Algebra, 53, 6, 427-433 (2005) · Zbl 1085.15006
[32] Wei, Tzu-Chieh; Severini, Simone, Matrix permanent and quantum entanglement of permutation invariant states, J. Math. Phys., 51, 9, Article 092203 pp. (2010) · Zbl 1309.81039
[33] Williams, V. Vassilevska, Breaking the Coppersmith-Winograd Barrier (2011), e-mail address:
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.