Tuesday, January 03, 2006

Minimum Weight Triangulation is NP-hard

OxDE points us to a great result: Minimum Weight Triangulation is NP-hard, by Mulzer and Rote.

OxDE has more thoughts on the result. A quick perusal reveals that
  • The gadget construction (the proof is via reduction from planar 1-in-3-SAT) is proved correct via computer. Depending on how picky you are about such things, the proof is therefore not "by hand" yet.
  • MWT is still not known to be in NP, because it is not known whether the number of bits needed to express edge lengths in an optimal solution is polynomial in the input size. They claim that their result can be extended to the case when edge weights are "rounded", and thus show NP-Completeness for this case.
If it all checks out, it's a major result, resolving the first problem on the CG Open Problems list, as well as whittling down to two the number of problems from Garey and Johnson's original list of 1412 that lie in limbo between P and NP (Factoring Precedence-constrained 3-processor scheduling and Graph Isomorphism)

Update: There were 12 open problems, not 14, and factoring was not one of them (Thanks, Lance).
Categories
Posted by Suresh Venkatasubramanian at 1/03/2006 12:26:00 AM

5 comments:

  1. Lance Fortnow1/03/2006 07:50:00 AM

    In my copy of Garey and Johnson, there are only 12 problems listed and Factoring is not one of them, just COMPOSITE NUMBER which has been settled.

    Do you have a pointer to the solutions of the other problems?

    ReplyDelete
  2. Suresh Venkatasubramanian1/03/2006 09:53:00 AM

    Ah; you are right I think. I went back and checked dsj's latest complexity column. the three open problems from the 12 original ones (according to dsj) are Graph Isomorphism and MWT. I think the article by Mulzer and Rote either has a slight mistake or is using a different list.

    thanks ! 

    Posted by Suresh

    ReplyDelete
  3. Anonymous1/04/2006 11:54:00 AM

    Just for the sake of completeness (no pun intended), in Garey and Johnson the problem of factoring is mentioned in passing in the entry for COMPOSITE NUMBER, where they comment that "... this latter problem may be harder than the basic decision problem."

    Of course they also discuss COMPOSITE NUMBER in the body of the text (although no mention of factoring), where they offer it and LINEAR PROGRAMMING as candidates for "NP-Intermediate" problems.
     

    Posted by Kurt

    ReplyDelete
  4. Suresh Venkatasubramanian1/04/2006 01:47:00 PM

    that's right. I asked David about this today at lunch, and that's what he said, that it was mentioned in passing but since COMPOSITE wasn't solved at that time, FACTORING wasn't brought up.  

    Posted by Suresh

    ReplyDelete
  5. alopatenko3/02/2006 10:53:00 AM

    Hope Johnson knows about this result
    He decided to start again his old column on NP-completeness and the first article was about problems which are not open any more 
    I give here a short review 

    Posted by Andrei Lopatenko

    ReplyDelete

Subscribe to: Post Comments (Atom)

Disqus for The Geomblog