# Algorithm for finding a path in a directed graph that visits each node in a given subset

I was wondering about a solution for the following problem:

Given a directed graph $$G=(V,E)$$ and a subset of vertices $$U \subseteq V$$ suggest an algorithm that finds if there is a directed path that visits every node in $$U$$. The path can revisit vertices/edges. The path can visit vertices not in $$U$$ repeatedly as well.

I was thinking about running DFS\BFS from each vertex but it feels inefficient, I'll be grateful for any insights.

Source: Open University of Israel - Algorithms course, written by Dr. Daniel Reichman, fall semester 2012-2013.

Instead of "path", Let us use "walk" for a sequence of edges which joins a sequence of vertices (that can revisit vertices and edges). We will reserve "path" for its usual meaning, a walk in which all vertices are distinct.

This answer describes a linear algorithm that given a directed graph $$G=(V,E)$$ and $$U \subseteq V$$, finds if there is a walk that visits every node in $$U$$. The main idea is to take advantage of the longest distances from the root in a directed acyclic graph (DAG) to speed up the search for a path.

### Reduce to a rooted DAG

Compute the condensation of $$G$$, a DAG that which is attained when each strongly-connected component of $$G$$ is contracted to a single vertex. This DAG is called "the meta-graph of strongly connected components" in D.W.'s answer. The computation can be done by any one of the linear-time algorithms.

Denote the condensation of $$G$$ by $$G'=(V', E')$$. Let $$U'$$ be the vertices in $$V'$$ that represent the strongly-connected components that contain at least one vertices in $$U$$. Since $$G'$$ is acyclic, any walk in $$G'$$ is a path.

Add a vertex $$s$$ to $$G'$$ and an edge from $$s$$ to every root of $$G'$$. (A vertex in a DAG is called root if there is no incoming edge to it). Now $$G'$$ is a connected DAG with a unique root, $$s$$.

The problem is transformed to finding if there is a (walk) path in $$G'$$ that visits every node in $$U'$$.

Replacing $$(G, V, E, U)$$ with $$(G', V', E', U')$$, we will assume henceforth that $$G$$ is is a connected DAG with the unique root $$s$$.

#### Longest distance from $$s$$ to each vertex

For each $$v\in V$$, let $$dist[v]$$ be the longest distance from $$s$$ to $$v$$, i.e., the biggest number of edges in a path from $$s$$ to $$v$$.

Here is a simple and useful property of $$dist$$. If there is an edge or a path from vertex $$v_1$$ to $$v_2$$, then $$dist[v_1].

Compute $$dist$$ using dynamic programming as follows.

1. Initialize a hash table/hash map $$dist$$ with $$dist[v] = 0$$ for all $$v\in V$$.
2. Create a topological order of all vertices. This can be done by some linear-time algorithm.
3. For every vertex $$v\in V$$ in topological order,
• For every adjacent vertex $$w$$ of $$v$$:
• if $$dist[w] < dist[v] + 1$$: $$\quad dist[w] = dist[v] + 1$$.

#### Check if there is a path from $$u_i$$ to $$u_{i+1}$$

Sort all vertices in $$U$$ by $$dist[\cdot]$$. Since $$dist[v]$$ is an integer between $$0$$ and $$|V|$$ for every vertex $$v$$, this sorting can be done in linear time with counting sort. (We can also simply select all vertices in $$U$$ from the sequence obtained in the step 2 above.)

Let $$U=\{u_1, u_2, \cdots\}$$, $$dist[u_i]\le dist[u_{i+1}]$$.

For $$i$$ from $$1$$ up to $$|U|$$, do the following:

1. If $$dist[u_i]=dist[u_{i+1}]$$, there is no wanted path. The algorithm ends.
2. do a breadth-first search (or a depth-first search) starting with $$u_i$$, in order to check if there is a path from $$u_i$$ to $$u_{i+1}$$. To speed up the search, whenever we see an edge that ends at a vertex $$w\not=u_{i+1}$$ such that $$dist[w]\ge dist[u_{i+1}]$$, we will remove that edge from $$G$$ and ignore $$w$$, since for all $$j\ge i$$, no path from $$u_j$$ to $$u_{j+1}$$ can include that edge. (Note that edge must start at a vertex with $$dist$$ smaller than $$dist[u_{i+1}]$$.)
3. If $$u_{i+1}$$ has not been reached, there is no wanted path. The algorithm ends.

When the algorithm have reached here, we know there is path from $$u_i$$ to $$u_{i+1}$$ for all $$i$$. Connecting all paths together, we obtain a path that passes all vertices in $$U$$.

Note the for-loop accesses each edge in $$U$$ at most once. Hence it takes linear time to complete the for-loop.

#### Linear-time complexity

It takes linear time to do each step of the three steps above. Hence this algorithm runs in linear time.

Some of the steps in the algorithm can be implemented faster. For example, when we compute the condensation of the original $$G$$ using Kosaraju's algorithm, we may obtain the topological order of $$V'$$ and $$U'$$ in parallel. We may also compute $$dist[\,]$$ at the same time.

• The adjective "longest" sounds contradictory to "distance". A better name for "longest distance from $s$ to $v$" could be "anti-distance from $s$ to $v$". Feb 24 at 19:05

Hint:

Work through a few small examples of graphs. Draw a few graphs with <= 8 vertices on a piece of paper, mark a subset of vertices, and check whether there is a path. See what patterns can spot from trying to solve each one by hand, one small problem at a time.

If that's not enough, here's a bigger hint:

Draw the meta-graph of strongly connected components. Do the same as above, with this additional information.

• I see, but it still staying quadratic time isn't it? Like if I were drawing the meta-graph then I would have to label the nodes of it as well (for each one of the connected components that contain a node from U), then I'll still have to check for each one of the nodes in the meta-graph that represent each component if there's a path from it to the other nodes that I have to visit Feb 19 at 11:51
• @Yarin, I suggest you spend time to write out the pseudocode and analyze the running time of the method you've come up with.
– D.W.
Feb 19 at 19:39
• +1 for the hints. However, it looks nontrivial to design a linear algorithm when the given graph is a DAG (i.e., every SCC consists of one vertex), unless we can take advantage of the "anti-distance" in a rooted DAG as shown in my answer. Feb 25 at 1:00