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

@article{Lokshtanov2014FixedParameterTC, title={Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth}, author={Daniel Lokshtanov and Marcin Pilipczuk and Michał Pilipczuk and Saket Saurabh}, journal={2014 IEEE 55th Annual Symposium on Foundations of Computer Science}, year={2014}, pages={186-195} }

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G<sub>1</sub>, G<sub>2</sub>, either concludes that one of these graphs has treewidth at least k, or determines whether G<sub>1</sub> and G<sub>2</sub> are isomorphic. The running time of the algorithm on an n-vertex graph is 2<sup>O(k5 log k)</sup> · n<sup>5</sup>, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general… Expand

#### Figures and Topics from this paper

#### 49 Citations

Canonisation and Definability for Graphs of Bounded Rank Width

- Computer Science, Mathematics
- 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- 2019

It is proved that the combinatorial Weisfeiler-Leman algorithm of dimension $(3k+4)$ is a complete isomorphism test for the class of all graphs of rank width at most k, and that fixed-point logic with counting captures polynomial time on all graph classes of bounded rank width. Expand

Isomorphism Testing Parameterized by Genus and Beyond

- Computer Science, Mathematics
- ESA
- 2021

(t, k)-WL-bounded graphs are introduced which provide a powerful tool to combine group-theoretic techniques with the standard Weisfeiler-Leman algorithm and are of independent interest. Expand

Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs

- Computer Science, Mathematics
- SIAM J. Comput.
- 2015

It is proved that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either “almost embeddable” to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Expand

Canonizing Graphs of Bounded Tree Width in Logspace

- Mathematics, Computer Science
- TOCT
- 2017

It is shown that graphs of bounded tree width can be canonized by logarithmic-space (logspace) algorithms, which implies that the isomorphism problem for graphs of bound treewidth can be decided in logspace. Expand

Graph Isomorphism for Bounded Genus Graphs In Linear Time

- Mathematics, Computer Science
- ArXiv
- 2015

This work improves previously known algorithms whose time complexity is $n^{O(g)}$ and is the first fixed-parameter tractable algorithm for the graph isomorphism problem for bounded genus graphs in terms of the Euler genus. Expand

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

- Mathematics, Computer Science
- STOC '12
- 2012

It is proved that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Expand

An improved isomorphism test for bounded-tree-width graphs

- Mathematics, Computer Science
- ICALP
- 2018

A new fpt algorithm testing isomorphism of n-vertex graphs of tree width in time is given, which avoids the use of Babai's algorithm and has the additional benefit that it can also used as a canonization algorithm. Expand

Graph Isomorphism Restricted by Lists

- Computer Science, Mathematics
- WG
- 2020

It is proved that when GraphIso is GI-complete for a class of graphs, it translates into NP-completeness of ListIso, and that no robust algorithm for cubic graph isomorphism exists, unless P = NP. Expand

Graph isomorphism in quasipolynomial time parameterized by treewidth

- Mathematics, Computer Science
- ICALP
- 2020

A quasipolynomial-time algorithm for the multiple-coset isomorphism problem allows to exploit graph decompositions of the given input graphs within Babai's group-theoretic framework. Expand

Isomorphism Testing for T-graphs in FPT

- Computer Science
- 2021

It is proved that the T -graph isomorphism problem is in FPT when T is the fixed parameter of the problem, and it can equivalently be stated that isomorphicism is inFPT for chordal graphs of (so-called) bounded leafage. Expand

#### References

SHOWING 1-10 OF 51 REFERENCES

Isomorphism testing for graphs of bounded genus

- Mathematics, Computer Science
- STOC '80
- 1980

This result is noteworthy for at least two reasons: first, it extends the polynomial time isomorphism results for the plane [HT 72] and also the projective plane [L 80] to arbitrary surfaces and secondly it gives one of the few known natural decompositions of the isomorphicism problem into an infinite hierarchy of problems. Expand

Minimum bisection is fixed parameter tractable

- Computer Science, Mathematics
- STOC
- 2014

This is the first fixed parameter tractable algorithm for Minimum Bisection with running time O(2O(k3) n3 log3 n) and a new decomposition theorem that states that every graph G can be decomposed by small separators into parts where each part is "highly connected" in the following sense. Expand

Isomorphism for Graphs of Bounded Distance Width

- Mathematics, Computer Science
- Algorithmica
- 1999

It is shown that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(nk+1) time, when they are bounded by a constant k. Expand

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

- Mathematics, Computer Science
- STOC '12
- 2012

It is proved that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Expand

New Lower and Upper Bounds for Graph Treewidth

- Computer Science
- WEA
- 2003

New lower and upper bounds for the treewidth are proposed and tested on the well known DIMACS benchmark for graph coloring, and the heuristic method computes good bounds within a very small computing time. Expand

Linear time algorithm for isomorphism of planar graphs (Preliminary Report)

- Mathematics, Computer Science
- STOC '74
- 1974

The time bound for planar graph isomorphism is improved to O(|V|) time and the algorithm can be easily extended to partition a set of planar graphs into equivalence classes of isomorphic graphs in time linear in the total number of vertices in all graphs in the set. Expand

Graph and map isomorphism and all polyhedral embeddings in linear time

- Mathematics, Computer Science
- STOC
- 2008

A linear time algorithm to test the graph isomorphism of two graphs, one of which admits an embedding of face-width at least 3 into S, improves a previously known algorithm and is the first algorithm for which the degree of polynomial in the time complexity does not depend on g. Expand

Necessary Edges in k-Chordalisations of Graphs

- Mathematics, Computer Science
- J. Comb. Optim.
- 2003

This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G, which is called necessary for treewidth k. Expand

A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus

- Mathematics, Computer Science
- STOC '80
- 1980

The isomorphism problem for graphs has been in recent years the object of a much research and it is not known whether there exists a polynomial-time algorithm for it. Expand

Myhill–Nerode Methods for Hypergraphs

- Mathematics, Computer Science
- Algorithmica
- 2015

An analog of the Myhill–Nerode theorem from formal language theory for hypergraphs is given and a method to derive linear-time algorithms and to obtain indicators for intractability for hyper graph problems parameterized by incidence treewidth is obtained. Expand