Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences

DOI10.1137/1.9781611974324.10MaRDI QIDQ5194946zbMATH OpenOpenAlexFDO

Authors Matúš Mihalák, Przemysław Uznański, Pencho Yordanov

Publication date 17 September 2019

Published in 2016 Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

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

zbMATH Keywords

Kirchhoff polynomialrooted directed spanning trees

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We study the problem of enumerating all rooted directed spanning trees (arborescences) of a directed graph (digraph) $G=(V,E)$ of $n$ vertices. An arborescence $A$ consisting of edges $e_1,ldots,e_{n-1}$ can be represented as a monomial $e_{1}cdot{e}_{2}cdots{e}_{n-1}$ in variables $einE$. All arborescences $mathsfarb(G)$ of a digraph then define the Kirchhoff polynomial $su{m}_{Ainmathsfarb(G)}pro{d}_{einA}e$. We show how to compute a compact representation of the Kirchhoff polynomial -- its prime factorization, and how it relates to combinatorial properties of digraphs such as strong connectivity and vertex domination. In particular, we provide digraph decomposition rules that correspond to factorization steps of the polynomial, and also give necessary and sufficient primality conditions of the resulting factors expressed by connectivity properties of the corresponding decomposed components. Thereby, we obtain a linear time algorithm for decomposing a digraph into components corresponding to factors of the initial polynomial, and a guarantee that no finer factorization is possible. The decomposition serves as a starting point for a recursive deletion-contraction algorithm, and also as a preprocessing phase for iterative enumeration algorithms. Both approaches produce a compressed output and retain some structural properties in the resulting polynomial. This proves advantageous in practical applications such as calculating steady states on digraphs governed by Laplacian dynamics, or computing the greatest common divisor of Kirchhoff polynomials. Finally, we initiate the study of a class of digraphs which allow for a practical enumeration of arborescences. Using our decomposition rules we observe that various digraphs from real-world applications fall into this class or are structurally similar to it.

Recommendations

• On tree factorizations of K_n
• On the enumeration of polynomials with prescribed factorization pattern
• A factorization of the Conway polynomial
• Factorization of polynomials given by arithmetic branching programs
• Factorization of polynomials given by arithmetic branching programs
• The arithmetic of prime degree trees
• Polynomial configurations in the primes
• scientific article; zbMATH DE number 937020
• A generalization of the results of Kreweras on the enumeration polynomial of inversions in arborescences
• On Factor Prime Factorizations for <formula formulatype="inline"> <tex>$n$</tex></formula>-D Polynomial Matrices

Cited in

(4)

• Arborescences of covering graphs
• Listing subgraphs by Cartesian decomposition
• Strong connectivity in directed graphs under failures, with applications
• Factorization of \(K_{n,n}\) into \((0,j)\)-prisms

This page was built for publication: Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences

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