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.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Yes it is NP-Complete. $\endgroup$
    – Chandra Chekuri
    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$
    – Narek Bojikian
    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$
    – Kristoffer Arnsfelt Hansen
    Dec 19, 2019 at 15:05

1 Answer 1

Reset to default
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$.

Improve this answer
$\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.