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 -