4
$\begingroup$

Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$?

I found a couple of hardness statements of similar problems referring all to the same paper [The directed subgraph homeomorphism problem, Fortune, Hopcroft and Wyllie, 1980]. The papers include

  • two disjoint directed paths,
  • and directed simple cycle passing through two vertices.

However, it is not very clear to me, if this case reduces directly to the paper as in the case of these to problems.

$\endgroup$
3
  • 5
    $\begingroup$ Yes it is NP-Complete. $\endgroup$ Dec 19, 2019 at 2:36
  • 1
    $\begingroup$ can you provide some more resources please? the official name of the problem or a paper mentioning the problem would be very appreciated :) $\endgroup$ Dec 19, 2019 at 5:01
  • 1
    $\begingroup$ This particular case is explained in case (ii) of Theorem 2 in the Fortune, Hopcroft and Wyllie paper. $\endgroup$ Dec 19, 2019 at 15:05

1 Answer 1

6
$\begingroup$

I just found a reduction from the two disjoint paths problem. Given a directed graph $G = (V, E)$ and two pairs $(s_1, t_1)$ and $(s_2, t_2)$, we can add a new vertex $w$ to the graph and an edge from $t_1$ to $w$ and from $w$ to $s_2$.

The new graph admits a simple path from $s_1$ to $t_2$ through $w$ if and only if the original graph admits two disjoint paths one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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