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

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



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.2.pdf
  • Filesize: 0.58 MB
  • 13 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.IPEC.2017.2

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].
Keywords
  • parameterized algorithms
  • hypergraph isomorphism
  • mislabeled graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Parameterized complexity of small weight automorphisms. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 7:1-7:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.7.
  2. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897542.
  3. László Babai, D. Yu. Grigoryev, and David M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 310-324. ACM, 1982. URL: http://dx.doi.org/10.1145/800070.802206.
  4. John D. Dixon and Brian Mortimer. Permutation groups. Springer, 1996. URL: http://dx.doi.org/10.1007/978-1-4612-0731-3.
  5. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0515-9.
  6. Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with 0(1) worst case access time. J. ACM, 31(3):538-544, 1984. URL: http://dx.doi.org/10.1145/828.1884.
  7. Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 36-41. IEEE Computer Society, 1980. URL: http://dx.doi.org/10.1109/SFCS.1980.34.
  8. Neil Immerman and Eric Lander. Describing Graphs: A First-Order Approach to Graph Canonization, pages 59-81. Springer, 1990. URL: http://dx.doi.org/10.1007/978-1-4612-4478-3_5.
  9. Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán. Completeness results for graph isomorphism. J. Comput. Syst. Sci., 66(3):549-566, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00042-4.
  10. Pavel Klavík, Dušan Knop, and Peter Zeman. Graph Isomorphism restricted by lists, 2016. URL: https://arxiv.org/abs/1607.03918.
  11. Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM J. Comput., 46(1):161-189, 2017. URL: http://dx.doi.org/10.1137/140999980.
  12. Anna Lubiw. Some np-complete problems similar to graph isomorphism. SIAM J. Comput., 10(1):11-21, 1981. URL: http://dx.doi.org/10.1137/0210002.
  13. Pascal Schweitzer. Isomorphism of (mis)labeled graphs. In Camil Demetrescu and Magnús M. Halldórsson, editors, Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, volume 6942 of Lecture Notes in Computer Science, pages 370-381. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_32.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail