Emit As You Go: Enumerating Edges of a Spanning Tree
Katrin Casel, Stefan Neubert · 2025
Read Emit As You Go: Enumerating Edges of a Spanning Tree by Katrin Casel, Stefan Neubert (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10279.txt.
Introduction
Planning is usually split into making the whole plan and then executing it, but when planning is slow, emitting the plan piece by piece saves time. Katrin Casel and Stefan Neubert study that idea — enumeration with tiny delay between outputs — for the minimum spanning tree, where the pieces are the tree's edges. They cover all four variants: weighted or not, directed or not.
For three variants they give algorithms whose delay stays small, and they prove matching lower bounds showing no one can do fundamentally better. For the fourth — graphs that are both weighted and directed — they prove meaningful enumeration is impossible. Experiments on random graphs confirm the theory's practical edge. The work draws a crisp line around when 'emit as you go' planning can work at all.
Catalog record
| CREATOR | Katrin Casel, Stefan Neubert |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-10279
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Emit As You Go: Enumerating Edges of a Spanning Tree Katrin Casel, Stefan Neubert Abstract Classically, planning tasks are studied as a two-step process: plan creation and plan execution. In situations where plan creation is slow (for example, due to expensive information access or complex constraints), a natural speed-up tactic is interleaving planning and execution. We implement such an approach with an enumeration algorithm that, after little preprocessing time, outputs parts of a plan one by one with little delay in-between consecutive outputs. As concrete planning task, we consider efficient connectivity in a network formalized as the minimum spanning tree problem in all four standard variants: (un)weighted (un)directed graphs. Solution parts to be emitted one by one for this concrete task are the individual edges that form the final tree. We show with algorithmic upper bounds and matching unconditional adversary lower bounds that efficient enumeration is possible for three of four problem variants; specifically for undirected unweighted graphs (delay in the order of the average degree), as well as graphs with either weights (delay in the order of the maximum degree and the average runtime per emitted edge of a total-time algorithm) or directions (delay in the order of the maximum degree). For graphs with both weighted and directed edges, we show that no meaningful enumeration is possible. Finally, with experiments on random undirected unweighted graphs, we show that the theoretical advantage of little preprocessing and delay carries over to practice. Humboldt Universität zu Berlin, [email protected]://orcid.org/0000-0001-6146-8684 Hasso Plattner Institute, University of Potsdam, [email protected]://orcid.org/0000-0001-9148-6592 ccs Theory of computation Graph algorithms analysis keywords solution part enumeration, preprocessing vs. delay, spanning tree † † runningauthor: K. Casel and S. Neubert † † copyright: Katrin Casel and Stefan Neubert † † supplement: The source code for our experiments is published as follows (including algorithm implementations and generators for random input instances): † † supplement: Software: https://github.com/Steditor/Enumeration-of-Solution-Parts 1 Introduction In many complex planning settings, such as path finding for robots in a storage facility, the combined time of planning and execution determines the overall efficiency. A natural way of optimizing this is to start execution before fully finishing planning [ 45 , 32 ] . This approach generalizes to all kinds of multi-step processes, in which the output of an early step is needed to start working on a later one. In fact, with large input instances it can even be beneficial to employ an algorithm with worse total-time, if that algorithm produces the solution in the form of many solution parts and (while still running) emits them for following steps to process [ 27 ] . But how much speedup can actually be gained by this approach? We tackle this question for one of the most fundamental problems on networks: cost-efficient connectivity. Be it networks for communication, electricity, transport or water supply – both for planning problems and for the analysis of existing infrastructure it is a central task to connect every node to all other nodes by a Minimum Spanning Tree (MST). Besides being useful as output on their own, MSTs are also used as input for many complex algorithmic tasks, e. g. for Coverage Path Planning [ 39 ] , or in data analytics for graph-based clustering [ 44 , 18 ] , and for image segmentation [ 14 ] . Naturally, there is an extensive history of research on the complexity of computing a (minimum) spanning tree for (un)directed and (un)weighted graphs – that is if by complexity one refers to the total-time complexity of the problem: How many computation steps does it take in total to produce a complete solution as output? With the above motivation of starting next steps early , recently several core algorithmic problems have been analyzed using terminology from enumeration complexity [ 38 ] : How much preprocessing time does it take at most to produce a first part of the solution, and what is the worst case delay in-between two consecutive solution parts that are emitted? (Note that in contrast to classical enumeration this question does not ask to enumerate all solutions to an input instance, but to enumerate all parts of a single solution.) Ideally, an algorithm does not need to spend any time on preprocessing but is able to immediately emit solution parts with little delay. On the other end of the spectrum are problems for which the time to compute even the first few parts of a solution is in the same order as the time required to solve the problem completely. The goal therefore is to understand possible tradeoffs between preprocessing time and delay. 10^{2} 10^{3} 10^{4} 10^{5} 10^{5} 10^{10} Number of vertices CPU time in ns e-first e-total prim-total Figure 1: Time to first output and total time of MST enumeration (e) compared to the runtime of Prim’s MST algorithm. Among the problems studied with this perspective are incremental sorting [ 34 , 30 ] , shuffling [ 6 ] , computation of all pairs shortest distances in a graph [ 7 ] and finding a topological ordering in a directed acyclic graph for solving scheduling problems [ 32 ] . Interestingly, one of the applications of incremental sorting is speeding up total-time MST algorithms; improved also as Filter Kruskal in [ 33 ] . While these algorithms employ the incremental idea for sub problems, we go one step further and discuss MST itself in terms of enumerating solution parts. Our Contribution We present a family of efficient algorithms that enumerate edges of a spanning tree for a given input graph. For MSTs of weighted undirected graphs, we experimentally confirm in Section 4 that our enumeration approach leads to a smaller time to a first emitted solution part and small delay in practice, with only a constant overhead in the total time (see Figure 1 ). We complement the algorithmic results with lower bounds to almost completely characterize the complexity of enumerating the edges of a spanning tree for a connected graph with n vertices and m edges. Table 1 summarizes our results for all typical edge types: • Undirected unweighted edges allow for a delay in the order of the average degree \overline{\Delta} ; we derive a matching lower bound from the best possible total-time algorithm ( Section 3.1 ). • For undirected weighted edges we show a lower bound in the order of the maximum degree \Delta on either preprocessing time or delay. We also present algorithms that, for small \Delta or with O(n) preprocessing time, homogeneously spread out the computation time \mathcal{T} of a total-time algorithm for minimum spanning trees and emit the n-1 solution parts with delay in O(\frac{\mathcal{T}}{n}) ( Section 3.2 ). • Given a directed unweighted graph along with the root for a spanning tree, computing a shortest path tree with delay in the order of the maximum out-degree \Delta^{+} [ 7 ] solves the problem with optimal delay, as we show with a matching lower bound ( Section 3.3 ) • Without given root or when the graph has directed weighted edges, no algorithm can emit any part of a solution after less than \Omega(m) time. For unweighted edges this already matches the total time needed to solve the instance. But also the