论文标题
图形中图同构的固定参数的障碍性在图形中具有排除在外的次要
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
论文作者
论文摘要
我们证明，图形同构和构成图中的图形不包括固定图$ h $作为未成年人，可以通过在时间$ f（h）\ cdot n^{o（1）} $上工作的算法来解决，其中$ f $是某种函数。换句话说，我们表明，当通过被排除的小调的大小进行参数化时，这些问题是固定参数可处理的，并且在运行时间上绑定的警告不一定是可计算的。基本方法是基于以规范的方式分解图形为牢不可破的（直觉，连接良好的）部分，这实质上可以减少给定的$ H $ -Minor-minor-minor-minor图形本身是牢不可讲的。这是对在第二个下属手稿中执行的无可破解$ h $ minor图表的分析来补充的，该图揭示了可以将每个这样的图形分解为几乎没有自动形态的部分，并且可以将其限制为treewidth。
We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph $H$ as a minor can be solved by an algorithm working in time $f(H)\cdot n^{O(1)}$, where $f$ is some function. In other words, we show that these problems are fixed-parameter tractable when parameterized by the size of the excluded minor, with the caveat that the bound on the running time is not necessarily computable. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given $H$-minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable $H$-minor-free graphs, performed in a second subordinate manuscript, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth.
