I've been reading Saxe's proof that 1-embeddability of integer weighted graphs is NP-Complete (http://www.math.columbia.edu/~dpt/RigidityREU/Saxe79EmbedNPHard.pdf Theorem 3.2). I don't understand how this proof works.

First of all, does "1-embeddability" mean mapping each vertex to the real line? What is meant by a "direction" as mentioned in Theorem 3.1?

I understand that PARTITION takes a set of integers and partitions them so that when all integers of $S_1$ are added, and when all integers in $S_2$ are added, both of these sums are the same.

In the proof of Theorem 3.2, it seems to be saying that we take this set of integers, and make them into weights of a cyclic graph. So we have one big cycle, and the edge weights are the integers. After this, I'm lost.

Why is it that the two sets $S_1$ and $S_2$ as defined add to the same thing?

And this proof is using a cyclic graph, how does it extend to general graphs? would we just remove an edge from this so its not cyclic?

  • $\begingroup$ If the problem is hard for a specific class of graphs, it's hard for any class of graphs that includes that class (e.g., the class of all graphs). $\endgroup$ Sep 25, 2013 at 23:48
  • $\begingroup$ I think I see it now...when we flatten the cycle onto the real line, then going around the cycle edges that go from left to right, and edges from right to left form the two sets...these edges add to the same length on the real number line since its just going one way, then going back, and the total distance is the same。 $\endgroup$
    – XBL
    Sep 26, 2013 at 0:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.