Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
MetadataShow full item record
Bulian, J., & Dawar, A. (2015). Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree. Algorithmica https://doi.org/10.1007/s00453-015-0045-3
A commonly studied means of parameterizing graph problems is the deletion distance from triviality , 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.
The work was supported in part by EPSRC grant EP/H026835, DAAD grant A/13/05456, and DFG project Logik, Struktur und das Graphenisomorphieproblem.
External DOI: https://doi.org/10.1007/s00453-015-0045-3
This record's URL: https://www.repository.cam.ac.uk/handle/1810/249190
Creative Commons Attribution 4.0
Licence URL: http://creativecommons.org/licenses/by/4.0/