2026-07-23T21:47:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19670 2024-03-06T11:04:36Z ddc:004 open_access

Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth Fluck, Eva Seppelt, Tim Spitzer, Gian Luca Treewidth treedepth homomorphism indistinguishability counting first-order logic 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eva Fluck and Tim Seppelt and Gian Luca Spitzer 2024 Is Part Of LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2024.27 urn:nbn:de:0030-drops-196704 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode