# Finding paths of certain length in trees

In a graph tree, is there any "smart/existing/efficient" algorithm to find linear segments of defined length?

For example given a tree graph:

g = {1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, 6 -> 12, 1 -> 3, 2 -> 5, 3 -> 7,
4 -> 9};
TreePlot[g, VertexLabeling -> True]


How can one find all linear segments of length 4. In this example this would be

1 2 4 8
1 2 4 9
1 3 6 12
2 1 3 7
2 1 3 6
9 4 2 5
...


This is probably a common problem, but I guess I have not yet found the right keywords for google. The naive implementation would be to visit every node, then recursively try to get four nodes away and delete all duplicated segments at the end...

• What you call "linear segment" is called a path in graph theory. You are looking for all paths of length three/four (depending on whether you're counting edges or nodes). Commented Oct 7, 2014 at 5:31
• By the way, if you are looking to implement this in Mathematica, there's a new function FindPath in Mathematica 10 that should be helpful.
– Juho
Commented Oct 7, 2014 at 5:55
• @Raphael thanks, now I did find similar problem solved in Perl (perlmonks.org/?node_id=522257). Will try to decipher:) Commented Oct 7, 2014 at 8:12
• @Juho Yup, but it finds all paths between two vertices. The final implementation will be in python, but mathematica was the quickest way to generate an image. Commented Oct 7, 2014 at 8:14
• @Ajasja You can also specify the function to find all paths of length $k$ between a pair of vertices. Using this, you can find all paths of length $k$. But this is a bit off-topic :)
– Juho
Commented Oct 7, 2014 at 9:14

Idea: Root the tree in an arbitrary node. For every node, count

• paths in its subtrees,
• paths that start in a subtree and end in the root, and
• paths that start in one subtree, traverse the root and end in another subtree.

That is, for a given node $v$ with children $u_1, \dots, u_m$, the number $p(v,k)$ of paths of length $k$ (counting nodes) in the subtree $T_v$ rooted in $v$ is

\qquad\displaystyle\begin{align*} p(v,k) &= \sum_{i=1}^m \biggl[ p(u_i,k) \biggr] \\ &\ + \sum_{i=1}^m \biggl[ p_r(u_i,k-1) \biggr] \\ &\ + \sum_{i=1}^{m-1} \sum_{j=i+1}^m \sum_{l=1}^{k-2} \biggl[ p(u_i,l) \cdot p(u_j,k-1-l) \biggr] \end{align*}

for $k \geq 2$; we anchor the recurrence in $p(v,1) = 1$ for all $v$. For the paths ending in the root, we get the (simpler) recurrence

\qquad\begin{align*} p_r(v,k) &= \sum_{i=1}^m p_r(u_i,k-1) \end{align*}

which also anchors in $p_r(v,1) = 1$.

These recurrences immediately imply a recursive algorithm (computing both simultaneously).

The runtime is in "$\Theta(m^2k)$" per node of degree $m$; hence, on trees with finitely bounded degree, the algorithm runs in time $\Theta(nk)$. Otherwise, it may take time $\Theta(n^2k)$ (e.g. on stars).

• Okay, this algorithm only counts the paths; I hope it's clear how to adapt it so that the actual paths are constructed (read $+$ as $\cup$ and $\cdot$ as concatenation, and anchor in $p_{(r)}(v,1) = [v]$). As long as the node labels are pairwise distinct, this never generates the same path (as label sequence) twice. Commented Oct 7, 2014 at 5:54

Any linear segment goes up for some length, then goes down. (Once you start going down, you can't go back up again, because you'd re-visit a vertex you'd already visited).

So, any linear segment of length four consists of an upwards-heading segment of length $\ell$ (where $0 \le \ell \le 4$), followed by a downwards-heading segment of length $4-\ell$. Therefore, the following algorithm works:

• For each vertex $v$ in the tree:

• For each $\ell \in \{0,1,2,3,4\}$:

• For each upwards-heading segment $s$ of length $\ell$ that has $v$ as its top vertex:

• For each upwards-heading segment $t$ of length $4-\ell$ that has $v$ as its top vertex:

• Output the concatenation of $s$ and $t$ (i.e., the reverse of $s$, followed by $t$).

To make this work, we need some way to enumerate all upwards-heading segments of length $\ell$ that end at a vertex $v$. This can be done by enumerating all children that are $\ell$ levels below $v$; for each such child $c$, we can go upwards $\ell$ times (following parent pointers), and that gives such a segment. Moreover, every such segment can be obtained in this way.

The overall running time will be $O(n^2)$, where $n$ is the number of vertices in your tree.