Arvind, Vikraman ;
Köbler, Johannes ;
Kuhnert, Sebastian ;
Torán, Jacobo
Finding Small Weight Isomorphisms with Additional Constraints is FixedParameter Tractable
Abstract
Lubiw showed that several variants of Graph Isomorphism are NPcomplete, 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 i^\pi\ne 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 Lubiwstyle constraints is in FPT, with k and the size of R as parameters. The problem remains in FPT even if a conjunction of disjunctions of such constraints is allowed. As a consequence of the main result 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 number of moved vertices is unrestricted, finding isomorphisms that satisfy a CNF of Lubiwstyle constraints can be solved in FPT with access to a GI oracle.
 Checking if there is an isomorphism π 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 \pi 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.
In the nonparameterized setting, all these problems are NPcomplete. Also, they all generalize in several ways the problem to decide whether there is an isomorphism between two graphs that moves at most k vertices, shown to be in FPT by Schweitzer [ESA 2011].
BibTeX  Entry
@InProceedings{arvind_et_al:LIPIcs:2018:8569,
author = {Vikraman Arvind and Johannes K{\"o}bler and Sebastian Kuhnert and Jacobo Tor{\'a}n},
title = {{Finding Small Weight Isomorphisms with Additional Constraints is FixedParameter Tractable}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {2:12:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8569},
URN = {urn:nbn:de:0030drops85690},
doi = {10.4230/LIPIcs.IPEC.2017.2},
annote = {Keywords: parameterized algorithms, hypergraph isomorphism, mislabeled graphs}
}
02.03.2018
Keywords: 

parameterized algorithms, hypergraph isomorphism, mislabeled graphs 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

02.03.2018 