2014/06/18 by Jannis Bulian, Bulian, Jannis, Anuj Dawar +1 · 3 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1406.4718
openalex publication_date 2014/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A commonly studied means of parameterizing graph problems is the deletion\ndistance from triviality (Guo et al. 2004), which counts vertices that need to\nbe deleted from a graph to place it in some class for which efficient\nalgorithms are known. In the context of graph isomorphism, we define triviality\nto mean a graph with maximum degree bounded by a constant, as such graph\nclasses admit polynomial-time isomorphism tests. We generalise deletion\ndistance to a measure we call elimination distance to triviality, based on\nelimination trees or tree-depth decompositions. We establish that graph\ncanonisation, and thus graph isomorphism, is FPT when parameterized by\nelimination distance to bounded degree, extending results of Bouland et al.\n(2012).\n