An Improved Isomorphism Test for Bounded-tree-width Graphs
An Improved Isomorphism Test for Bounded-tree-width Graphs
复制标题
有界树宽度图的改进同构测试
DOI：
10.1145/3382082
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
D. Wiebking
中科院分区：
文献类型：
--
作者：
M. Grohe;D. Neuen;P. Schweitzer;D. Wiebking
我们给出了一个新的FPT算法，测试树宽度为time 2kpolylog（k）n3的n-顶点图的同构，改进了Lokshtanov，Pilipczuk，Pilipczuk和Saurabh（FOCS 2014）的FPT算法，该算法在时间上运行2 O（k5 log k）n5。基于Lokshtanov等人提出的同构不变图分解技术的改进版本，证明了树宽图的自同构群的结构的限制。然后，我们的算法大量使用了Luks（JCSS 1982）在有界度图的同构测试中引入的群论技术，以及巴拜（STOC 2016）在他的准多项式同构测试中引入的群论技术。事实上，我们甚至把巴拜的算法当作一个黑箱来使用，我们还给出了第二个算法，它以稍差的运行时间2 O（k2 log k）n3为代价，避免了使用巴拜的算法，更重要的是，它还有一个额外的好处，那就是它也可以用作经典化算法。
We give a new FPT algorithm testing isomorphism ofn-vertex graphs of tree-widthkin time2kpolylog(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-widthk. 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.
登录
查看更多内容
k-可收缩图的同构测试和规范形式（有界价和有界属的推广）
DOI：
10.1007/3-540-12689-9_114
发表时间：
1983
期刊：
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
G. Miller
通讯作者：
G. Miller
DOI：
10.1007/bf01098279
发表时间：
1991
期刊：
Journal of Soviet Mathematics
影响因子：
--
作者：
I. Ponomarenko
通讯作者：
I. Ponomarenko
由树宽参数化的拟多项式时间内的图同构
DOI：
--
发表时间：
2019
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Daniel Wiebking
通讯作者：
Daniel Wiebking
图的 k 弦化中的必要边
影响因子：
1
作者：
H. Bodlaender
通讯作者：
H. Bodlaender
单位平方图的图同构
DOI：
10.4230/lipics.esa.2016.70
发表时间：
2016
期刊：
ArXiv
影响因子：
--
作者：
Daniel Neuen
通讯作者：
Daniel Neuen