Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree

DOI10.1007/978-3-319-13524-3_12MaRDI QIDQ2946014zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jannis Bulian, Anuj Dawar

Publication date 15 September 2015

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

Full work available at URL https://arxiv.org/abs/1406.4718, https://www.repository.cam.ac.uk/handle/1810/249190

Mathematics Subject Classification ID

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

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).

Recommendations

• Graph isomorphism parameterized by elimination distance to bounded degree
• Isomorphism for graphs of bounded distance width
• Elimination Distance to Bounded Degree on Planar Graphs
• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• Isomorphism for graphs of bounded connected-path-distance-width
• Edge-distance between isomorphism classes of graphs
• On distances between isomorphism classes of graphs
• On tractable parameterizations of graph isomorphism
• Approximate graph isomorphism
• On isomorphism between distance-regular graphs

Cited in

(5)

• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• Fixed-parameter tractable distances to sparse graph classes
• Graph isomorphism parameterized by elimination distance to bounded degree
• On tractable parameterizations of graph isomorphism
• On the parallel parameterized complexity of the graph isomorphism problem

This page was built for publication: Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946014)