30 research outputs found
An Algorithmic Meta Theorem for Homomorphism Indistinguishability
No full textTwo graphs G and H are homomorphism indistinguishable over a family of graphs ℱ if for all graphs F ∈ ℱ the number of homomorphisms from F to G is equal to the number of homomorphism from F to H. Many natural equivalence relations comparing graphs such as (quantum) isomorphism, cospectrality, and logical equivalences can be characterised as homomorphism indistinguishability relations over various graph classes.
The wealth of such results motivates a more fundamental study of homomorphism indistinguishability. From a computational perspective, the central object of interest is the decision problem HomInd(ℱ) which asks to determine whether two input graphs G and H are homomorphism indistinguishable over a fixed graph class ℱ. The problem HomInd(ℱ) is known to be decidable only for few graph classes ℱ. Due to a conjecture by Roberson (2022) and results by Seppelt (MFCS 2023), homomorphism indistinguishability relations over minor-closed graph classes are of special interest. We show that HomInd(ℱ) admits a randomised polynomial-time algorithm for every minor-closed graph class ℱ of bounded treewidth.
This result extends to a version of HomInd where the graph class ℱ is specified by a sentence in counting monadic second-order logic and a bound k on the treewidth, which are given as input. For fixed k, this problem is randomised fixed-parameter tractable. If k is part of the input, then it is coNP- and coW[1]-hard. Addressing a problem posed by Berkholz (2012), we show coNP-hardness by establishing that deciding indistinguishability under the k-dimensional Weisfeiler-Leman algorithm is coNP-hard when k is part of the input
Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
No full textTwo graphs and are homomorphism indistinguishable over a class of
graphs if for all graphs the number of
homomorphisms from to is equal to the number of homomorphisms from
to . Many natural equivalence relations comparing graphs such as (quantum)
isomorphism, spectral, and logical equivalences can be characterised as
homomorphism indistinguishability relations over certain graph classes.
Abstracting from the wealth of such instances, we show in this paper that
equivalences w.r.t. any self-complementarity logic admitting a characterisation
as homomorphism indistinguishability relation can be characterised by
homomorphism indistinguishability over a minor-closed graph class.
Self-complementarity is a mild property satisfied by most well-studied logics.
This result follows from a correspondence between closure properties of a graph
class and preservation properties of its homomorphism indistinguishability
relation.
Furthermore, we classify all graph classes which are in a sense finite
(essentially profinite) and satisfy the maximality condition of being
homomorphism distinguishing closed, i.e. adding any graph to the class strictly
refines its homomorphism indistinguishability relation. Thereby, we answer
various questions raised by Roberson (2022) on general properties of the
homomorphism distinguishing closure.Comment: 27 pages, 1 figure, 1 tabl
Homomorphism Tensors and Linear Equations
No full textLov\'asz (1967) showed that two graphs and are isomorphic if and only
if they are homomorphism indistinguishable over the class of all graphs, i.e.
for every graph , the number of homomorphisms from to equals the
number of homomorphisms from to . Recently, homomorphism
indistinguishability over restricted classes of graphs such as bounded
treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly
powerful framework for capturing diverse equivalence relations on graphs
arising from logical equivalence and algebraic equation systems.
In this paper, we provide a unified algebraic framework for such results by
examining the linear-algebraic and representation-theoretic structure of
tensors counting homomorphisms from labelled graphs. The existence of certain
linear transformations between such homomorphism tensor subspaces can be
interpreted both as homomorphism indistinguishability over a graph class and as
feasibility of an equational system. Following this framework, we obtain
characterisations of homomorphism indistinguishability over several natural
graph classes, namely trees of bounded degree and graphs of bounded pathwidth,
answering a question of Dell et al. (2018), and graphs of bounded treedepth
Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth
No full textWe 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)
Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
No full textWe show that feasibility of the level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability relation. In other words, we define a class of graphs such that graphs and are not distinguished by the level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in . By analysing the treewidth of graphs in , we prove that the level of Sherali--Adams linear programming hierarchy is as strong as the level of Lasserre. Moreover, we show that this is best possible in the sense that cannot be lowered to for any . The same result holds for the Lasserre hierarchy with non-negativity constraints, which we similarly characterise in terms of homomorphism indistinguishability over a family of graphs. Additionally, we give characterisations of level- Lasserre with non-negativity constraints in terms of logical equivalence and via a graph colouring algorithm akin to the Weisfeiler--Leman algorithm. This provides a polynomial time algorithm for determining if two given graphs are distinguished by the level of the Lasserre hierarchy with non-negativity constraints.Full version. 36 pages, 6 figure
The Complexity of Homomorphism Reconstructibility
No full textRepresenting graphs by their homomorphism counts has led to the beautiful theory of homomorphism indistinguishability in recent years. Moreover, homomorphism counts have promising applications in database theory and machine learning, where one would like to answer queries or classify graphs solely based on the representation of a graph G as a finite vector of homomorphism counts from some fixed finite set of graphs to G. We study the computational complexity of the arguably most fundamental computational problem associated to these representations, the homomorphism reconstructability problem: given a finite sequence of graphs and a corresponding vector of natural numbers, decide whether there exists a graph G that realises the given vector as the homomorphism counts from the given graphs.
We show that this problem yields a natural example of an NP^#-hard problem, which still can be NP-hard when restricted to a fixed number of input graphs of bounded treewidth and a fixed input vector of natural numbers, or alternatively, when restricted to a finite input set of graphs. We further show that, when restricted to a finite input set of graphs and given an upper bound on the order of the graph G as additional input, the problem cannot be NP-hard unless = NP. For this regime, we obtain partial positive results. We also investigate the problem’s parameterised complexity and provide fpt-algorithms for the case that a single graph is given and that multiple graphs of the same order with subgraph instead of homomorphism counts are given
Homomorphism indistinguishability
No full textTwo graphs G and H are homomorphism indistinguishable over a class of graphs if, for all graphs F ∊ , the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. In 1967, Lovász showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over the class of all graphs. Subsequently, many graph isomorphism relaxations such as quantum isomorphism, spectral, and logical equivalences have been characterised as homomorphism indistinguishability relations over certain graph classes. Thereby, homomorphism indistinguishability connects seemingly disparate fields such as quantum information, finite model theory, and machine learning. This thesis explores three themes: We first review the plenitude of characterisations of graph isomorphism relaxations as a homomorphism indistinguishability relation. Focusing on integer programming relaxations for graph isomorphism, we prove that the feasibility of each level of the Sherali–Adams and Lasserre hierarchies is characterised as homomorphism indistinguishability relations. These results, which are derived using (bi)labelled graphs and homomorphism tensors, shed light on the distinguishing power of these hierarchies. In particular, we determine the precise number of Sherali–Adams levels necessary such that their feasibility guarantees the feasibility of a given Lasserre level. Abstracting from the wealth of homomorphism indistinguishability characterisations, we embark on a more principled study of homomorphism indistinguishability investigating the distinguishing power and the complexity of homomorphism indistinguishability relations over minor-closed graph class. The homomorphism distinguishing closure cl() of a graph class is the central notion for studying the distinguishing power of homomorphism indistinguishability relations. It is defined as the maximal graph class whose homomorphism indistinguishability relation coincides with the one of . Roberson conjectured that every minor-closed union-closed graph class is homomorphism distinguishing closed, i.e. cl() = . We confirm Roberson's conjecture, which is generally wide open, for further graphs classes and prove unconditionally that if is minor-closed then so is cl(). Lastly, we investigate the complexity of deciding whether two graphs are homomorphism indistinguishable over a fixed graph class. For infinite graph classes, this problem is a priori not even decidable. In stark contrast to this, we show that, over every minor-closed graph class of bounded treewidth, homomorphism indistinguishability can be decided in randomised polynomial time
