2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$ – Merk Zockerborg Mar 25 at 15:26
  • $\begingroup$ @MerkZockerborg There's a rich literature for the problem. One method you can search for is color coding. $\endgroup$ – Juho Mar 25 at 15:43
  • $\begingroup$ @MerkZockerborg, how many paths of length $k$ are there? If you were to enumerate all of them, how long would that take? $\endgroup$ – D.W. Mar 25 at 19:12
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.