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

DOI10.4230/LIPICS.IPEC.2017.2zbMATH Open1443.68118arXiv1709.10063OpenAlexW2964045964MaRDI QIDQ5111861FDOQ5111861

Sebastian Kuhnert, Vikraman Arvind, Johannes Köbler, Jacobo Torán

Publication date: 27 May 2020

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 $RsubseteqVimesV$ of forbidden pairs whether there is an isomorphism $pi$ from $X_1$ to $X_2$ such that $pi(i)eqj$ for all $(i,j)inR$. 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 $pi$ 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.

Full work available at URL: https://arxiv.org/abs/1709.10063

Recommendations

• Parameterized complexity of small weight automorphisms and isomorphisms
• Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor
• On tractable parameterizations of graph isomorphism
• Parameterized complexity of small weight automorphisms
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Parameterized complexity of finding small degree-constrained subgraphs
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• A convex relaxation bound for subgraph isomorphism

zbMATH Keywords

parameterized algorithmshypergraph isomorphismmislabeled graphs

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Title not available (Why is that?)
• Some NP-Complete Problems Similar to Graph Isomorphism
• Title not available (Why is that?)
• Completeness results for graph isomorphism.
• Graph isomorphism in quasipolynomial time [extended abstract]
• Isomorphism of (mis)Labeled Graphs
• Parameterized Complexity of Small Weight Automorphisms.
• Graph isomorphism restricted by lists

Cited In (1)

• Parameterized complexity of small weight automorphisms and isomorphisms

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)