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

Prof. Erik Demaine TAs: Josh Brunner, Lily Chung, Jenny Diomidova

[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

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).
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; betweenness; bipartite crossing number, crossing number, Rubik's Cube.

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)

In class, I'll give a brief overview of the Polynomial Hierarchy (classes Σ_k and Π_k), which provide more of a continuum between NP and PSPACE.

Download Video: 360p, 720p

Handwritten notes, page 1/6 • [previous page] • [next page] • [PDF]

Slides, page 1/23 • [previous page] • [next page] • [PDF]

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

Slides, page 1/23 • [previous page] • [next page] • [PDF]