Document Open Access Logo

Towards an Isomorphism Dichotomy for Hereditary Graph Classes

Author Pascal Schweitzer

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.689.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Pascal Schweitzer

Cite AsGet BibTex

Pascal Schweitzer. Towards an Isomorphism Dichotomy for Hereditary Graph Classes. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 689-702, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.STACS.2015.689

Abstract

In this paper we resolve the complexity of the isomorphism problem on all but finitely many of the graph classes characterized by two forbidden induced subgraphs. To this end we develop new techniques applicable for the structural and algorithmic analysis of graphs. First, we develop a methodology to show isomorphism completeness of the isomorphism problem on graph classes by providing a general framework unifying various reduction techniques. Second, we generalize the concept of the modular decomposition to colored graphs, allowing for non-standard decompositions. We show that, given a suitable decomposition functor, the graph isomorphism problem reduces to checking isomorphism of colored prime graphs. Third, we extend the techniques of bounded color valence and hypergraph isomorphism on hypergraphs of bounded color class size as follows. We say a colored graph has generalized color valence at most k if, after removing all vertices in color classes of size at most k, for each color class C every vertex has at most k neighbors in C or at most k non-neighbors in C. We show that isomorphism of graphs of bounded generalized color valence can be solved in polynomial time.
Keywords
  • graph isomorphism
  • modular decomposition
  • bounded color valence
  • reductions
  • forbidden induced subgraphs

Metrics

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

References

  1. Vikraman Arvind, Bireswar Das, Johannes Köbler, and Seinosuke Toda. Colored hypergraph isomorphism is fixed parameter tractable. In FSTTCS, pages 327-337, 2010. Google Scholar
  2. László Babai. Moderately exponential bound for graph isomorphism. In FCT, pages 34-50, 1981. Google Scholar
  3. László Babai. Handbook of Combinatorics (vol. 2), chapter Automorphism groups, isomorphism, reconstruction, pages 1447-1540. MIT Press, 1995. Google Scholar
  4. László Babai and Eugene M. Luks. Canonical labeling of graphs. In STOC, pages 171-183, 1983. Google Scholar
  5. Kellogg S. Booth and C. J. Colbourn. Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-04, Comp. Sci. Dep., Univ. Waterloo, 1979. Google Scholar
  6. Andreas Brandstädt and Dieter Kratsch. On the structure of (P_5, gem)-free graphs. Discrete Applied Mathematics, 145(2):155-166, 2005. Google Scholar
  7. Andrew Curtis, Min Lin, Ross McConnell, Yahav Nussbaum, Francisco Soulignac, Jeremy Spinrad, and Jayme Szwarcfiter. Isomorphism of graph classes related to the circular-ones property. Discrete Mathematics and Theoretical Computer Science, 15(1):157-182, 2013. Google Scholar
  8. Konrad Dabrowski and Daniël Paulusma. Clique-width of graph classes defined by two forbidden induced subgraphs. CoRR, abs/1405.7092, 2014. Google Scholar
  9. Konrad K. Dabrowski, Petr A. Golovach, and Daniel Paulusma. Colouring of graphs with ramsey-type forbidden subgraphs. Theoretical Computer Science, 522(0):34-43, 2014. Google Scholar
  10. Frank Fuhlbrück. Fixed-parameter tractability of the graph isomorphism and canonization problems. Diploma thesis, Humboldt-Universität zu Berlin, 2013. Google Scholar
  11. Mark K. Goldberg. A nonfactorial algorithm for testing isomorphism of two graphs. Discrete Applied Mathematics, 6(3):229-236, 1983. Google Scholar
  12. Petr A. Golovach and Daniël Paulusma. List coloring in the absence of two subgraphs. Discrete Applied Mathematics, 166:123-130, 2014. Google Scholar
  13. Martin Grohe and Dániel Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In STOC, pages 173-192, 2012. Google Scholar
  14. Yuri Gurevich. From invariants to canonization. Bulletin of the EATCS, 63, 1997. Google Scholar
  15. Yuri Gurevich. From invariants to canonization. In Current Trends in Theoretical Computer Science, pages 327-331. World Scientific, 2001. Google Scholar
  16. Michel Habib and Christophe Paul. A survey of the algorithmic aspects of modular decomposition. Computer Science Review, 4(1):41-59, 2010. Google Scholar
  17. Tommi A. Junttila and Petteri Kaski. Conflict propagation and component recursion for canonical labeling. In TAPAS, pages 151-162, 2011. Google Scholar
  18. Johannes Köbler, Uwe Schöning, and Jacobo Torán. The graph isomorphism problem: its structural complexity. Birkhäuser Verlag, Basel, Switzerland, 1993. Google Scholar
  19. Johannes Köbler and Oleg Verbitsky. From invariants to canonization in parallel. In CSR, pages 216-227, 2008. Google Scholar
  20. Daniel Král, Jan Kratochvíl, Zsolt Tuza, and Gerhard J. Woeginger. Complexity of coloring graphs without forbidden induced subgraphs. In WG, pages 254-262, 2001. Google Scholar
  21. Stefan Kratsch and Pascal Schweitzer. Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. In WG, pages 34-45, 2012. Google Scholar
  22. Stefan Kratsch and Pascal Schweitzer. Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. CoRR, abs/1208.0142, 2012. Google Scholar
  23. Vadim V. Lozin. A decidability result for the dominating set problem. Theoretical Computer Science, 411(44-46):4023-4027, 2010. Google Scholar
  24. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42-65, 1982. Google Scholar
  25. Gary L. Miller. Isomorphism testing and canonical forms for k-contractable graphs (a generalization of bounded valence and bounded genus). In FCT, pages 310-327, 1983. Google Scholar
  26. Yota Otachi and Pascal Schweitzer. Isomorphism on subgraph-closed graph classes: A complexity dichotomy and intermediate graph classes. In ISAAC, pages 111-118, 2013. Google Scholar
  27. Michaël Rao. Decomposition of (gem,co-gem)-free graphs. Unpublished, available at http://www.labri.fr/perso/rao/publi/decompgemcogem.ps, 2007. Google Scholar
  28. Pascal Schweitzer. Problems of unknown complexity: Graph isomorphism and Ramsey theoretic numbers. PhD thesis, Universität des Saarlandes, Germany, 2009. Google Scholar
  29. Pascal Schweitzer. Towards an isomorphism dichotomy for hereditary graph classes. CoRR, abs/1411.1977, 2014. Google Scholar
  30. Ákos Seress. Permutation Group Algorithms. Cambridge Tracts in Mathematics. Cambridge University Press, 2003. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact