TY - GEN
T1 - Killing a vortex
AU - Thilikos, Dimitrios M.
AU - Wiederrecht, Sebastian
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - We provide a 'vortex-free' refinement of the seminal structure theorem for Kt-minor free graphs by Robertson and Seymour as follows: we identify a (parameterized) graph Ht and we prove that if we replace Kt by Ht, then the resulting decomposition becomes 'vortex-free'. Up to now, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the single-crossing minor-free graphs. This result is tight in the sense that, whenever we minor-exclude a graph that is not a minor of some Ht, the appearance of vortices is unavoidable. Using the above decomposition theorem, we design an algorithm that, given an Ht-minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. This algorithm yields, on Ht-minor-free graphs, polynomial algorithms for computational problems such as the dimer problem, the exact matching problem, and the computation of the permanent. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are precisely those graph classes that do not contain every Ht as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.
AB - We provide a 'vortex-free' refinement of the seminal structure theorem for Kt-minor free graphs by Robertson and Seymour as follows: we identify a (parameterized) graph Ht and we prove that if we replace Kt by Ht, then the resulting decomposition becomes 'vortex-free'. Up to now, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the single-crossing minor-free graphs. This result is tight in the sense that, whenever we minor-exclude a graph that is not a minor of some Ht, the appearance of vortices is unavoidable. Using the above decomposition theorem, we design an algorithm that, given an Ht-minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. This algorithm yields, on Ht-minor-free graphs, polynomial algorithms for computational problems such as the dimer problem, the exact matching problem, and the computation of the permanent. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are precisely those graph classes that do not contain every Ht as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.
KW - Counting Algorithms
KW - Graph Minors
KW - Graph Parameters
KW - Perfect Matchings
KW - Permanent
KW - Pfaffian Orientations
UR - http://www.scopus.com/inward/record.url?scp=85146312137&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85146312137&partnerID=8YFLogxK
U2 - 10.1109/FOCS54457.2022.00104
DO - 10.1109/FOCS54457.2022.00104
M3 - Conference contribution
AN - SCOPUS:85146312137
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1069
EP - 1080
BT - Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PB - IEEE Computer Society
T2 - 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Y2 - 31 October 2022 through 3 November 2022
ER -