Counting Matrix Partitions of Graphs

on YouTube ↗45m

" summary

Proves a precise dichotomy: for any fixed symmetric 0/1/ matrix M, counting list M‑partitions is either polynomial‑time computable or #P‑complete, decided by the presence of a d rectangularizing sequence. Key tools are a faithful CSP reduction for purifying list families and a purification algorithm* that splits an instance into polynomially many purifying list‑instances λ1…λT. If no d‑sequence exists the algorithm runs in polynomial time via CSP techniques; if one exists the problem is #P‑complete. Ambiguity remains for some listless/asymmetric extensions.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 1:51Graph homomorphisms
3. 3:42Complexity of counting homomorphisms
4. 6:13Homomorphisms as CSPs
5. 7:23Matrix partitions
6. 10:24Examples
7. 13:56An encoding as a CSP
8. 17:06#CSP dichotomy
9. 22:37Complexity of list M-partitions
10. 24:51Parameterization
11. 26:51Purity
12. 29:01Derectangularizing sequences
13. 31:59Dichotomy for purifying lists (1)
14. 37:25Dichotomy for purifying lists (III)
15. 39:07Purification