Document

**Published in:** LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

We study the expressive power of first-order logic with counting quantifiers, especially the k-variable and quantifier-rank-q fragment 𝖢^k_q, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio (2021) proved that two graphs satisfy the same 𝖢^k_q-sentences if and only if they are homomorphism indistinguishable over the class 𝒯^k_q of graphs admitting a k-pebble forest cover of depth q. Their proof builds on the categorical framework of game comonads developed by Abramsky, Dawar, and Wang (2017). We reprove their result using elementary techniques inspired by Dvořák (2010). Using these techniques we also give a characterisation of guarded counting logic. Our main focus, however, is to provide a graph theoretic analysis of the graph class 𝒯^k_q. This allows us to separate 𝒯^k_q from the intersection of the graph class TW_{k-1}, that is graphs of treewidth less or equal k-1, and TD_q, that is graphs of treedepth at most q if q is sufficiently larger than k. We are able to lift this separation to the semantic separation of the respective homomorphism indistinguishability relations. A part of this separation is to prove that the class TD_q is homomorphism distinguishing closed, which was already conjectured by Roberson (2022).

Eva Fluck, Tim Seppelt, and Gian Luca Spitzer. Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fluck_et_al:LIPIcs.CSL.2024.27, author = {Fluck, Eva and Seppelt, Tim and Spitzer, Gian Luca}, title = {{Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {27:1--27:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.27}, URN = {urn:nbn:de:0030-drops-196704}, doi = {10.4230/LIPIcs.CSL.2024.27}, annote = {Keywords: Treewidth, treedepth, homomorphism indistinguishability, counting first-order logic} }

Document

**Published in:** LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

We establish a connection between tangles, a concept from structural graph theory that plays a central role in Robertson and Seymour’s graph minor project, and hierarchical clustering. Tangles cannot only be defined for graphs, but in fact for arbitrary connectivity functions, which are functions defined on the subsets of some finite universe, which in typical clustering applications consists of points in some metric space.
Connectivity functions are usually required to be submodular. It is our first contribution to show that the central duality theorem connecting tangles with hierarchical decompositions (so-called branch decompositions) also holds if submodularity is replaced by a different property that we call maximum-submodular.
We then define a natural, though somewhat unusual connectivity function on finite data sets in an arbitrary metric space and prove that its tangles are in one-to-one correspondence with the clusters obtained by applying the well-known single linkage clustering algorithms to the same data set.
The idea of viewing tangles as clusters has first been proposed by Diestel and Whittle [Reinhard Diestel et al., 2019] as an approach to image segmentation. To the best of our knowledge, our result is the first that establishes a precise technical connection between tangles and clusters.

Eva Fluck. Tangles and Single Linkage Hierarchical Clustering. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 38:1-38:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fluck:LIPIcs.MFCS.2019.38, author = {Fluck, Eva}, title = {{Tangles and Single Linkage Hierarchical Clustering}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {38:1--38:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.38}, URN = {urn:nbn:de:0030-drops-109826}, doi = {10.4230/LIPIcs.MFCS.2019.38}, annote = {Keywords: Tangles, Branch Decomposition, Duality, Hierarchical Clustering, Single Linkage} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail