More Needles in the Hay Might Make it Harder to Find One?

on YouTube ↗24m

" summary

Shows that few solutions can speed some NP-hard cases: directed Hamiltonian cycle maps cycles to parity of xyz vertex partitions and lists y-parts in expected phi^n time then finishes by Gaussian elimination over GF(2) to get a 1.618^n algorithm; combining a randomized edge-sparsification yields n choose k · 1.618^n when there are ≤2^k cycles. For k-coloring of bounded-degree graphs, counting modular in/out subgraphs gives a (d/2+1)^pw time algorithm when k>d/2, bypassing the k^pw SETH barrier.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 1:03Unique solutions cannot help too much
3. 1:40Uniqueness doesn't help at all for Satisfiability
4. 2:12Two candidates where uniqueness might help
5. 2:40Arithmetical algorithms
6. 3:18Directed hamiltonian cycle
7. 3:32Example with 2 hamiltonian cycles
8. 3:47Count vertex partitions
9. 6:06All partitions IV
10. 6:34Example with 1 Hamiltonian cycle
11. 9:42Case in point
12. 12:00A uniquely 3-colorable graph
13. 13:06The connection
14. 14:02An orientation with modular degree constraints
15. 14:22Even subgraphs
16. 16:18A non-3-colorable graph
17. 16:45Even and odd subgraphs
18. 17:18k-coloring and path decomposition
19. 18:39k-coloring path decomposition hardness
20. 19:19Bounded degree
21. 19:54Counting subgraphs and path decomposition