我有两个同构图。
给定一个自补图G，是否有任何更快的算法来找到顶点映射 G 及其补码？
我认为应该有更快的方法，因为我们知道这两个图既同构又互补。
编辑 对不起，我应该更清楚: 我已经知道 VF2 算法在最好的情况下具有 O(V^2) 的时间复杂度，在最坏的情况下具有 O(V!·V) 的时间复杂度。这使得计算我正在使用的大型图(1k 个顶点，500k 个边)的映射变得很慢。
我只是想问一下，对于图既是同构又是互补的这种特殊情况，是否存在更快的解决方案。
最佳答案
这是自补图的同构问题。
可以预料 那 同构 问题 会 实际上更容易 解决什么时候 受限制的 自补 图表 或有向图， 因为 他们的 强的 结构的 特性。 它变了 出去， 然而 [科尔本 和 科尔本 1978年， 1979], 那 同构 问题 对于自补图 是多项式 相当于一般 同构 问题； 我们说 这是 同构 完全的 .即使我们只是想知道是否 一张图 或有向图 是自补的，复杂度是一样的。 这 使它不可能 那 那里 会很简单 和 快速测试 用于识别 sc 图； 为了 例子， 比较 彩色的 多项式 图表的 和 那 它的 补体不会告诉我们是否 它是自互补的 (看 1.59). 认出 和同构 自补的 图表 所以 拿 在添加 重要性。 他们 可以 提供 治愈 为了什么 被昵称为 同构 疾病， 和 甚至定居 有名的 (或臭名昭著的) 问题 是否 P 等于 到 NP，我们将 看。
本文第97页: 自补图和概括:综合引用手册。 阿拉斯泰尔·法鲁吉亚 马耳他大学 1999 年 8 月
http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf
关于algorithm - 图与补码之间的映射，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47814111/