Santiago Guzm'an-Pro

collaborators

4 papers

cs.CC2026

On the complexity of Sandwich Problems for $M$ -partitions

Alexey Barsukov, Santiago GuzmÃ¡n-Pro

We present a structural classification of constraint satisfaction problems (CSP) described by reflexive complete $2$ -edge-coloured graphs. In particular, this classification extend…

cs.DM2025

A CSP approach to Graph Sandwich Problems

Manuel Bodirsky, Santiago GuzmÃ¡n-Pro

The \emph{Sandwich Problem} (SP) for a graph class $\calC$ is the following computational problem. The input is a pair of graphs $(V, E_{1})$ and $(V, E_{2})$ where $E_{1} \subseteq E_{2}$ , a…

math.LO2025

Hereditary First-Order Logic: the tractable quantifier prefix classes

Manuel Bodirsky, Santiago GuzmÃ¡n-Pro

Many computational problems can be modelled as the class of all finite structures $A$ that satisfy a fixed first-order sentence $I ¨ $ hereditarily, i.e., we require that eve…

cs.CC2025

Restricted CSPs and F-free Digraph Algorithmics

Santiago GuzmÃ¡n-Pro, Barnaby Martin

In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to $P_{k}$ -free and $P_{k}$ -subgraph-f…

On the complexity of Sandwich Problems for M-partitions

A CSP approach to Graph Sandwich Problems

Hereditary First-Order Logic: the tractable quantifier prefix classes

Restricted CSPs and F-free Digraph Algorithmics

On the complexity of Sandwich Problems for $M$ -partitions