Other problems solvable with this technique

  • k-colorability was only one example; the same inclusion–exclusion machinery handles, e.g. 41:00, 41:47:
    • minimum Steiner tree
    • finding all k-colorable induced subgraphs
  • Recommended survey: Husfeldt, "An invitation to algorithmic uses of inclusion–exclusion", ICALP 2011, also on arXiv; further references are inside it 41:47, 42:08.

Decision → construction: actually finding a k-coloring

  • Natural objection: the formula only tells you a coloring exists, not what it is 43:58, 44:20.
  • It can be found in roughly the same running time via a reduction in Björklund–Husfeldt (FOCS '06) 44:20.
  • The reduction is a black box, only a couple of paragraphs long, and not algorithm-specific: if you can compute a graph's chromatic number in 2^n time, you can find a k-coloring in roughly the same time 45:07, 45:25.
  • Skipped in class for time; the paper is on arXiv 45:07.

Loose ends left as exercises

  • Only the zeta transform side of Yates's algorithm was shown; computing the Möbius inversion uses an almost identical dynamic program, left as an exercise (possibly to be added to the notes) 47:21, 47:45.

Transition to the final topic

  • The remaining class and a half covers sketching and streaming 45:49, 47:45.
  • Deliberately kept short: Harvard runs a whole course on it — Algorithms for Big Data, offered next fall — so the lecturer avoids duplicating that material 48:26.
  • Next lecture will connect a streaming algorithm to something already seen in the course, and use it to speed that earlier result up 48:51.