Skip to main content

2019 | OriginalPaper | Buchkapitel

Color Refinement, Homomorphisms, and Hypergraphs

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Recent results show that the structural similarity of graphs can be characterized by counting homomorphisms to them: the Tree Theorem states that the well-known color-refinement algorithm does not distinguish two graphs G and H if and only if, for every tree T, the number of homomorphisms \(\mathsf {Hom}(T, G)\) from T to G is equal to the corresponding number \(\mathsf {Hom}(T, H)\) from T to H (Dell, Grohe, Rattan 2018). We show how this approach transfers to hypergraphs by introducing a generalization of color refinement. We prove that it does not distinguish two hypergraphs G and H if and only if, for every connected Berge-acyclic hypergraph B, we have \(\mathsf {Hom}(B, G) = \mathsf {Hom}(B, H)\). To this end, we show how homomorphisms of hypergraphs and of a colored variant of their incidence graphs are related to each other. This reduces the above statement to one about vertex-colored graphs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
3.
Zurück zum Zitat Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recogn. Artif. Intell. 18(3), 265–298 (2004)CrossRef Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recogn. Artif. Intell. 18(3), 265–298 (2004)CrossRef
4.
Zurück zum Zitat Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 210–223. ACM (2017) Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 210–223. ACM (2017)
6.
Zurück zum Zitat Dell, H., Grohe, M., Rattan, G.: Lovász meets Weisfeiler and Leman. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, pp. 40:1–40:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018) Dell, H., Grohe, M., Rattan, G.: Lovász meets Weisfeiler and Leman. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, pp. 40:1–40:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
9.
Zurück zum Zitat Lovász, L.: On the cancellation law among finite relational structures. Periodica Math. Hung. 1(2), 145–156 (1971)MathSciNetCrossRef Lovász, L.: On the cancellation law among finite relational structures. Periodica Math. Hung. 1(2), 145–156 (1971)MathSciNetCrossRef
10.
Zurück zum Zitat Lovász, L.: Large Networks and Graph Limits. American Mathematical Society (2012) Lovász, L.: Large Networks and Graph Limits. American Mathematical Society (2012)
13.
Zurück zum Zitat Vishwanathan, S.V.N., Schraudolph, N.N., Kondor, R., Borgwardt, K.M.: Graph kernels. J. Mach. Learn. Res. 11, 1201–1242 (2010)MathSciNetMATH Vishwanathan, S.V.N., Schraudolph, N.N., Kondor, R., Borgwardt, K.M.: Graph kernels. J. Mach. Learn. Res. 11, 1201–1242 (2010)MathSciNetMATH
Metadaten
Titel
Color Refinement, Homomorphisms, and Hypergraphs
verfasst von
Jan Böker
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-30786-8_26