# algorithm for connectivity by path of given length

Given an unweighted, undirected graph $$G=(V,E)$$ without loops or multiedges, and vertices $$v,w$$, one can use breadth-first search to check if $$v$$, $$w$$ are connected, and in particular the algorithm will return a shortest path between them. BFS has time complexity $$O(|V|+|E|)=O(|V|^2)$$.

Now let $$k$$ be some fixed integer (not part of the input). Is there an algorithm that takes $$G$$, $$v,$$ $$w$$, and checks whether there is a path between $$v$$ and $$w$$ of length $$k$$? What would be its time complexity?

The problem is NP-complete and referred to as Longest Path. It is FPT, though, so you can solve it in time polynomial in $$n$$ for fixed $$k$$.

If you want to solve it in FPT time, the easiest solution is to do color coding. The trick is two-fold.

1. Suppose that vertices are colored with $$k$$ colors, and you are looking for a rainbow-path of length $$k$$, i.e. a path where every vertex has different color. This problem can be solved by dynamic programming!

2. Repeat the following step: Randomly color the vertices of the graph with $$k$$ colors, and run the rainbow algorithm.

With probability depending only on $$k$$, if there exists a $$k$$-path, then you will output a rainbow path.

• Could you elaborate a bit more on the case when $k$ is fixed? This is the case I am interested in, and I've edited my question to reflect this. The article mentions something about 'dynamic programming' for this case. Is there a simpler approach to getting polynomial in $n$ for fixed $k$? Mar 25 at 15:26
• @MerkZockerborg There's a rich literature for the problem. One method you can search for is color coding.
– Juho
Mar 25 at 15:43
• @MerkZockerborg, how many paths of length $k$ are there? If you were to enumerate all of them, how long would that take?
– D.W.
Mar 25 at 19:12

If the required path doesn't need to be simple, then there's a dynamic programming solution. Assume that the given graph is specified by an adjacency matrix $$G$$. Let $$F_k(v, w)$$ be the answer for input $$k$$, $$v$$ and $$w$$. So we have a formula:

$$F_k(v, w) = \bigvee_u F_{k - 1}(v, u) \wedge G(u, w)$$

This kind of formula can be calculated using matrix multiplication: we use the AND operator instead of multiplication, and take the OR of them instead of the sum. Time complexity is $$O(|V|^3 \log k)$$.