Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

DOI10.1137/140999980zbMATH Open1358.05284arXiv1404.0818OpenAlexW2593190625MaRDI QIDQ2968151FDOQ2968151

Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Daniel Lokshtanov

Publication date: 10 March 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$, or determines whether $G_1$ and $G_2$ are isomorphic. The running time of the algorithm on an $n$-vertex graph is $2^{O(k^{5}logk)}cdot{n}^5$, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in $2^{O(k^{5}logk)}cdot{n}^5$ time that, for a given graph $G$ on $n$ vertices, either concludes that the treewidth of $G$ is at least $k$, or: * finds in an isomorphic-invariant way a graph $mathfrakc(G)$ that is isomorphic to $G$; * finds an isomorphism-invariant construction term --- an algebraic expression that encodes $G$ together with a tree decomposition of $G$ of width $O(k^4)$. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for $G_1$ and $G_2$ are equal.

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

Recommendations

• An improved isomorphism test for bounded-tree-width graphs
• An improved isomorphism test for bounded-tree-width graphs
• Canonizing graphs of bounded tree width in logspace
• Canonizing Graphs of Bounded Tree Width in Logspace
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
• Publication:4725763
• On tractable parameterizations of graph isomorphism
• Graphs of bounded treewidth can be canonized in AC\(^1\)
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Restricted space algorithms for isomorphism on bounded treewidth graphs

zbMATH Keywords

fixed-parameter tractabilitygraph isomorphismcanonizationbounded treewidth graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Decomposition by clique separators
• A partial k-arboretum of graphs with bounded treewidth
• Graph minors. XIII: The disjoint paths problem
• Parametrized complexity theory.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Treewidth. Computations and approximations
• Optimal decomposition by clique separators
• Title not available (Why is that?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• The isomorphism problem for classes of graphs closed under contraction
• Isomorphism for graphs of bounded distance width
• Isomorphism for graphs of bounded feedback vertex set number
• On Tractable Parameterizations of Graph Isomorphism
• Graph isomorphism is in the low hierarchy
• Graph minors. XVI: Excluding a non-planar graph
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• Title not available (Why is that?)
• Necessary edges in \(k\)-chordalisations of graphs
• An introduction to clique minimal separator decomposition
• Title not available (Why is that?)
• Minimum bisection is fixed parameter tractable
• A V log V algorithm for isomorphism of triconnected planar graphs
• Title not available (Why is that?)
• Canonical representations of partial 2- and 3-trees
• Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
• Myhill-Nerode Methods for Hypergraphs
• Isomorphism for Graphs of Bounded Connected-Path-Distance-Width

Cited In (28)

• Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
• A Faster Isomorphism Test for Graphs of Small Degree
• A \(c^k n\) 5-approximation algorithm for treewidth
• Isomorphism Testing for Graphs Excluding Small Minors
• Mine ’Em All: A Note on Mining All Graphs
• Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
• Graph isomorphism parameterized by elimination distance to bounded degree
• Computing Tree Decompositions
• An improved isomorphism test for bounded-tree-width graphs
• Isomorphism testing for \(T\)-graphs in FPT
• Isomorphism Testing Parameterized by Genus and Beyond
• Title not available (Why is that?)
• Canonisation and Definability for Graphs of Bounded Rank Width
• Graph isomorphism restricted by lists
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• An algorithmic framework for locally constrained homomorphisms
• Isomorphism for graphs of bounded feedback vertex set number
• Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics
• An adaptive prefix-assignment technique for symmetry reduction
• Faster isomorphism for \(p\)-groups of class 2 and exponent \(p\)
• Complexity-separating graph classes for vertex, edge and total colouring
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs
• Canonizing Graphs of Bounded Tree Width in Logspace
• Testing Graph Isomorphism in Parallel by Playing a Game
• Induced minor free graphs: isomorphism and clique-width
• Subexponential Time Algorithms for Finding Small Tree and Path Decompositions

This page was built for publication: Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

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