Minimum Weight Triangulation is NP-hard

I just saw a new paper by Mulzer and Rote: Minimum-weight triangulation is NP-hard. This closes off one of a very small number of open problems from Garey and Johnson's book on NP-completeness, still open until now. It's in distinguished company, as the other questions left on the list include integer factorization and graph isomorphism; compared to these, MWT is more of a curiosity (other triangulations are more useful in applications) but one with a long history, and it's good to see it finally solved.

The proof is apparently a standard gadget-based reduction from a planar 3-SAT variant, using known MWT heuristics to prove that certain edges must be used in any MWT of each gadget, as had been suggested by Beirouti and Snoeyink in 1998; Snoeyink had found a gadget that could be used as a wire in a 3-SAT reduction, but not enough other gadgets to complete the proof. However, in contrast to most gadget-based NP-completeness proofs, the new gadgets are extremely complex. As with the proofs of the four-color theorem for coloring planar graphs and Kepler's conjecture for densest sphere packing, the new proof involves some computer calculations to check that the intended triangulations of the gadgets have lengths less than those of any erroneous triangulation, so it doesn't look like it's in a state to be verified purely by hand yet.

ETA: Suresh weighs in, and points out that Lance points out that factorization was not on Garey and Johnson's original list. But it should have been.

Comments: