Victor Dalmau
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Victor Dalmau has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Andrei Krokhin
Durham University Durham University
5 shared publications - Balder Ten Cate
University of Amsterdam
3 shared publications - Carsten Lutz
Leipzig University
2 shared publications - Catarina Carvalho
School of Physics, Astronomy and Mathematics University of Hertfordshire
2 shared publications - Hubie Chen
Departament de Tecnologies de la Informació i les Comunicacions Universitat Pompeu Fabra Barcelona Spain
2 shared publications - Jakub Opršal
University of Birmingham, Birmingham, United Kingdom
2 shared publications
Latest Publications
- Open Access
- 13 October 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
Extremal Fitting Problems for Conjunctive Queries
The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not unique. This leads us to propose natural refinements of the notion of a fitting CQ, such as most-general fitting CQ , most-specific fitting CQ , and unique fitting CQ . We give structural characterizations of these notions in terms of (suitable refinements of) homomorphism dualities, frontiers, and direct products, which enable the construction of the refined fitting CQs when they exist. We also pinpoint the complexity of the associated existence and verification problems, and determine the size of fitting CQs. We study the same problems for unions of CQs (UCQs).
- 13 October 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
Open AccessExtremal Fitting Problems for Conjunctive Queries
The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not unique. This leads us to propose natural refinements of the notion of a fitting CQ, such as most-general fitting CQ , most-specific fitting CQ , and unique fitting CQ . We give structural characterizations of these notions in terms of (suitable refinements of) homomorphism dualities, frontiers, and direct products, which enable the construction of the refined fitting CQs when they exist. We also pinpoint the complexity of the associated existence and verification problems, and determine the size of fitting CQs. We study the same problems for unions of CQs (UCQs).
- Open Access
- 25 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (1) , 1-37
The Sherali–Adams and Weisfeiler–Leman Hierarchies in (Promise Valued) Constraint Satisfaction Problems
In this article, we study the interactions between so-called fractional relaxations of the integer programs (IPs) which encode homomorphism and isomorphism of relational structures. We give a combinatorial characterization of a certain natural linear programming (LP) relaxation of homomorphism in terms of fractional isomorphism. As a result, we show that the families of constraint satisfaction problems (CSPs) that are solvable by such linear program are precisely those that are closed under an equivalence relation which we call Weisfeiler-Leman invariance . We also generalize this result to the much broader framework of Promise Valued Constraint Satisfaction Problems, which brings together two well-studied extensions of the CSP framework. Finally, we consider the hierarchies of increasingly tighter relaxations of the homomorphism and isomorphism IPs obtained by applying the Sherali-Adams and Weisfeiler-Leman methods, respectively. We extend our combinatorial characterization of the basic LP to higher levels of the Sherali-Adams hierarchy, and we generalize a well-known logical characterization of the Weisfeiler-Leman test from graphs to relational structures.
- 25 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (1) , 1-37
Open AccessThe Sherali–Adams and Weisfeiler–Leman Hierarchies in (Promise Valued) Constraint Satisfaction Problems
In this article, we study the interactions between so-called fractional relaxations of the integer programs (IPs) which encode homomorphism and isomorphism of relational structures. We give a combinatorial characterization of a certain natural linear programming (LP) relaxation of homomorphism in terms of fractional isomorphism. As a result, we show that the families of constraint satisfaction problems (CSPs) that are solvable by such linear program are precisely those that are closed under an equivalence relation which we call Weisfeiler-Leman invariance . We also generalize this result to the much broader framework of Promise Valued Constraint Satisfaction Problems, which brings together two well-studied extensions of the CSP framework. Finally, we consider the hierarchies of increasingly tighter relaxations of the homomorphism and isomorphism IPs obtained by applying the Sherali-Adams and Weisfeiler-Leman methods, respectively. We extend our combinatorial characterization of the basic LP to higher levels of the Sherali-Adams hierarchy, and we generalize a well-known logical characterization of the Weisfeiler-Leman test from graphs to relational structures.
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-15
Local consistency as a reduction between constraint satisfaction problems
We study the use of local consistency methods as reductions between constraint satisfaction problems (CSPs), and promise version thereof, with the aim to classify these reductions in a similar way as the algebraic approach classifies gadget reductions between CSPs. This research is motivated by the requirement of more expressive reductions in the scope of promise CSPs. While gadget reductions are enough to provide all necessary hardness in the scope of (finite domain) non-promise CSP, in promise CSPs a wider class of reductions needs to be used. We provide a general framework of reductions, which we call consistency reductions, that covers most (if not all) reductions recently used for proving NP-hardness of promise CSPs. We prove some basic properties of these reductions, and provide the first steps towards understanding the power of consistency reductions by characterizing a fragment associated to arc-consistency in terms of polymorphisms of the template. In addition to showing hardness, consistency reductions can also be used to provide feasible algorithms by reducing to a fixed tractable (promise) CSP, for example, to solving systems of affine equations. In this direction, among other results, we describe the well-known Sherali-Adams hierarchy for CSP in terms of a consistency reduction to linear programming.
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-15
Open AccessLocal consistency as a reduction between constraint satisfaction problems
We study the use of local consistency methods as reductions between constraint satisfaction problems (CSPs), and promise version thereof, with the aim to classify these reductions in a similar way as the algebraic approach classifies gadget reductions between CSPs. This research is motivated by the requirement of more expressive reductions in the scope of promise CSPs. While gadget reductions are enough to provide all necessary hardness in the scope of (finite domain) non-promise CSP, in promise CSPs a wider class of reductions needs to be used. We provide a general framework of reductions, which we call consistency reductions, that covers most (if not all) reductions recently used for proving NP-hardness of promise CSPs. We prove some basic properties of these reductions, and provide the first steps towards understanding the power of consistency reductions by characterizing a fragment associated to arc-consistency in terms of polymorphisms of the template. In addition to showing hardness, consistency reductions can also be used to provide feasible algorithms by reducing to a fixed tractable (promise) CSP, for example, to solving systems of affine equations. In this direction, among other results, we describe the well-known Sherali-Adams hierarchy for CSP in terms of a consistency reduction to linear programming.
- 3 July 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (3) , 2041-2068
Functors on Relational Structures Which Admit Both Left and Right Adjoints
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors [Formula: see text] and [Formula: see text] between thin categories of relational structures are adjoint if for all structures [Formula: see text] and [Formula: see text], we have that [Formula: see text] maps homomorphically to [Formula: see text] if and only if [Formula: see text] maps homomorphically to [Formula: see text]. If this is the case, [Formula: see text] is called the left adjoint to [Formula: see text] and [Formula: see text] the right adjoint to [Formula: see text]. Foniok and Tardif [ Discrete Math., 338 (2015), pp. 527–535] described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr [ Reports of the Midwest Category Seminar IV, Lecture Notes in Math. 137, Springer, 1970, pp. 100–113]. We generalize results of Foniok and Tardif to arbitrary relational structures, and coincidently, we also provide more right adjoints on digraphs, and since these constructions are connected to finite duality, we also provide a new construction of duals to trees. Our results are inspired by an application in promise constraint satisfaction—it has been shown that such functors can be used as efficient reductions between these problems.
- 3 July 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (3) , 2041-2068
Functors on Relational Structures Which Admit Both Left and Right Adjoints
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors [Formula: see text] and [Formula: see text] between thin categories of relational structures are adjoint if for all structures [Formula: see text] and [Formula: see text], we have that [Formula: see text] maps homomorphically to [Formula: see text] if and only if [Formula: see text] maps homomorphically to [Formula: see text]. If this is the case, [Formula: see text] is called the left adjoint to [Formula: see text] and [Formula: see text] the right adjoint to [Formula: see text]. Foniok and Tardif [ Discrete Math., 338 (2015), pp. 527–535] described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr [ Reports of the Midwest Category Seminar IV, Lecture Notes in Math. 137, Springer, 1970, pp. 100–113]. We generalize results of Foniok and Tardif to arbitrary relational structures, and coincidently, we also provide more right adjoints on digraphs, and since these constructions are connected to finite duality, we also provide a new construction of duals to trees. Our results are inspired by an application in promise constraint satisfaction—it has been shown that such functors can be used as efficient reductions between these problems.
- Open Access
Functors on relational structures which admit both left and right adjoints
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors $Λ$ and $Γ$ between thin categories of relational structures are adjoint if for all structures $\mathbf A$ and $\mathbf B$, we have that $Λ(\mathbf A)$ maps homomorphically to $\mathbf B$ if and only if $\mathbf A$ maps homomorphically to $Γ(\mathbf B)$. If this is the case, $Λ$ is called the left adjoint to $Γ$ and $Γ$ the right adjoint to $Λ$. In 2015, Foniok and Tardif described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr in 1970. We generalise results of Foniok and Tardif to arbitrary relational structures, and coincidently, we also provide more right adjoints on digraphs, and since these constructions are connected to finite duality, we also provide a new construction of duals to trees. Our results are inspired by an application in promise constraint satisfaction -- it has been shown that such functors can be used as efficient reductions between these problems.Open AccessFunctors on relational structures which admit both left and right adjoints
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors $Λ$ and $Γ$ between thin categories of relational structures are adjoint if for all structures $\mathbf A$ and $\mathbf B$, we have that $Λ(\mathbf A)$ maps homomorphically to $\mathbf B$ if and only if $\mathbf A$ maps homomorphically to $Γ(\mathbf B)$. If this is the case, $Λ$ is called the left adjoint to $Γ$ and $Γ$ the right adjoint to $Λ$. In 2015, Foniok and Tardif described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr in 1970. We generalise results of Foniok and Tardif to arbitrary relational structures, and coincidently, we also provide more right adjoints on digraphs, and since these constructions are connected to finite duality, we also provide a new construction of duals to trees. Our results are inspired by an application in promise constraint satisfaction -- it has been shown that such functors can be used as efficient reductions between these problems. - Open Access
The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
In this paper we study the interactions between so-called fractional relaxations of the integer programs (IPs) which encode homomorphism and isomorphism of relational structures. We give a combinatorial characterization of a certain natural linear programming (LP) relaxation of homomorphism in terms of fractional isomorphism. As a result, we show that the families of constraint satisfaction problems (CSPs) that are solvable by such linear program are precisely those that are closed under an equivalence relation which we call Weisfeiler-Leman invariance. We also generalize this result to the much broader framework of Promise Valued Constraint Satisfaction Problems, which brings together two well-studied extensions of the CSP framework. Finally, we consider the hierarchies of increasingly tighter relaxations of the homomorphism and isomorphism IPs obtained by applying the Sherali-Adams and Weisfeiler-Leman methods respectively. We extend our combinatorial characterization of the basic LP to higher levels of the Sherali-Adams hierarchy, and we generalize a well-known logical characterization of the Weisfeiler-Leman test from graphs to relational structures.
Open AccessThe Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
In this paper we study the interactions between so-called fractional relaxations of the integer programs (IPs) which encode homomorphism and isomorphism of relational structures. We give a combinatorial characterization of a certain natural linear programming (LP) relaxation of homomorphism in terms of fractional isomorphism. As a result, we show that the families of constraint satisfaction problems (CSPs) that are solvable by such linear program are precisely those that are closed under an equivalence relation which we call Weisfeiler-Leman invariance. We also generalize this result to the much broader framework of Promise Valued Constraint Satisfaction Problems, which brings together two well-studied extensions of the CSP framework. Finally, we consider the hierarchies of increasingly tighter relaxations of the homomorphism and isomorphism IPs obtained by applying the Sherali-Adams and Weisfeiler-Leman methods respectively. We extend our combinatorial characterization of the basic LP to higher levels of the Sherali-Adams hierarchy, and we generalize a well-known logical characterization of the Weisfeiler-Leman test from graphs to relational structures.
- Open Access
- 18 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 89-98
Extremal Fitting Problems for Conjunctive Queries
The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not unique. This leads us to proposing natural refinements of the notion of a fitting CQ, such as most-general fitting CQ, most-specific fitting CQ, and unique fitting CQ. We give structural characterizations of these notions in terms of (suitable refinements of) homomorphism dualities, frontiers, and direct products, which enable the construction of the refined fitting CQs when they exist. We also pinpoint the complexity of the associated existence and verification problems, and determine the size of fitting CQs. We study the same problems for UCQs and for the more restricted class of tree CQs.
- 18 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 89-98
Open AccessExtremal Fitting Problems for Conjunctive Queries
The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not unique. This leads us to proposing natural refinements of the notion of a fitting CQ, such as most-general fitting CQ, most-specific fitting CQ, and unique fitting CQ. We give structural characterizations of these notions in terms of (suitable refinements of) homomorphism dualities, frontiers, and direct products, which enable the construction of the refined fitting CQs when they exist. We also pinpoint the complexity of the associated existence and verification problems, and determine the size of fitting CQs. We study the same problems for UCQs and for the more restricted class of tree CQs.
- Open Access
- 6 November 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 47 (4) , 1-41
Conjunctive Queries: Unique Characterizations and Exact Learnability
We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts.
- 6 November 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 47 (4) , 1-41
Open AccessConjunctive Queries: Unique Characterizations and Exact Learnability
We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts.
- Open Access
- 8 July 2022
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (4) , 838-867
The Complexity of the Distributed Constraint Satisfaction Problem
We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template’s invariance under certain operations. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes’ neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP.
- 8 July 2022
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (4) , 838-867
Open AccessThe Complexity of the Distributed Constraint Satisfaction Problem
We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template’s invariance under certain operations. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes’ neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP.
- Open Access
Dismantlability, connectedness, and mixing in relational structures
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved---like, for example, dismantlability---and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Brice\~no. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif.
Open AccessDismantlability, connectedness, and mixing in relational structures
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved---like, for example, dismantlability---and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Brice\~no. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif.