1
$\begingroup$

I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint.

The additional constraint is that there are $N$ sets of special edges with weight $0$ such that a path is not considered valid if it traverses one edge in a set but not the remaining edges in that set.

Note that these $N$ sets of edges are disjoint such that no edge belongs to more than one of the $N$ sets. The number of edges in each set is around 3 to 6. And there are a large number of these sets. About $50\%$ of edges belong to a set, the rest don't belong to a set and can be traversed normally.

Does such an algorithm exist? Can such an algorithm exist that is better than brute force?

Improve this question
$\endgroup$
2
  • $\begingroup$ Are these sets always paths or disjoint unions of paths? If not, doesn't that imply that a shortest 'path' may contain cycles? $\endgroup$
    – reinierpost
    Jan 19 '15 at 17:11
  • $\begingroup$ The edges in the set don't create a path on their own, they are disjoint. Yup, the shortest path may contain a cycle, but because of the constraint, traversing the path multiple times, or removing it will probably not be the best option. $\endgroup$
    – dan
    Jan 19 '15 at 22:01
4
$\begingroup$

It is $NP$-complete, and thus it is unlikely that a polynomial algorithm ("better than brute force") exists. Proof is by reduction from Hamiltonian $s-t$-Path:

Every edge in the input graph $G=(V,E)$ is given weight $1$. The graph is then duplicated, and special (weight 0) edges are added between corresponding vertices in the two graphs. We thus get two copies of the original graph, and the copies are linked by $|V|$ special edges between the two copies of the same vertex. Call these new edges the 'copy' edges.

$|V|$ vertices are added to the graph and connect in a chain with $|V|-1$ new special (weight) 0 edges. Another special (weight 0) edge is added to connect the end vertex to $s$. Call these new edges the 'chain' edges.

Partition the $2|V|$ new edges into $|V|$ edge sets that each consist of one copy edge and one chain edge.

We now try to find a shortest path between the start of the chain and vertex $t$ that satisfies your requirement of traversing either all or none of the edges from each edge set. Such a path must start by traversing the full chain, so it must contain all chain edges, so it must contain all copy edges, so it must visit every vertex of the original graph; therefore, omitting all special edges from it will produce a Hamiltonian path from $s$ to $t$, if one exists.

Deciding whether a Hamiltonian path between arbitrary edges $s$ and $t$ exists is known to be $NP$-complete, so your problem is $NP$-hard: if you can find a polynomial algorithm for it (such as Dijkstra's), you will have proved $P=NP$.

Improve this answer
$\endgroup$
15
  • $\begingroup$ Hi, I'm not sure what a Hamiltonian s−t-Path am not sure if I'm finding the correct information on google. Can you link to a page related to this so I can read up on it? $\endgroup$
    – dan
    Jan 20 '15 at 9:01
  • $\begingroup$ Hamiltonian Path is the problem of finding a path in a graph that visits all vertices exactly once. Hamiltonian s-t-Path is the same, except that the beginning and end vertices of the path are fixed, which makes the reduction slightly easier. $\endgroup$
    – Tom van der Zanden
    Jan 20 '15 at 9:20
  • $\begingroup$ You say "create a chain of V special (weight) 0 edges" but the edges are not connected, so how do you create a chain? $\endgroup$
    – dan
    Jan 20 '15 at 10:43
  • $\begingroup$ The sets you create have a weight 1 edge and a weight 0 edge. In my question, all edges in a set have weight 0. Only edges that don't belong to a set have non-zero weight $\endgroup$
    – dan
    Jan 20 '15 at 10:45
  • $\begingroup$ Why does "Such a path must traverse all special edges"? $\endgroup$
    – dan
    Jan 20 '15 at 10:46

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.