Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable

Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: 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 s u b s e t e q V i m e s V

of forbidden pairs whether there is an isomorphism

p i

from

X_{1}

to

X_{2}

such that

p i (i) e q j

for all

(i, j) i n 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 weight and complexity are unrestricted, finding isomorphisms that satisfy a CNF of Lubiw-style constraints can be solved in FPT with access to a GI oracle. - Checking if there is an isomorphism

p i

between two graphs with complexity t is also in FPT with t as parameter, where the complexity of a permutation is the Cayley measure defined as the minimum number t such that

p i

can be expressed as a product of t transpositions. - We consider a more general problem in which the vertex set of a graph X is partitioned into Red and Blue, and we are interested in an automorphism that stabilizes Red and Blue and moves exactly k vertices in Blue, where k is the parameter. This problem was introduced by [Downey and Fellows 1999], and we showed [STACS 2017] that it is W[1]-hard even with color classes of size 4 inside Red. Now, for color classes of size at most 3 inside Red, we show the problem is in FPT.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111861)