Skip to main content
4 votes

Find the transitive closure but with a twist

Your problem (called path avoiding forbidden pairs problem) is NP-hard. Here is a reduction from the CNF SAT problem. We construct a set of relations such that $s \mathbin{R'} t$ if and only if a ...
pcpthm's user avatar
  • 2,727
1 vote

BFS on directed graph with disjointed edges?

Assuming you want the following: Given a graph $G=(V,E)$ and a set of nodes $N \subseteq V$, find a tree $T$ that spans over all nodes in $N$. Here, $T$ is a spanning tree of the induced subgraph of a ...
codeR's user avatar
  • 1,457
1 vote

How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path

The problem of finding 2 disjoints paths from $s_1$ to $t_1$ and from $s_2$ to $t_2$ is NP-complete for directed graphs. Your problem is therefore NP-complete. Reduction: Given an instance of 2-...
Pål GD's user avatar
  • 16.7k

Only top scored, non community-wiki answers of a minimum length are eligible