1
$\begingroup$

So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component.

My idea is: In a strongly connected component we can get from one vertex to every other vertex.

If we start at some vertex u then we can visit each of the remaining n-1 vertices by going from the vertex we are currently on to some adjacent vertex, setting the vertex we reach as the current one and repeating until we have no unvisited vertices left. As such the longest path always has length n-1.

Another idea is that we can run depth first search on the connected component and the highest level found will be the length of the longest path.

Intuitively these ideas make sense to me but not sure how to structure them formally or even if they are right. Could I get some guidance on this?

$\endgroup$
1
  • 1
    $\begingroup$ I assume that you are referring to simple paths (as otherwise the length of the longest path is undefined as soon as the connected component has at least $2$ vertices). The statement "The longest path always has length $n-1$" is false. As a counterexample consider the directed graph obtained by starting from an undirected star on $n\ge 4$ vertices and replacing each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$. Here the length of the longest (simple) path is $2$ but $n-1 > 2$. $\endgroup$
    – Steven
    Feb 8 at 23:27
1
$\begingroup$

You won't be able to find any efficient algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.

Consider an instance of Hamiltonian path: given a graph $H=(V,E)$ on $n$ vertices decide whether it contains a simple path of length $n-1$. This is a well-known $\mathsf{NP}$-hard problem.

Construct $G$ from $H$ by adding two vertices $x$ and $y$, the edges $(x,y)$ and $(y,x)$, and all the edges $(y,v)$ and $(v,y)$ for $v \in V$. Notice that the only strongly connected component of $G$ is $G$ itself.

There is a simple path of length $n+1$ in $G$ if and only if there is a path of length $n-1$ in $H$.

Indeed, if $P = \langle v_1, v_2, \dots, v_n \rangle$ is a path of length $n-1$ in $H$, then $\langle x, y, v_1, v_2, \dots, v_n \rangle$ is a path of length $n+1$ in $G$.

Conversely, if $P$ is a path of length $n+1$ in $G$, $P$ must have $x$ as one if its endpoints (as otherwise $x$ would have one in-neighbor and one out-neighbor in $P$, but the only in/out neighbor of $x$ is $y$, contradicting the hypothesis that $P$ is simple). Then $P$ is of the form $\langle x, y, v_1, v_2, \dots, v_n \rangle$ and $\langle v_1, v_2, \dots, v_n \rangle$ is a path of length $n-1$ in $H$.

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