Prove NP-Completeness of generating 2 shortest routes over given edge grouping constraints?

Question

I've been trying unsuccessfully to the following problem is NP-Complete or NP-Hard.

The problem is as follows:

You are given a graph G(V,E) and asked to generate two routes from starting node S to node T. The edges E are split into K disjoint sets. Let us refer two the routes as R1 and R2. There can be no edges E1 and E2 in the same set such that E1 is in the path R1 and E2 is in R2 (in simpler terms each set must be used by no more than one of the routes). Additionally there can be no nodes shared between R1 and R2. We are seeking the shortest combined path length of R1 and R2 (Minimize (len(R1) + len(R2)) ).

I have tried reducing Subset Sum and Independent Set to this with no success.

Answer 1

For starters, thanks for posting a seriously interesting problem. This was a lot of fun to work through!

The reduction I've come up with is from 3SAT to your problem. Intuitively, the reduction works as follows: we build a graph consisting of two parallel, cascading series of nodes (let's call them the left and the right branches). The left branch edges correspond to the variables in the formula and the right branch corresponds to the clauses in the formula. We'll build the graph such that the two paths correspond to choosing a variable assignment for the formula that satisfies all the clauses.

The left branch, which forces variables to take on values, is build as follows. For each variable x, build a gadget that looks like this:

              *
  true -->   / \  <-- false
            *   *
             \ /
              *

Starting at the top node, we'll have "left" mean "x is true" and "right" mean "x is false." We'll build one copy of this gadget for each variable and link them from top to bottom. Therefore, a path from the top of the chain down to the bottom corresponds to choosing a variable assignment for the propositional formula.

The right branch is built similarly. Suppose we have a clause x &lor; y &lor; z. We then build this gadget:

              *
             /|\
            * * *
             \|/
              *

Here, the left branch corresponds to "x is true," the middle branch corresponds to "y is true", and the right branch corresponds to "z is true." The idea is that we need to have at least one true literal per clause, and we'll choose which literal that is by choosing which path to go down.

Now, we build the constrain sets. For each variable x, we want to ensure that if in the left branch we say that x is true, we don't follow an edge in the right branch where x is supposed to be false. Therefore, we'll create a constraint set containing the edge "x is true" from the left branch and all copies of "x is false" from the right branch. We'll similarly create a second constrain set containing the edge "x is false" from the left branch and all edges marked "x is true" from the right branch. These constraint sets collectively ensure that if we take a path through the left branch and through the right branch, we chose a value for every variable (the path through the left branch) and picked at least one true literal per clause (the path through the right branch).

To finish everything, we'll create a new start node S and a new terminal node T, linking S to the first node in the left branch and the first node in the right branch and linking the last node in the left and right branches to T. Now, there's a satisfying assignment to the formula if and only if there are two node-disjoint paths from S to T respecting all the constraints. Doing some quick math shows that if the formula has n variables and m clauses, then the length of the path through the left branch will be 2n + 2 and the length of the path through the right branch will be 2m + 2, so the formula is satisfiable if and only if there's a pair of node-disjoint paths from S to T of combined length 2n + 2m + 4. Note that there isn't a legal path at all if the formula isn't satisfiable.

Hope this helps!