Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree

DOI10.1007/978-3-319-13524-3_12zbMath1341.68058DBLPconf/iwpec/BulianD14arXiv1406.4718OpenAlexW2570782777WikidataQ58215464 ScholiaQ58215464MaRDI QIDQ2946014

Anuj Dawar, Jannis Bulian

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: A commonly studied means of parameterizing graph problems is the deletion distance from triviality (Guo et al. 2004), which counts vertices that need to be deleted from a graph to place it in some class for which efficient algorithms are known. In the context of graph isomorphism, we define triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests. We generalise deletion distance to a measure we call elimination distance to triviality, based on elimination trees or tree-depth decompositions. We establish that graph canonisation, and thus graph isomorphism, is FPT when parameterized by elimination distance to bounded degree, extending results of Bouland et al. (2012).

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)