6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

This lecture is about Hamiltonicity (paths/cycles that visit every vertex exactly once). In particular, we'll see a very special and useful case that is NP-hard: grid graphs, defined by a set of points on a grid, with edges exactly when two points have unit distance. This version is hard for square, triangular, and hexagonal grids. We'll prove this and see how to reduce to other fun problems like optimally mowing your lawn, 3D printing, Settlers of Catan, and Nikoli puzzles Slitherlink and Hashiwokakero.