solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看1137次
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. (arXiv:1709.10063v1 [cs.CC])
来源于:arXiv
Lubiw showed that several variants of Graph Isomorphism are NP-complete,
where the solutions are required to satisfy certain additional constraints
[SICOMP 10, 1981]. One of these, called Isomorphism With Restrictions, is to
decide for two given graphs $X_1=(V,E_1)$ and $X_2=(V,E_2)$ and a subset
$R\subseteq V\times V$ of forbidden pairs whether there is an isomorphism $\pi$
from $X_1$ to $X_2$ such that $\pi(i)\neq j$ for all $(i,j)\in R$. We prove
that this problem and several of its generalizations are in fact in FPT:
- The problem of deciding whether there is an isomorphism between two graphs
that moves k vertices and satisfies Lubiw-style constraints is in FPT, with k
and the size of $R$ as parameters. The problem remains in FPT if a CNF of such
constraints is allowed. It follows that the problem to decide whether there is
an isomorphism that moves exactly k vertices is in FPT. This solves a question
left open in our article on exact weight automorphisms [STACS 2017].
- When the w 查看全文>>