Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
Change log
Authors
Bulian, J
Dawar, Anuj https://orcid.org/0000-0003-4014-8248
Abstract
A commonly studied means of parameterizing graph problems is the deletion distance from triviality [11], which counts vertices that need to be deleted from a graph to place it in some class for which e cient algorithms are known. In the context of graph isomorphism, we de ne 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.
Description
Keywords
Graph, Isomorphism, Canonization, Parameterized complexity, Fixed-parameter tractable, Bounded degree, Graph theory, Complexity theory, Tree-depth
Journal Title
Algorithmica
Conference Name
Journal ISSN
0178-4617
1432-0541
1432-0541
Volume Title
Publisher
Springer Science and Business Media LLC
Publisher DOI
Sponsorship
Engineering and Physical Sciences Research Council (EP/H026835/1)
The work was supported in part by EPSRC grant EP/H026835, DAAD grant A/13/05456, and DFG project Logik, Struktur und das Graphenisomorphieproblem.