## 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},..,e_{n-1} can be represented as a monomial e_{1}·e_{2} ⋯e_{n-1} in variables e ∈ E. All arborescences arb(G) of a digraph then define the KirchhofF polynomial ∑ A_{∈arb(G)} ∏_{e∈A}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 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 language | English |
---|---|

Title of host publication | 13th Workshop on Analytic Algorithmics and Combinatorics 2016, ANALCO 2016 |

Publisher | Society for Industrial and Applied Mathematics Publications |

Pages | 93-105 |

Number of pages | 13 |

ISBN (Electronic) | 9781510819696 |

Publication status | Published - 2016 |

MoE publication type | A4 Article in a conference publication |

Event | Workshop on Analytic Algorithmics and Combinatorics - Arlington, United States Duration: 11 Jan 2016 → 11 Jan 2016 Conference number: 13 |

### Workshop

Workshop | Workshop on Analytic Algorithmics and Combinatorics |
---|---|

Abbreviated title | ANALCO |

Country | United States |

City | Arlington |

Period | 11/01/2016 → 11/01/2016 |