The previous version had a flawed definition (for Vertex Cover), which has been fixed here.

Table of Contents:

00:00 - Introduction and Prerequisites:
00:28 - Independent Set Definition
01:17 - Reducing Independent Set to/from Clique
02:53 - Vertex Cover Definition
03:39 - Reducing Independent Set to/from Vertex Cover
04:24 - Reduction Compositions
05:00 - NP-Hard and NP-Complete Definitions
06:02 - Proving additional problems NP-Hard
07:09 - Dominating Set Definition
08:13 - Reducing Vertex Cover to Dominating Set
12:38 - Up Next