Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor

DOI10.1145/3519935.3520076arXiv2210.14638OpenAlexW4281745429MaRDI QIDQ6083544

Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Daniel Lokshtanov

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph $H$ as a minor can be solved by an algorithm working in time $f(H)cdot{n}^{O(1)}$, where $f$ is some function. In other words, we show that these problems are fixed-parameter tractable when parameterized by the size of the excluded minor, with the caveat that the bound on the running time is not necessarily computable. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given $H$-minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable $H$-minor-free graphs, performed in a second subordinate manuscript, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth.

Full work available at URL: https://arxiv.org/abs/2210.14638

zbMATH Keywords

fixed-parameter tractabilitygraph isomorphismexcluded minor

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable

This page was built for publication: Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor