Parameterized Complexity of Small Weight Automorphisms

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



PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.7.pdf
  • Filesize: 0.54 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. Parameterized Complexity of Small Weight Automorphisms. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.7

Abstract

We show that checking if a given hypergraph has an automorphism that moves exactly k vertices is fixed parameter tractable, using k and additionally either the maximum hyperedge size or the maximum color class size as parameters. In particular, it suffices to use k as parameter if the hyperedge size is at most polylogarithmic in the size of the given hypergraph. As a building block for our algorithms, we generalize Schweitzer's FPT algorithm [ESA 2011] that, given two graphs on the same vertex set and a parameter k, decides whether there is an isomorphism between the two graphs that moves at most k vertices. We extend this result to hypergraphs, using the maximum hyperedge size as a second parameter. Another key component of our algorithm is an orbit-shrinking technique that preserves permutations that move few points and that may be of independent interest. Applying it to a suitable subgroup of the automorphism group allows us to switch from bounded hyperedge size to bounded color classes in the exactly-k case.
Keywords
  • Parameterized algorithms
  • hypergraph isomorphism.

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42:844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
  2. V. Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Solving linear equations parameterized by Hamming weight. Algorithmica, 75(2):322-338, 2016. URL: http://dx.doi.org/10.1007/s00453-015-0098-3.
  3. Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. URL: http://dx.doi.org/10.1007/BF01305232.
  4. Peter J. Cameron and Taoyang Wu. The complexity of the weight problem for permutation and matrix groups. Discrete Mathematics, 310(10):408-416, 2010. URL: http://dx.doi.org/10.1016/j.disc.2009.03.005.
  5. Rod G. Downey and Michael R. Fellows. Parameterized complexity. Springer, New York, 1999. Google Scholar
  6. Rod G. Downey and Michael R. Fellows. Fundamentals of parameterized complexity. Springer, London, 2013. Google Scholar
  7. Rod G. Downey, Michael R. Fellows, Alexander Vardy, and Geoff Whittle. The parametrized complexity of some fundamental problems in coding theory. SIAM Journal on Computing, 29(2):545-570, 1999. URL: http://dx.doi.org/10.1137/S0097539797323571.
  8. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, 2006. Google Scholar
  9. Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with 𝒪(1) worst case access time. J. ACM, 31(3):538-544, 1984. URL: http://dx.doi.org/10.1145/828.1884.
  10. Daniele Micciancio Ilya Dumer and Madhu Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory, 49(1):22-37, 2003. URL: http://dx.doi.org/10.1109/TIT.2002.806118.
  11. Anna Lubiw. Some NP-complete problems similar to Graph Isomorphism. SIAM Journal on Computing, 10(1):11-21, 1981. URL: http://dx.doi.org/10.1137/0210002.
  12. Pascal Schweitzer. Isomorphism of (mis)labeled graphs. In Camil Demetrescu and Magnús M. Halldórsson, editors, Proc. 19th ESA, pages 370-381, Berlin, 2011. Springer. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_32.
  13. Charles C. Sims. Computational methods in the study of permutation groups. In John Leech, editor, Computational problems in abstract algebra, pages 169-183. Pergamon Press, 1970. Google Scholar
  14. Jacobo Torán. On the hardness of graph isomorphism. SIAM Journal on Computing, 33(5):1093-1108, 2004. URL: http://dx.doi.org/10.1137/S009753970241096X.
  15. Alexander Vardy. The intractability of computing the minimum distance of a code. IEEE Transactions on Information Theory, 43(6):1757-1766, 1997. URL: http://dx.doi.org/10.1109/18.641542.
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