Name
Abstract | ||
|---|---|---|
We give a new FPT algorithm testing isomorphism of n-vertex graphs of tree-width k in time 2kpolylog(k)n3, improving the FPT algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2O(k5 log k)n5. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree-width k. Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai’s algorithm as a black box in one place.
We also give a second algorithm that, at the price of a slightly worse running time 2O(k2 log k)n3, avoids the use of Babai’s algorithm and, more importantly, has the additional benefit that it can also be used as a canonization algorithm.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3382082 | ACM Transactions on Algorithms |
Keywords | DocType | Volume |
Graph isomorphism,decompositions,graph canonization,tree-width | Journal | 16 |
Issue | ISSN | Citations |
3 | 1549-6325 | 0 |
PageRank | References | Authors |
0.34 | 17 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Grohe | 1 | 2280 | 127.40 |
| Daniel Neuen | 2 | 9 | 5.03 |
| Pascal Schweitzer | 3 | 214 | 16.94 |
| Daniel Wiebking | 4 | 0 | 2.03 |