CS Paper Radar

On Counting Graphs for Modal Logic with Counting

Avijeet Ghosh, François Schwarzentruber

cs.AI cs.LO ·submitted 2026-10-19 11:17 UTC · v1

Abstract

In this paper, we study the theoretical computational complexity of counting trees and graphs that are classified positively by a graph neural networks, or said equivalently that satisfy a given formula of modal logic with counting. We also study convergence.

Closest papers

Nearest neighbours by meaning across the whole index.

Recurrent Graph Neural Networks with Set-Based Aggregation

cs.AI ·2026-09-14 ·Blai Bonet
similarity 0.64
Abstract

Recurrent GNNs iterate message passing to convergence, and their logical characterizations to date rely on multi-set aggregation, graded (counting) logics, and halting or acceptance conditions that cannot be verified from the network's parameters. We study recurrent GNNs with set-based aggregation and identify sufficient conditions checkable from the weights for networks to compile into formulas and formulas into networks. The main result is an effective, two-directional equivalence between a class of networks and the Boolean closure of reachability and safety properties, the fragment B$Σ^{\circ}_1$ of the modal $μ$-calculus. The fragment is not an artifact: it is the exact expressive level of stabilization over finite vocabulary, which supports fixed points of a single polarity and Boolean combinations thereof, but not the composition of fixed points of opposite polarities. The correspondence needs no counting logic, no external halting signal, and no non-effective acceptance condition, yielding a verifiable path from weights to symbolic explanations for networks meeting the conditions.

0.27

Deciding two-variable logic with global and local Presburger quantification

cs.LO math.LO ·2026-10-29 ·Michael Benedikt, Chia-Hsuan Lu, Alex Perry, Tony Tan
similarity 0.62
Abstract

We look at a two-variable logic over finite graphs that allows Presburger quantifiers: linear arithmetic inequalities between the number of elements that satisfy subformulas. The prior literature shows that closing two-variable logic under Presburger quantification leads to undecidability, while closing under \emph{local quantification} -- the counts are always over neighbors of a given node -- preserves decidability. Here we show decidability of satisfiability for an intermediate logic that allows both local counts and global counts, but where the linear constraints do not mix the two. The proof requires a significant extension of the prior machinery developed for two-variable logic with counting. As a corollary we obtain decidability of satisfiability for an important family of Graph Neural Networks (GNNs). GNNs are a popular graph learning formalism. For example, in a variation of GNNs considered in the past literature, local aggregation is used in each layer to create modified values at each vertex of a graph, and then global aggregation is used in a final layer to obtain a single numerical value for the graph as a whole. Our logic is motivated by the fact that mixing of local counting and global aggregation in GNNs has been shown to lead to undecidability. Our results here show that if global and local aggregation are separated, one regains decidability. Decidability of other static analysis problems, like equivalence of GNNs, follows from the decidability of satisfiability.

0.23

Robust Algebraic Theories of Triangle Graphs

cs.FL ·2026-08-11 ·Marius Bozga, Radu Iosif, Florian Zuleger
theory similarity 0.60
Abstract

Triangle graphs are graphs of tree-width at most three in which every edge belongs to a triangle. This class encompasses well-known graph families such as Apollonian networks. We also consider fan graphs, a subclass of triangle graphs closely related to the 3-connected triangle graphs. Our main result is an algebraic characterization of both classes. We introduce two graph algebras based on parallel composition and a ternary serial composition, and show that they generate exactly the triangle and fan graphs, respectively. These algebras provide a natural extension of the classical algebra of series-parallel graphs from tree-width two to tree-width three. Building on these characterizations, we investigate context-free, recognizable, and logically-definable graph languages. We show that counting monadic second-order logic (CMSO) is decidable over the context-free sets of triangle and fan graphs. Moreover, we prove that recognizable graph languages coincide with languages definable in CMSO for both algebras.

0.04

Counting Feedback Vertex Sets of All Sizes in Subexponential Time, Conditionally

cs.DS ·2026-11-02 ·Mengyang Wu, Minghao Wang
theoryhot direction similarity 0.59
Abstract · 27 pages

Assuming a Boolean tensor contraction hypothesis (Theorem D.1 of OpenAI's recent preprint refuting the Exponential Time Hypothesis), we study exact feedback vertex set counting in general graphs. For an $n$-vertex, $m$-edge simple graph, we compute the complete size distribution deterministically in $\mathrm{poly}(n+m)\,2^{O(n(\log\log n)^2/\sqrt{\log n})}$ time and polynomial working space. The algorithm combines a whole-edge forest identity, subset-index scalar networks, sparse parity filtering, and disjoint high-degree branching. A binomial inversion recovers the multiplicities introduced by exceptional-set guesses. The counting interface supports fixed vertices, minimum solutions, and unranking. Component markers yield induced-tree and induced-path counts within the same bound. Sparse Hamilton, forest, and Steiner edge-tree counting follow from the scalar encoding.

0.38

Extensions of Courcelle's Theorem without Logic

cs.LO ·2026-08-21 ·Yuval Filmus, Johann A. Makowsky
theory similarity 0.58
Abstract · 17 pages. This is an expanded and improved version of arXiv:2505.02771

Courcelle's Theorem states that on graphs $G$ of tree-width at most $k$ with a given tree-decomposition of size $t(G)$, graph properties $\mathcal{P}$ definable in Monadic Second Order Logic can be checked in linear time in the size of $t(G)$. Inspired by L. Lovász' work using connection matrices instead of logic, we give a generalized version of Courcelle's theorem which replaces the definability hypothesis by a purely combinatorial hypothesis using a generalization of connection matrices. This paper clarifies the role of logic in such theorems and displays their purely combinatorial assumption.

0.18

An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability

cs.DM ·2026-11-02 ·Moritz Lichter, Harry Vinall-Smeeth
theory similarity 0.57
Abstract · 66 pages

One way to compare two graphs $G_1, G_2$ is to check whether there is some graph $H$ in a graph class $\mathcal{H}$, such that the number of homomorphisms from $H$ to $G_1$ is not equal to that from $H$ to $G_2$. This is the field of homomorphism distinguishability which has gained a lot of traction in recent years. In this paper, we study the case where $\mathcal{H}$ is the class of graphs of treewidth $k$. This has connections to important concepts in logic, machine learning, combinatorial optimization and proof complexity. In particular, Dvořák showed that $G_1$ and $G_2$ can be distinguished by a homomorphism count from a graph of treewidth $k$ iff $G_1$ and $G_2$ are distinguishable by the $k$-dimensional Weisfeiler-Leman algorithm. While the relation between the iteration number of this algorithm and the depth of the tree-decomposition of a distinguishing graph is understood, our understanding of the \emph{size} of $H$ is limited. We show a $2^{Ω(n^{k/2})}$ lower bound on the size of a graph of treewidth $k$ required to distinguish two graphs of order $n$. This bound is proved via a new combinatorial game along with a construction which uses a recent compression technique for CFI graphs. It is almost tight to the known $2^{O(n^{k+1})}$ upper bound and is an exponential improvement on the previous best known lower bound.

0.25

The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas

cs.CC cs.DS ·2026-08-20 ·Takashi Horiyama, Shoon Mineyoshi, Yuto Okura, Kazuhisa Seto, Junichi Teruyama
theory similarity 0.56
Abstract

The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the computational complexity of {\sc Conn $k$-Horn}, the Boolean connectivity problem for $k$-Horn formulas. We provide algorithmic and hardness results for {\sc Conn $k$-Horn}. On the algorithmic side, we first present an exact exponential-time algorithm for arbitrary $k$ without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in $O^*(2^{(1 - 1/2k)n})$ time and polynomial space, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of $k$-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We next give two polynomial-time algorithms for arbitrary $k$ under the following two restrictions: (i) each variable appears at most twice, and (ii) each clause has length exactly $k$ and each variable appears at most $k$ times. On the hardness side, we prove that {\sc Conn $3$-Horn} remains $\mathsf{coNP}$-complete even when each variable appears exactly three times.

0.26

Vector space embeddings of modal logic formulas: theory and application

cs.LO ·2026-10-25 ·Pietro Casavecchia, Alberto Paparella, Leonardo Serrentino
code/data similarity 0.56
Abstract · 6 pages, 1 figure. Presented at the ESSLLI 2025 Student Session, Bochum. An extended version appeared as "Semantic Embeddings for Modal Logi…

Reasoning tasks over modal logics are notoriously difficult, comprising problems which are often semi-decidable. Hence, it is not rare for applications leveraging such tasks to exploit heuristic approaches able to give results in an acceptable amount of time, at the cost of some inaccuracies. Some approaches may benefit from vector embeddings, allowing for instance to involve neural networks and machine learning models in the reasoning process. This work aims at providing a new way to provide such embeddings specifically for the modal case, aiming for faster reasoning through both mathematical and learning techniques.

0.46