Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree

DOI10.1007/978-3-319-13524-3_12zbMATH Open1341.68058DBLPconf/iwpec/BulianD14arXiv1406.4718OpenAlexW2570782777WikidataQ58215464 ScholiaQ58215464MaRDI QIDQ2946014FDOQ2946014

Authors: Jannis Bulian, Anuj Dawar 

Publication date: 15 September 2015

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

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

Full work available at URL: https://arxiv.org/abs/1406.4718

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

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)

Cited In (2)

• Fixed-parameter tractable distances to sparse graph classes
• On tractable parameterizations of graph isomorphism

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)