On Algorithms Based on Finitely Many Homomorphism Counts

Authors Yijia Chen , Jörg Flum, Mingjun Liu, Zhiyang Xun



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.32.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Author Details

Yijia Chen
  • Shanghai Jiao Tong University, Shanghai, China
Jörg Flum
  • Albert-Ludwigs-Universität, Freiburg i.Br., Germany
Mingjun Liu
  • Fudan University, Shanghai, China
Zhiyang Xun
  • Shanghai Jiao Tong University, Shanghai, China

Acknowledgements

Mingjun Liu is supervised by Yijia Chen in the Mathematical Logic Program for undergraduate students at Fudan University.

Cite As Get BibTex

Yijia Chen, Jörg Flum, Mingjun Liu, and Zhiyang Xun. On Algorithms Based on Finitely Many Homomorphism Counts. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.32

Abstract

It is well known [L. Lovász, 1967] that up to isomorphism a graph G is determined by the homomorphism counts hom(F, G), i.e., by the number of homomorphisms from F to G where F ranges over all graphs. Moreover, it suffices that F ranges over the graphs with at most as many vertices as G. Thus, in principle, we can answer any query concerning G with only accessing the hom(⋅, G)’s instead of G itself. In this paper, we deal with queries for which there is a hom algorithm, i.e., there are finitely many graphs F₁, …, F_k such that for any graph G whether it is a Yes-instance of the query is already determined by the vector hom^⟶_{F₁, …, F_k}(G): = (hom(F₁, G), …, hom(F_k, G)).
We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. On the other hand, queries expressible as a Boolean combination of universal sentences in first-order logic FO have a hom algorithm. Even though it is not easy to find FO definable queries without a hom algorithm, we succeed to show this for the non-existence of an isolated vertex, a property expressible by the FO sentence ∀ x∃ y Exy, somehow the "simplest" graph property not definable by a Boolean combination of universal sentences. These results provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm.
For adaptive hom algorithms, i.e., algorithms that might access a hom(F_{i+1}, G) with F_{i+1} depending on hom(F_j, G) for 1 ≤ j ≤ i we show that three homomorphism counts hom(⋅, G) are sufficient and in general necessary to determine the (isomorphism type of) G. In particular, by three adaptive queries we can answer any question on G. Moreover, adaptively accessing two hom(⋅, G)’s is already enough to detect an isolated vertex.
In 1993 Chaudhuri and Vardi [S. Chaudhuri and M. Y. Vardi, 1993] showed the analogue of the Lovász Isomorphism Theorem for the right homomorphism vector of a graph G, i.e, the vector of values hom(G,F) where F ranges over all graphs characterizes the isomorphism type of G. We study to what extent our results carry over to the right homomorphism vector.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph theory
Keywords
  • homomorphism numbers
  • hom algorithms
  • adaptive hom algorithms

Metrics

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

References

  1. A. Atserias, P. Kolaitis, and W. Wu. On the expressive power of homomorphism counts. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-13. IEEE, 2021. Google Scholar
  2. J. Böker. Graph similarity and homomorphism densities. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 32:1-32:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  3. J. Böker, Y. Chen, M. Grohe, and G. Rattan. The complexity of homomorphism indistinguishability. In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, pages 54:1-54:13, 2019. Google Scholar
  4. C. Borgs, J. Chayes, L. Lovász, V.T. Sós, and K. Vesztergombi. Counting graph homomorphisms. In Topics in Discrete Mathematics, pages 315-371, 2006. Google Scholar
  5. J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992. Google Scholar
  6. S. Chaudhuri and M. Y. Vardi. Optimization of Real conjunctive queries. In Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1993, pages 59-70. ACM Press, 1993. Google Scholar
  7. Y. Chen and J. Flum. Tree-depth, quantifier elimination, and quantifier rank. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 225-234, 2018. Google Scholar
  8. Y. Chen and J. Flum. FO-definability of shrub-depth. In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, January 13-16, 2020, Barcelona, Spain, pages 15:1-15:16, 2020. Google Scholar
  9. R. Curticapean, H. Dell, and D. Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 210-223. ACM, 2017. Google Scholar
  10. H. Dell, M. Grohe, and G. Rattan. Lovász meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107, pages 40:1-40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  11. G. Ding. Subgraphs and well-quasi-ordering. Journal of Graph Theory, 16(5):489-502, 1992. Google Scholar
  12. Z. Dvorák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64(4):330-342, 2010. Google Scholar
  13. R. Ganian, P. Hlinený, J. Nesetril, J. Obdrzálek, P. Ossona de Mendez, and R. Ramadurai. When trees grow low: Shrubs and fast MSO₁. In Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, pages 419-430, 2012. Google Scholar
  14. M. Grohe. Counting bounded tree depth homomorphisms. In LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020, pages 507-520. ACM, 2020. Google Scholar
  15. M. Grohe. word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, pages 1-16. ACM, 2020. Google Scholar
  16. L. Lovász. Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica, 18:321-328, 1967. Google Scholar
  17. L. Lovász. On the cancellation law among finite relational structures. Periodica Mathematica Hungarica, 1:145-156, 1971. Google Scholar
  18. T. A. McKee. Forbidden subgraphs in terms of forbidden quantifiers. Notre Dame Journal of Formal Log., 19:186-188, 1978. Google Scholar
  19. J. Mycielski. Sur le coloriage des graphes. Information Processing Letters, 108(6):412-417, 2008. 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