Fine-Grained Complexity of Exact Algorithms
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06
summary
Shows an ETH-based lower bound: G→H cannot be solved in |H|^{o(|G|)} time (unless ETH fails) via a reduction from 3‑coloring that groups R original vertices into one, making H′ of size about d^R to force local colorings. Gives a second reduction turning homomorphism into subgraph isomorphism by guessing how many G‑vertices map to each H‑vertex and replacing each H‑vertex by an independent set, implying subgraph isomorphism requires 2^{o(n log n)} time (ETH). Notes single‑exponential algorithms when H has bounded treewidth/clique‑width and many open cases (embeddings, bandwidth, branchwidth, book thickness).
AI-written summary · about
chapters (26)
- 0:00Intro
- 1:42Outline
- 2:18Motivation
- 4:30Brute Force
- 6:07Graph Coloring
- 9:15Exact Algorithms
- 10:39What makes algorithms cool
- 14:33Graph Homomorphism
- 28:54Normal Homomorphism
- 29:21Subgraph Isomorphism
- 30:15Brute Force Isomorphism
- 30:34Proof
- 32:57Problems
- 41:59Metric Embedding
- 43:02Trig Embedding
- 44:20Graph Embedding
- 45:36Bandwidth
- 46:43Graph Meets
- 47:20Graph Decompositions
- 47:43Branch Decomposition
- 48:41Clickers
- 49:19Minimum Genus
- 50:46Book Thickness
- 52:15HColoring
- 53:44Conclusion
- 54:27Questions