License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.79
URN: urn:nbn:de:0030-drops-186131
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18613/
Scheidt, Benjamin ;
Schweikardt, Nicole
Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
Abstract
We introduce the 2-sorted counting logic GC^k and its restriction RGC^k that express properties of hypergraphs. These logics have available k variables to address hyperedges, an unbounded number of variables to address vertices of a hypergraph, and atomic formulas E(e,v) to express that a vertex v is contained in a hyperedge e. We show that two hypergraphs H,H' satisfy the same sentences of the logic RGC^k if, and only if, they are homomorphism indistinguishable over the class of hypergraphs of generalised hypertree width at most k. Here, H,H' are called homomorphism indistinguishable over a class ? if for every hypergraph G ∈ ? the number of homomorphisms from G to H equals the number of homomorphisms from G to H'. This result can be viewed as a lifting (from graphs to hypergraphs) of a result by Dvořák (2010) stating that any two (undirected, simple, finite) graphs H,H' are indistinguishable by the k+1-variable counting logic C^{k+1} if, and only if, they are homomorphism indistinguishable over the class of graphs of tree-width at most k.
BibTeX - Entry
@InProceedings{scheidt_et_al:LIPIcs.MFCS.2023.79,
author = {Scheidt, Benjamin and Schweikardt, Nicole},
title = {{Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {79:1--79:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-292-1},
ISSN = {1868-8969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18613},
URN = {urn:nbn:de:0030-drops-186131},
doi = {10.4230/LIPIcs.MFCS.2023.79},
annote = {Keywords: counting logics, guarded logics, homomorphism counting, hypertree decompositions, hypergraphs, incidence graphs, quantum graphs}
}
Keywords: |
|
counting logics, guarded logics, homomorphism counting, hypertree decompositions, hypergraphs, incidence graphs, quantum graphs |
Collection: |
|
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
21.08.2023 |