Say I have two problems A and B.

A is the shortest path problem with positive weights

B is the shortest path problem (with potentially negative weights)

I would like to show: There is no mapping m, from B to A such that for every instance I_B of B the exact solutions for m(I_B) is the same as for I_B.

What I would like to know is where can I find proofs of this kind? How would you approach something like this?


Let's assume that the weights are integers (for both A and B), and that m must be onto. You could also assume that m must be a bijection (i.e., one-to-one and onto) and it would make no difference; the proposition you present is still false.

The reason is that all weighted digraphs (I'm assuming that's what you mean, not that it matters) are isomorphic to each other.

Let's prove: There exists a mapping m : B -> A s.t. for all instances I_B of B, the solution S(m(I_B)) = S(I_B).

To show this, we will construct this mapping m. Further, we'll show that m is a bijection.

We will divide the set of all digraphs into partitions. Each partition will contain all graphs of a particular number of nodes N, and a particular solution structure that makes all graphs in the partition isomorphic to each other, in the sense that all solutions paths are the same. (We index each node in an N-node graph from 1 to N, and consider two solution paths to be identical iff they contain exactly the same indexes in the exact same order and both have N nodes.)

Observe that each such partition has a countably infinite cardinality, due to the fact that there are infinitely many weight possibilities for each edge. (Proof omitted.)

Thus, to construct m, all we must do is map every member of a partition (in B) to another member of the corresponding partition (in A). Obviously, B contains extra graphs, but both have all partitions with the same cardinality as the set of natural numbers.

Now, we have that m is a bijection because every element in each partition of B maps to a unique element in the corresponding partition of A...and every element of every partition of B can be mapped to for each partition of A.

| cite | improve this answer | |

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.