2024/01/02 by Tad White, White, Tad
Computer Science · #05C30 #05C85 #68R10 #Advanced Algebra and Logic #Combinatorics (math.CO) #FOS: Mathematics #Formal Methods in Verification #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2401.01462
openalex publication_date 2024/01/02 · openalex created_date 2024/01/05 · openalex updated_date 2026/07/28
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.