Uploaded April 2018 | Updated November 2026, 5 days ago
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS6160 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs6160/ and other related videos at http://www.cs.virginia.edu/robins/videos.html
Specific topics covered in this lecture: NP-completeness of planar graph 3-colorability, "gadget"-based proof, 3-colorability constraint propagation, NP-completeness of max-degree-4 planar graph 3 colorability, combining parameter constraints, composing reductions, four-color theorem, computer-generated proofs, planarity testing in linear time, colorability on torus-embedable graphs, coloring theorems for other manifolds, applications of graph coloring, optimization and local minima, heuristics and approximations, "wishful thinking" algorithms, 2*OPT vertex cover heuristic, practical optimizations, meta-heuristics, some NP-complete problems are not approximable, approximation-preserving transformations, 2*OPT approximation heuristic for maximum cuts, trying to avoid getting trapped in local minima, preview of provably-good TSP heuristics, approximating proofs and zero-knowledge protocols
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS6160 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs6160/ and other related videos at http://www.cs.virginia.edu/robins/videos.html
Specific topics covered in this lecture: NP-completeness of planar graph 3-colorability, "gadget"-based proof, 3-colorability constraint propagation, NP-completeness of max-degree-4 planar graph 3 colorability, combining parameter constraints, composing reductions, four-color theorem, computer-generated proofs, planarity testing in linear time, colorability on torus-embedable graphs, coloring theorems for other manifolds, applications of graph coloring, optimization and local minima, heuristics and approximations, "wishful thinking" algorithms, 2*OPT vertex cover heuristic, practical optimizations, meta-heuristics, some NP-complete problems are not approximable, approximation-preserving transformations, 2*OPT approximation heuristic for maximum cuts, trying to avoid getting trapped in local minima, preview of provably-good TSP heuristics, approximating proofs and zero-knowledge protocols










