Prime factorization of the Kirchhoff polynomial: Compact enumeration of arborescences

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

7 Citations (Scopus)

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 e1,..,en-1 can be represented as a monomial e1·e2 ⋯en-1 in variables e ∈ E. All arborescences arb(G) of a digraph then define the KirchhofF polynomial ∑ A∈arb(G)e∈Ae. 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 symbolically deriving 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 allows 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.

Original languageEnglish
Title of host publication13th Workshop on Analytic Algorithmics and Combinatorics 2016, ANALCO 2016
PublisherSociety for Industrial and Applied Mathematics Publications
Pages93-105
Number of pages13
ISBN (Electronic)9781510819696
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventWorkshop on Analytic Algorithmics and Combinatorics - Arlington, United States
Duration: 11 Jan 201611 Jan 2016
Conference number: 13

Workshop

WorkshopWorkshop on Analytic Algorithmics and Combinatorics
Abbreviated titleANALCO
CountryUnited States
CityArlington
Period11/01/201611/01/2016

Fingerprint Dive into the research topics of 'Prime factorization of the Kirchhoff polynomial: Compact enumeration of arborescences'. Together they form a unique fingerprint.

Cite this