72 citations · 320 across the 78 of their papers we have counts for
96 papers
Graph Homomorphisms and Universal Algebra
Manuel Bodirsky
Constraint satisfaction problems are computational problems that naturally appear in many areas of theoretical computer science. One of the central themes is their computational co…
The complexity of finding coset-generating polymorphisms and the promise metaproblem
Manuel Bodirsky, Armin Weiß
We show that the metaproblem for coset-generating polymorphisms is NP-complete, answering a question of Chen and Larose: given a finite structure, the computational question is whe…
The Complexity of Resilience for Digraph Queries
Manuel Bodirsky, Žaneta Semanišinová
We prove a complexity dichotomy for the resilience problem for unions of conjunctive digraph queries (i.e., for existential positive sentences over the signature of directe…
Taking model-complete cores
Manuel Bodirsky, Bertalan Bodor, Paolo Marimon
A first-order theory is a model-complete core theory if every first-order formula is equivalent modulo to an existential positive formula; a core companion of a theory …
Circular Chromatic Numbers, Signability, Relation Algebras, and Network Satisfaction Problems
Manuel Bodirsky, Santiago Guzmán-Pro, Moritz Jahn +2
In this paper, we characterize finite graphs with circular chromatic number less than 3 in terms of the existence of certain signings (-labellings studied in the conte…
On the Computational Power of Extensional ESO
Manuel Bodirsky, Santiago Guzmán Pro
Extensional ESO is a fragment of existential second-order logic (ESO) that captures the following family of problems. Given a fixed ESO sentence and an input structure $\mathbb…