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

DOI10.1137/140999980MaRDI QIDQ2968151zbMATH OpenOpenAlexFDO

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

Publication date 10 March 2017

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

Full work available at URL https://arxiv.org/abs/1404.0818, http://wrap.warwick.ac.uk/66066/1/WRAP_1371795-cs-270115-tw-iso.pdf

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)

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.

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)
• scientific article; zbMATH DE number 3999309
• 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

Cites work

• scientific article; zbMATH DE number 5485559 (Why is no real title available?)
• scientific article; zbMATH DE number 3679848 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 1982177 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A V log V algorithm for isomorphism of triconnected planar graphs
• A partial k-arboretum of graphs with bounded treewidth
• An introduction to clique minimal separator decomposition
• Canonical representations of partial 2- and 3-trees
• Decomposition by clique separators
• Fundamentals of parameterized complexity
• Graph isomorphism is in the low hierarchy
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XVI: Excluding a non-planar graph
• Graph structure and monadic second-order logic. A language-theoretic approach
• Isomorphism for graphs of bounded connected-path-distance-width
• Isomorphism for graphs of bounded distance width
• Isomorphism for graphs of bounded feedback vertex set number
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Minimum bisection is fixed parameter tractable
• Necessary edges in k-chordalisations of graphs
• On tractable parameterizations of graph isomorphism
• Optimal decomposition by clique separators
• Parametrized complexity theory.
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The isomorphism problem for classes of graphs closed under contraction
• Treewidth. Computations and approximations

Cited in

(29)

• 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
• Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
• Graph isomorphism parameterized by elimination distance to bounded degree
• Mine 'em all: a note on mining all graphs
• Computing Tree Decompositions
• Graphs of bounded treewidth can be canonized in AC\(^1\)
• Isomorphism testing for \(T\)-graphs in FPT
• An improved isomorphism test for bounded-tree-width graphs
• An improved isomorphism test for bounded-tree-width graphs
• Isomorphism Testing Parameterized by Genus and Beyond
• Subexponential time algorithms for finding small tree and path decompositions
• scientific article; zbMATH DE number 7559112 (Why is no real title available?)
• 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
• On tractable parameterizations of graph isomorphism
• Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics
• An adaptive prefix-assignment technique for symmetry reduction
• Complexity-separating graph classes for vertex, edge and total colouring
• Faster isomorphism for \(p\)-groups of class 2 and exponent \(p\)
• 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

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)