Skip to main content
Springer Nature Link
Log in

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism, denoted CHI, which has running time (2b N)O(1), where the parameter b is the maximum size of the color classes of the given hypergraphs and N is the input size. We also describe an fpt algorithm for a parameterized coset intersection problem that is used as a subroutine in our algorithm for CHI.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Arvind, V., Das, B., Köbler, J., Toda, S.: Colored hypergraph isomorphism is fixed parameter tractable. In: Proceedings of the 30th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Leibniz International Proceedings in Informatics, vol. 8, pp. 327–337. Leibniz-Zentrum für Informatik, Dagstuhl (2010)

    Google Scholar 

  2. Arvind, V., Köbler, J.: On hypergraph and graph isomorphism with bounded color classes. In: Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 3884, pp. 384–395. Springer, Berlin (2006)

    Google Scholar 

  3. Arvind, V., Köbler, J.: Canonizing hypergraphs under Abelian group action. In: Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 6842, pp. 444–455. Springer, Berlin (2011)

    Google Scholar 

  4. Babai, L.: Monte-carlo algorithms in graph isomorphism testing. Technical report 79-10, Université de Montréal (1979)

  5. Babai, L.: Moderately exponential bounds for graph isomorphism. In: Proceedings of the 3rd International Symposium Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science, vol. 117, pp. 34–50. Springer, Berlin (1981)

    Chapter  Google Scholar 

  6. Babai, L., Codenotti, P.: Isomorhism of hypergraphs of low rank in moderately exponential time. In: Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 667–676 (2008)

    Google Scholar 

  7. Babai, L., Kantor, W.M., Luks, E.M.: Computational complexity and the classification of finite simple groups. In: Proceedings of the 24th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 162–171 (1983)

    Google Scholar 

  8. Babai, L., Luks, E.M.: Canonical labeling of graphs. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), pp. 171–183 (1983)

    Google Scholar 

  9. Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algor. 11(4), 631–643 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  10. Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput. 24(4), 873–921 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  11. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)

    Book  Google Scholar 

  12. Evdokimov, S., Ponomarenko, I.: Isomorphism of colored graphs with slowly increasing multiplicity of Jordan blocks. Combinatorica 19(3), 321–333 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  13. Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)

    Google Scholar 

  14. Furst, M., Hopcroft, J.E., Luks, E.M.: Polynomial-time algorithms for permutation groups. Technical report, Cornell University (1980)

  15. Isaacs, I.M.: Finite Group Theory. American Mathematical Society, Philadelphia (2008)

    MATH  Google Scholar 

  16. Jenner, B., Köbler, J., McKenzie, P., Torán, J.: Completeness results for graph isomorphism. J. Comput. Syst. Sci. 66(3), 549–566 (2003)

    Article  MATH  Google Scholar 

  17. Kratsch, S., Schweitzer, P.: Isomorphism for graphs of bounded feedback vertex set number. In: Kaplan, H. (ed.) Proceedings of the 12th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 6139, pp. 81–92. Springer, Berlin (2010)

    Google Scholar 

  18. Köbler, J., Schöning, U., Torán, J.: The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science. Birkhäuser, Boston (1993)

    Book  MATH  Google Scholar 

  19. Köbler, J.: On graph isomorphism for restricted graph classes. In: Logical Approaches to Computational Barriers. Lecture Notes in Computer Science, vol. 3988, pp. 241–256. Springer, Berlin (2006)

    Chapter  Google Scholar 

  20. Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42–65 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  21. Luks, E.M.: Permutation groups and polynomial-time computation. In: Finkelstein, L., Kantor, W.M. (eds.) Groups and Computation. Discrete Mathematics and Theoretical Computer Science, vol. 11, pp. 139–175. American Mathematical Society, Philadelphia (1993)

    Google Scholar 

  22. Luks, E.M.: Hypergraph isomorphism and structural equivalence of boolean functions. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 652–658 (1999)

    Google Scholar 

  23. Miller, G.L.: Isomorphism testing for graphs of bounded genus. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 225–235 (1980)

    Google Scholar 

  24. Miller, G.L.: Isomorphism of k-contractible graphs. Inf. Con. 56(1–2), 1–20 (1983)

    Article  MATH  Google Scholar 

  25. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)

    Book  MATH  Google Scholar 

  26. Seress, Á.: Permutation Group Algorithms. Cambridge University Press, Cambridge (2003)

    Book  MATH  Google Scholar 

  27. Sims, C.C.: Computational methods in the study of permutation groups. In: Leech, J. (ed.) Computational Problems in Abstract Algebra, pp. 169–183. Pergamon, Elmsford (1970)

    Chapter  Google Scholar 

  28. Sims, C.C.: Some group theoretic algorithms. In: Dold, A., Eckmann, B. (eds.) Topics in Algebra. Lecture Notes in Mathematics, vol. 697, pp. 108–124. Springer, Berlin (1978)

    Chapter  Google Scholar 

  29. Toda, S.: Computing automorphism groups of chordal graphs whose simplicial components are of small size. IEICE Trans. Inform. Syst. 89-D(8), 2388–2401 (2006)

    Article  Google Scholar 

  30. Yamazaki, K., Bodlaender, H.L., de Fluiter, B., Thilikos, D.M.: Isomorphism for graphs of bounded distance width. Algorithmica 24(2), 105–127 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  31. Zemlyachenko, V.N., Kornienko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta 118, 83–158 (1982)

    MATH  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank the referees for their helpful comments and suggestions.

Author information

Authors and Affiliations

  1. The Institute of Mathematical Sciences, Chennai, 600 113, India

    V. Arvind

  2. Indian Institute of Technology Gandhinagar, Ahmedabad, 382 424, India

    Bireswar Das

  3. Institut für Informatik, Humboldt Universität zu Berlin, Berlin, Germany

    Johannes Köbler

  4. Nihon University, Tokyo, Japan

    Seinosuke Toda

Authors
  1. V. Arvind
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bireswar Das
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Johannes Köbler
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Seinosuke Toda
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Johannes Köbler.

Additional information

Supported by the Research Group Linkage Programme of the Alexander von Humboldt Foundation. A preliminary version of this paper appeared in the Proceedings of the 30th Conference on Foundations of Software Technology and Theoretical Computer Science, 2010 [1].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Arvind, V., Das, B., Köbler, J. et al. Colored Hypergraph Isomorphism is Fixed Parameter Tractable. Algorithmica 71, 120–138 (2015). https://doi.org/10.1007/s00453-013-9787-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-013-9787-y

Keywords

Search

Navigation