Quota Trees
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916080291676160 |
|---|---|
| author | White, Tad |
| author_facet | White, Tad |
| contents | We introduce the notion of quota trees in directed graphs. Given a nonnegative integer ``quota'' for each vertex of a directed multigraph $G$, a quota tree is an immersed rooted tree which hits each vertex of $G$ the prescribed number of times. When the quotas are all one, the tree is actually embedded and we recover the usual notion of a spanning arborescence (directed spanning tree). The usual algorithms which produce spanning arborescences with various properties typically have (sometimes more complicated) ``quota'' analogues.
Our original motivation for studying quota trees was the problem of characterizing the sizes of the Myhill-Nerode equivalence classes in a connected deterministic finite-state automaton recognizing a given regular language. We show that the obstruction to realizing a given set of M-N class sizes is precisely the existence of a suitable quota tree.
In this paper we develop the basic theory of quota trees. We give necessary and sufficient conditions for the existence of a quota tree (or forest) over a given directed graph with specified quotas, solving the M-N class size problem as a special case. We discuss some potential applications of quota trees and forests, and connect them to the $k$ lightest paths problem. We give two proofs of the main theorem: one based on an algorithmic loop invariant, and one based on direct enumeration of quota trees. For the latter, we use Lagrange inversion to derive a formula which vastly generalizes both the matrix-tree theorem and Cayley's formula for counting labeled trees. We give an efficient algorithm to sample uniformly from the set of forests with given quotas, as well as a generalization of Edmonds' algorithm for computing a minimum-weight quota forest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_01462 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quota Trees White, Tad Combinatorics 05C30, 05C85, 68R10 We introduce the notion of quota trees in directed graphs. Given a nonnegative integer ``quota'' for each vertex of a directed multigraph $G$, a quota tree is an immersed rooted tree which hits each vertex of $G$ the prescribed number of times. When the quotas are all one, the tree is actually embedded and we recover the usual notion of a spanning arborescence (directed spanning tree). The usual algorithms which produce spanning arborescences with various properties typically have (sometimes more complicated) ``quota'' analogues. Our original motivation for studying quota trees was the problem of characterizing the sizes of the Myhill-Nerode equivalence classes in a connected deterministic finite-state automaton recognizing a given regular language. We show that the obstruction to realizing a given set of M-N class sizes is precisely the existence of a suitable quota tree. In this paper we develop the basic theory of quota trees. We give necessary and sufficient conditions for the existence of a quota tree (or forest) over a given directed graph with specified quotas, solving the M-N class size problem as a special case. We discuss some potential applications of quota trees and forests, and connect them to the $k$ lightest paths problem. We give two proofs of the main theorem: one based on an algorithmic loop invariant, and one based on direct enumeration of quota trees. For the latter, we use Lagrange inversion to derive a formula which vastly generalizes both the matrix-tree theorem and Cayley's formula for counting labeled trees. We give an efficient algorithm to sample uniformly from the set of forests with given quotas, as well as a generalization of Edmonds' algorithm for computing a minimum-weight quota forest. |
| title | Quota Trees |
| topic | Combinatorics 05C30, 05C85, 68R10 |
| url | https://arxiv.org/abs/2401.01462 |