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

DOI10.1137/140999980zbMath1358.05284arXiv1404.0818OpenAlexW2593190625MaRDI QIDQ2968151

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

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

zbMATH Keywords

fixed-parameter tractabilitybounded treewidth graphsgraph isomorphismcanonization

Mathematics Subject Classification ID

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

Related Items

Isomorphism Testing for Graphs Excluding Small Minors ⋮ Computing Tree Decompositions ⋮ Subexponential Time Algorithms for Finding Small Tree and Path Decompositions ⋮ Graph isomorphism parameterized by elimination distance to bounded degree ⋮ Isomorphism testing for \(T\)-graphs in FPT ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ An improved isomorphism test for bounded-tree-width graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract) ⋮ Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs ⋮ A Faster Isomorphism Test for Graphs of Small Degree ⋮ Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics ⋮ Isomorphism Testing Parameterized by Genus and Beyond ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable ⋮ Unnamed Item ⋮ An adaptive prefix-assignment technique for symmetry reduction ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Graph isomorphism restricted by lists ⋮ Mine ’Em All: A Note on Mining All Graphs ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ Canonisation and Definability for Graphs of Bounded Rank Width

Cites Work

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