License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.2
URN: urn:nbn:de:0030-drops-85690
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8569/
Arvind, Vikraman ;
Köbler, Johannes ;
Kuhnert, Sebastian ;
Torán, Jacobo
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
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\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 Lubiw-style 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 Lubiw-style 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 non-parameterized setting, all these problems are NP-complete. 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 Fixed-Parameter Tractable}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {2:1--2:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8569},
URN = {urn:nbn:de:0030-drops-85690},
doi = {10.4230/LIPIcs.IPEC.2017.2},
annote = {Keywords: parameterized algorithms, hypergraph isomorphism, mislabeled graphs}
}
|
Keywords: |
|
parameterized algorithms, hypergraph isomorphism, mislabeled graphs |
|
Collection: |
|
12th International Symposium on Parameterized and Exact Computation (IPEC 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
02.03.2018 |
