Author name cluster

Johan Thapper

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

TCS Journal 2018 Journal Article

Tractability conditions for numeric CSPs

Peter Jonsson
Johan Thapper

The computational complexity of the constraint satisfaction problem (CSP) with semilinear relations over the reals has gained recent attraction. As a result, its complexity is known for all finite sets of semilinear relations containing the relation R + = { ( x, y, z ) ∈ R 3 | x + y = z }. We consider larger and more expressive classes of relations such as semialgebraic and o-minimal relations. We present a general result for characterising computationally hard fragments and, under certain side conditions, this result implies that polynomial-time solvable fragments are only to be found within two limited families of sets of relations. In the setting of semialgebraic relation, our result takes on a simplified form and we provide a full complexity classification for constraint languages that consist of algebraic varieties. Full classifications like the one obtained here for algebraic varieties or the one for semilinear relations appear to be rare and we discuss several barriers for obtaining further such results. These barriers have strong connections with well-known open problems concerning the complexity of various restrictions of convex programming.

Details DOI

STOC Conference 2013 Conference Paper

The complexity of finite-valued CSPs

Johan Thapper
Stanislav Zivný

Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language . The valued constraint satisfaction problem, VCSP(Γ), is the problem of minimising a function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exact solvability for all finite-valued languages defined on domains of arbitrary finite size. We show that every core language Γ either admits a binary idempotent and symmetric fractional polymorphism in which case the basic linear programming relaxation solves any instance of VCSP(Γ) exactly, or Γ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(Γ). In other words, there is a single algorithm for all tractable cases and a single reason for intractability. Our results show that for exact solvability of VCSPs the basic linear programming relaxation suffices and semidefinite relaxations do not add any power. Our results generalise all previous partial classifications of finite-valued languages: the classification of {0,1}-valued languages containing all unary functions obtained by Deineko et al. [JACM'06]; the classifications of {0,1}-valued languages on two-element, three-element, and four-element domains obtained by Creignou [JCSS'95], Jonsson et al. [SICOMP'06], and Jonsson et al.[CP'11], respectively; the classifications of finite-valued languages on two-element and three-element domains obtained by Cohen et al. [AIJ'06] and Huber et al. [SODA'13], respectively; the classification of finite-valued languages containing all {0,1}-valued unary functions obtained by Kolmogorov and Zivny [JACM'13]; and the classification of Min-0-Ext problems obtained by Hirai [SODA'13].

Details

FOCS Conference 2012 Conference Paper

The Power of Linear Programming for Valued CSPs

Johan Thapper
Stanislav Zivný

A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs). Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation. Using this result, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) sub modular on arbitrary lattices, (2) bisubmodular (also known as k-sub modular) on arbitrary finite domains, (3) weakly (and hence strongly) tree-sub modular on arbitrary trees.

Details

MFCS Conference 2007 Conference Paper

The Maximum Solution Problem on Graphs

Peter Jonsson
Gustav Nordh
Johan Thapper

Abstract We study the complexity of the problem Max Sol which is a natural optimisation version of the graph homomorphism problem. Given a fixed target graph H with V ( H ) ⊆ ℕ, and a weight function w: V ( G ) →ℚ +, an instance of the problem is a graph G and the goal is to find a homomorphism f: G → H which maximises ∑ v ∈ G f ( v ) · w ( v ). Max Sol can be seen as a restriction of the Min Hom -problem [Gutin et al. , Disc. App. Math. , 154 (2006), pp. 881-889] and as a natural generalisation of Max Ones to larger domains. We present new tools with which we classify the complexity of Max Sol for irreflexive graphs with degree less than or equal to 2 as well as for small graphs (| V ( H )| ≤ 4). We also study an extension of Max Sol where value lists and arbitrary weights are allowed; somewhat surprisingly, this problem is polynomial-time equivalent to Min Hom.

Details