6 citations · 6 across the 4 of their papers we have counts for
4 papers · 1 filter
The complexity of Boolean surjective general-valued CSPs
Peter Fulla, Hannes Uppman, Stanislav Zivny
Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a -valued objective function given as a sum of fixed-arity funct…
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
Peter Jonsson, Victor Lagerkvist, Johannes Schmidt +1
Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the…
Computational Complexity of the Minimum Cost Homomorphism Problem on Three-Element Domains
Hannes Uppman
In this paper we study the computational complexity of the (extended) minimum cost homomorphism problem (Min-Cost-Hom) as a function of a constraint language, i.e. a set of constra…
Three-Element Min-Sol and Conservative Min-Cost-Hom
Hannes Uppman
Thapper and Zivny [STOC'13] recently classified the complexity of VCSP for all finite-valued constraint languages. However, the complexity of VCSPs for constraint languages that ar…