6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza]

Lecture 9 Video     [previous] [next]

[+] Graph Problems.
Vertex Cover: planar max-degree-3; exact vertex cover (polynomial), edge cover (polynomial), connected vertex cover, rectilinear Steiner tree.
Vertex Coloring: planar max-degree-4 3-coloring, max-degree-3 3-coloring (polynomial), Push-1X, Push-1G (gravity).
Graph Orientation: 1-in-3, 2-in-3, 0-or-3 vertices; packing trominoes.
Graph Layout: Bandwidth, minimum linear arrangement, cutwidth, vertex separation, sum cut, edge bisection, vertex bisection; bipartite crossing number, crossing number, Rubik's Cube.
[Scribe Notes] [src]

This lecture is our last about straight-up NP-hardness. We've already seen the main techniques for such proofs, but there are a few other techniques that get used now and then. We will see three:

  • Vertex cover, in particular planar vertex cover and planar connected vertex cover
  • Vertex coloring, in particular planar max-degree-4 3-coloring
  • Graph orientation, about assigning edge directions to satisfy vertex constraints.
In particular, we will use these techniques to prove hardness of
  • Rectilinear Steiner tree
  • Pushing-block puzzles Push-1X and Push-1G (gravity)
  • Crossing number
  • A version of Rubik's Cube (just a rough sketch)

Download Video: 360p, 720p

Handwritten notes, page 1/7[previous page][next page][PDF]

Handwritten notes, page 1/7[previous page][next page][PDF]

Slides, page 1/31[previous page][next page][PDF]

http://​dx.doi.org/​10.1137/​0211025

Slides, page 1/31[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.