Structural sparsity, admissibility, computing short path packings

Two-sentence summary: I describe a $(k \cdot \ell^2)^{k \cdot \ell} \cdot n^{O(1)}$-time search-tree algorithm for determining whether there is a packing of $k$ paths of length at most $\ell$ in a given graph with $n$ vertices. I’ll explain how this problem is motivated by research into the structural sparsity of graph classes.

There have recently been some attempts at testing whether real-world graph classes are structurally sparse [1, 2, 3]. Structural sparsity is a way of capturing sparsity in a way that is theoretically robust and algorithmically useful. One way to phrase structural sparsity is roughly that we can find a vertex ordering, such that each vertex $v$ connects only to few vertices within a small distance before $v$ in the ordering. Computing such orderings helps us check how some parts from the theory of structural sparsity may eventually apply to practice and it could directly be useful for example for counting graph motifs (small subgraphs) [4]. One indication that this is a robust field of study is that computing similar orderings is also being noticed from other directions [5].

A related new approach towards testing structural sparsity is to compute the so-called admissibility of a graph [2, 3]. The advantage compared to previous ones is that it is much easier to formulate and, as we will see below, seems to be easier to work with.

Fix some integer $r$, which in the context of sparsity determines the degree of locality with which we are looking at our graph (or graph class). Let $v_1, v_2, \ldots, v_n$ be an ordering of the vertices of a graph $G$. The $r$-admissibility of this ordering is the maximum, taken over all vertices $v$, of the largest number of vertex-disjoint paths from $v$ to vertices earlier in the ordering. Now the $r$-admissibility of a graph $G$ is the smallest admissibility of a vertex ordering of $G$.

Computing the $r$-admissibility of a graph reduces to greedily iteratively placing at the beginning of a partial ordering $\pi$ a vertex $v$ with the smallest number of internally vertex-disjoint paths of length at most $r$ to vertices that have not yet been placed. If this was not the case, that is, a greedily placed vertex $v$ does not satisfy this condition, then we can look at an extension of $\pi$ with smallest admissibility, move $v$ backwards to where we would have placed it in our greedy strategy. The admissibility has to increase. But all the vertices after $v$ (after moving) have the same number of paths to before them. A vertex $u$ before $v$ (after moving) can get a new path to before $u$ only via $v$. But then this path was already present before moving $v$. This is a contradiction to our assumption that the admissibility increased by moving $v$ and so indeed our greedy strategy works.

So to compute the admissibility, we iteratively need to compute maximum vertex-disjoint packings of paths from some vertex $v$ to some vertex set $S$. By putting $v = t$ and introducing an imaginary target vertex $s$ that is adjacent to all vertices in $S$, this problem in turn reduces to the following:

Given a graph $G$, two vertices $s, t \in V(G)$, two integers $k, \ell \in \mathbb{N}$; are there $k$ internally vertex-disjoint $s$-$t$ paths in $G$, each of length at most~$\ell$?

In the remainder of the post I give an algorithm that solves this problem efficiently for small $\ell$ and $k$. In fact, the algorithm solves the following more general problem. Given are a graph $G$, an integer $k \in \mathbb{N}$, and for each $i \in [k]$ a triple $(s_i, t_i, \ell_i)$ of two vertices $s_i, t_i \in V(G)$ and an integer~$\ell_i \in \mathbb{N}$. The question is whether there are $k$ paths $P_1, P_2, \ldots, P_k$ in $G$ such that for each $i \in [k]$, path $P_i$ starts in $s_i$, ends in~$t_i$, and has length at most $\ell_i$ and such that each pair of paths $P_i$, $P_j$ are disjoint except for their endpoints (that is, $V(P_i) \cap V(P_j) \subseteq \{s_i, t_i\} \cap \{s_j, t_j\}$)?

We refer to a set $(P_i)_{i \in [k]}$ of paths as above as a solution. The single-pair problem SPP reduces to MTSPP by setting, for each $i \in [k]$, the triple $(s_i, t_i, \ell_i) = (s, t, \ell)$.

Theorem. MTSPP can be decided in $(k \cdot \ell^2)^{k \cdot \ell} \cdot n^{O(1)}$ time, where $\ell = \sum_{i \in [k]}\ell_{i}$ and $n = |V(G)|$.

I prove this using a search tree. Each node corresponds to one MTSPP instance. At a node $N$, the algorithm first tries a greedy construction; if that fails, it branches into a bounded number of smaller MTSPP instances.

For node instance $(G, k, (s_i, t_i, \ell_i)_{i \in [k]})$, do:

1. For $i = 1, 2, \ldots, k$, define $$G_i = G \setminus \left(\left(\bigcup_{i' \in [i-1]}V(P_{i'})\right)\setminus\{s_i,t_i\}\right).$$
2. Compute a path $P_i$ in $G_i$ from $s_i$ to $t_i$ of length at most $\ell_i$ (or fail if none exists). This is a BFS subroutine.
3. If all $P_i$ are found, output $(P_i)_{i \in [k]}$.
4. Otherwise let $i_{\mathrm{break}}$ be the first index where no path was found, and branch as described below.

Observation (intersection lemma). If the greedy loop breaks at $i_{\mathrm{break}}$ and a solution $(P_i^\star)_{i \in [k]}$ exists, then $P_{i_{\mathrm{break}}}^\star$ contains an internal vertex that is also an internal vertex of some previously found greedy path $P_i$ with $i < i_{\mathrm{break}}$. Formally: $$\left(V(P_{i_{\mathrm{break}}}^{\star}) \setminus \{s_{i_{\mathrm{break}}}, t_{i_{\mathrm{break}}}\}\right) \cap \bigcup_{i \in [i_{\mathrm{break}} - 1]}\left(V(P_i)\setminus\{s_i,t_i\}\right) \neq \emptyset.$$

The proof is by contradiction: otherwise $P_{i_{\mathrm{break}}}^\star$ would be contained in $G_{i_{\mathrm{break}}}$, so the BFS step would have found a feasible path.

Branching rule. For every $$v_{k+1} \in \bigcup_{i \in [i_{\mathrm{break}} - 1]}(V(P_i)\setminus\{s_i,t_i\})$$ and every $\ell_{k+1} \in \mathbb{N}$ with $\ell_{k+1} < \ell_{i_{\mathrm{break}}}$, create a child instance by:

1. Keeping all triples $(s_i,t_i,\ell_i)$ for $i \in [k] \setminus \{i_{\mathrm{break}}\}$.
2. Replacing $(s_{i_{\mathrm{break}}}, t_{i_{\mathrm{break}}}, \ell_{i_{\mathrm{break}}})$ by $(s_{i_{\mathrm{break}}}, v_{k+1}, \ell_{i_{\mathrm{break}}}-\ell_{k+1})$.
3. Adding $(v_{k+1}, t_{i_{\mathrm{break}}}, \ell_{k+1})$ as a new $(k+1)$-st triple.

This rule is safe: The original instance is solvable iff at least one child instance is solvable (split at a guessed intersection vertex, and conversely concatenate the split paths).

Apply the greedy phase plus branching repeatedly until either some $\ell_i=0$ (dead end) or a full solution is found.

For the running time, use the measure $$\mu(N)=\sum_{i \in [k]} \ell_i - 1.$$ Then $\mu(N) \le k\cdot \ell$, each branching step creates at most $\mu(N)\cdot \ell$ children, and every child decreases the measure by at least one. Therefore the search tree has at most $(k \cdot \ell^2)^{k \cdot \ell}$ nodes, giving total running time $(k \cdot \ell^2)^{k \cdot \ell} \cdot n^{O(1)}$.

I advised Michael Huber who wrote his thesis [6] about packing short paths. He wrote a clean version of the above algorithm, improved it, and implemented the result. I just now compared this with a straightforward ILP and Michael’s work seems to outperform the ILP by quite a bit.

1. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Nadara, W., Pilipczuk, M., Rabinovich, R., Reidl, F., Siebertz, S. ACM Journal of Experimental Algorithmics. 24, 2.6:1–2.6:34 (2019).
2. A Practical Algorithm for 2-Admissibility, Awofeso, C., Greaves, P., Lachish, O., Reidl, F. In: 23rd International Symposium on Experimental Algorithms, SEA 2025, Venice, Italy, July 22-24, 2025. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2025).
3. A Practical Algorithm for 3-Admissibility, Awofeso, C., Greaves, P., Lachish, O., Reidl, F. In: SOFSEM 2026: Theory and Practice of Computer Science - 51st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2026, Kraków, Poland, February 9-13, 2026, Proceedings. Springer (2026).
4. ESCAPE: Efficiently Counting All 5-Vertex Subgraphs, Pinar, A., Seshadhri, C., Vishal, V. In: Proceedings of the 26th International Conference on World Wide Web (WWW 2017). International World Wide Web Conferences Steering Committee (2017).
5. Mind the Gap When Searching for Relaxed Cliques, Wünsche, N. (2021).
6. How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length, Huber, M.K. CoRR. abs/2404.10469, (2024).