Killing a vortex

Dimitrios M. Thilikos, Sebastian Wiederrecht

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PublisherIEEE Computer Society
Number of pages12
ISBN (Electronic)9781665455190
StatePublished - 2022
Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
Duration: Oct 31 2022Nov 3 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428


Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Country/TerritoryUnited States


  • Counting Algorithms
  • Graph Minors
  • Graph Parameters
  • Perfect Matchings
  • Permanent
  • Pfaffian Orientations

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Killing a vortex'. Together they form a unique fingerprint.

Cite this