4
$\begingroup$

We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully partitions $E$.

For any two vertices in $V$, I need to find the shortest path between them. The additional caveat is that no two edges which belong to the same partition may be in the path.

This has totally thwarted any polynomial algorithm I can think of. It confounds algorithms like Djikstra, because at any step during the process, it may be best to forgo the best available edge in favor of having a better choice still open in the future.

I've tried reducing it to the traveling salesman problem, and several others, but I can't quite get there. Proof-writing is not really my strongest suit. Any point towards proving this would be much appreciated.

EDIT: Yes, $S$ is a partitioning of $E$. This does seem to be perfectly analogous to rainbow graphs. Is it known that finding rainbow paths on an unweighted graph is NP-Hard?

$\endgroup$
  • 1
    $\begingroup$ "I could not come up with a polynomial-time algorithm" is probably not the best indicator for "this problem is NP-hard". $\endgroup$ – Raphael Oct 25 '16 at 8:17
  • 3
    $\begingroup$ The problem is known as strong rainbow $st$-connectivity and is NP-complete (for many restricted graph classes). For positive news, it can be solved in $O^*(2^k)$ time and polynomial space, where $k$ is the number of colors. If you search for "strong rainbow connectivity", you will hit the relevant papers (in this exact problem, the goal is to verify whether a given edge-colored graph has a rainbow shortest path between each pair of vertices. But the results hold for the $st$-version as well). $\endgroup$ – Juho Oct 25 '16 at 19:19
  • $\begingroup$ Out of curiosity, where did the problem come up? From some application? $\endgroup$ – Juho Oct 25 '16 at 19:29
  • 2
    $\begingroup$ A paper by Chakraborty et al. gives a proof that determining whether there is any rainbow path between $s$ and $t$ is NPC. The same is true when we look for a rainbow shortest path and follows from Theorem 1.1 by reducing from a variant of 3-SAT. If you follow papers that reference the Chakraborty et al. paper, you will find many more results (disclaimer: I'm an author on some of them, and don't want to advertise my own papers). $\endgroup$ – Juho Oct 26 '16 at 14:37
  • $\begingroup$ @Juho: I see, and thanks for the link and proof idea. If you happen to know which paper proves hardness for the strong variant of the problem, I think it would make a great answer. (There's nothing wrong with linking to your own paper if it answers the question!) $\endgroup$ – j_random_hacker Oct 26 '16 at 14:53
2
$\begingroup$

If it helps, the problem you are trying to solve is looking for a "rainbow path" between the two vertices. It's a relatively new area of research, and there's now a book:

Rainbow Connections of Graphs X. Li and Y. Sun http://www.springer.com/la/book/9781461431183

Or here's an earlier paper: G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang. Rainbow connection in graphs. Mathematica Bohemica, 133(1):85–98, 2008.

The result you're looking for is likely in one of those places, something they cite, or something that cites them.

$\endgroup$
  • $\begingroup$ Rainbow colorings, on the other hand, seem to fit perfectly. However, we don't ask "is there a rainbow coloring?" but "given a coloring, is it a (strong) rainbow coloring?" (as a subquestion of actually finding all rainbow paths). This may be easier. In particular, if the former problem is NP-complete we know that the verification problem is in $P$! $\endgroup$ – Raphael Oct 25 '16 at 8:26
  • $\begingroup$ The question that is raised here is looking for the shortest rainbow path in a weighted graph, but none of the abstracts I've read in the Rainbow Connection literature have mentioned weighted graphs. It wouldn't surprise me if it's in there somewhere, though, and even if not their proof techniques may be useful in solving the problem for the weighted graph version. $\endgroup$ – tjhighley Oct 25 '16 at 12:44
0
$\begingroup$

I don't have time to come up with and write out a full proof right now, but I can think of a reduction from 3SAT that I believe will work. Suppose we have $m$ variables $x_1, \dots, x_m$ and $n$ clauses $(a_{i1} \vee a_{i2} \vee a_{i3})$, $1 \le i \le n$, $a_{ij} \in \bigcup_{1 \le j \le m}\{x_j, \bar x_j\}$. Basically, for each clause in the 3SAT instance, we make a gadget consisting of 3 paths, each containing $n$ edges and corresponding to a literal in the clause, as well as a source vertex that is connected to each of the 3 "leftmost" vertices of the paths and a target vertex that is connected to each of the 3 "rightmost" vertices of the paths. All these edges can be given unit weight. String these gadgets together "in series" -- that is, use the target vertex of the first clause's gadget as the source vertex of the second clause's gadget, etc. Finally, add an edge with huge weight between the very first source vertex and the very last target vertex. I believe that, after also constructing a partition $S$ of the edges as I describe below, the 3SAT instance will be satisfiable if and only if there is a path from the very first gadget's source vertex to the very last gadget's target vertex that is shorter than the path consisting of the single, huge-weight edge just mentioned.

The $j$-th path in the gadget for the $i$-th clause, $1 \le j \le 3$, will consist of the $n+1$ vertices $v_{i,j,1}, \dots, v_{i,j,n+1}$. The trick is to assign edges in these paths to parts in the partition $S$ in such a way that, if some clause uses an edge for some literal $x$, then no clause can construct a whole path for the negative of that same literal, $\bar x$: this will express the fundamental constraint of 3SAT, which is that no variable can be simultaneously TRUE and FALSE. (Note that $x$ may itself be a negative literal; $\bar{\bar x} = x$.)

To this end, notice that in order to build a path between the source and target of some clause's gadget, we need to use every edge on one of its 3 paths. So the core idea is: Each edge taken on the $x_p$-path in some clause forbids some edge on the $\bar x_p$-path in every clause that has such a path. Specifically, the $k$-th edge on the $x_p$-path in clause $i$ forbids the $i$-th edge on the $\bar x_p$-path in clause $k$, and vice versa, whenever both edges exist. We can achieve this by creating $mn^2$ parts $s_{p,i,k}$ in $S$, with $1 \le p \le m$ and $1 \le i, k \le n$ and assigning:

  • any edge $(v_{i,j,k}, v_{i,j,k+1})$ corresponding to a positive literal $x_p$ to part $s_{p,i,k}$, and
  • any edge $(v_{i',j',k'}, v_{i',j',k'+1})$ corresponding to a negative literal $\bar x_p$ to part $s_{p,k',i'}$ (note the permuted indices).

Assuming that no variable appears more than once in any clause (if this actually happens, it can be easily remedied with standard techniques), from this construction it should be clear that at most one positive-literal edge and at most one negative-literal edge can appear in any specific part $s_{p,i,k}$, so no $x_i$-edge conflicts with any other $x_i$-edge (in any clause), and no $\bar x_i$-edge conflicts with any other $\bar x_i$-edge (in any clause).

The remaining edges (which connect source or target vertices to path vertices) can all be put in additional singleton parts in $S$, which allows them to be chosen freely.

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