Summary
This paper studies the problem of listing all paths in a directed graph one by one, so that each new path changes only a little from the previous one by adding or removing an edge. The authors define a property called inner-connectedness that exactly captures which graphs allow such stepwise listings with a fixed limit on the number of changes needed each step. They prove that for these graphs, the worst number of changes needed is at most three. When listings are required to be ordered by path length, the necessary changes depend on a new graph property called peripherality, which can be large. It is also hard to compute the minimal number of changes needed in this ordered case.
What this means in practice
- •For graph algorithm designers: Enable design of algorithms that enumerate all walks in certain graphs with minimal incremental updates between consecutive walks.
- •For software developers optimizing path traversal: Inform techniques for incremental updating of paths in navigation or network tracing tasks when the underlying graph is inner-connected.
A theory result. No direct application yet.
Authors
Antoine Amarilli, Claire David, Nadime Francis, Victor Marsault, Mikaël Monet, Yann Strozecki
Abstract
Consider a directed graph G and the (generally infinite) set Walks(G) of the walks in that graph. We are interested in ordering Walks(G) as w1, w2,... in a way that ensures that each walk is obtained from the previous one by a bounded number of elementary operations, namely, push operations (which add a new edge at either end of the walk) and pop operations (which remove the first or last edge of the walk). Our goal is to optimize the aforementioned bound, when it exists, in particular when imposing the additional requirement that walks must be ordered in increasing order of length. To this end, we introduce a condition on graphs inspired by earlier work, called inner-connectedness, which is testable in linear time; we show that inner-connected graphs are precisely those which admit bounded walk orderings. Focusing on such graphs, we then introduce and study the pp-rank and the pp-increasing-rank. Namely, the pp-rank of a graph is the best possible bound on the number of push-pop operations in a bounded walk ordering for that graph; and the pp-increasing-rank is the same where we further impose that shorter walks appear before longer walks in the ordering. We show that the pp-rank of inner-connected graphs is in fact always bounded by 3. The pp-increasing-rank of inner-connected graphs is also always finite, but it can be up to linear in the input graph. More precisely, we show that the pp-increasing-rank is related to a new parameter we introduce, the peripherality of graphs. In particular, for cyclic graphs, peripherality is related to the pp-increasing-rank up to multiplicative and additive constants. We last study how to compute these parameters, and show that while peripherality can be computed in polynomial time, the pp-increasing-rank itself is generally NP-hard to compute.