Repository logo
 

Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree


Change log

Authors

Bulian, J 

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

Volume Title

Publisher

Springer Science and Business Media LLC
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.