Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with constraint satisfaction problem:
TR02-032 | 17th April 2002
Andrei Bulatov

Tractable Constraint Satisfaction Problems on a 3-element set

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate ... more >>>

TR02-034 | 18th April 2002
Andrei Bulatov

Mal'tsev constraints are tractable

A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of ... more >>>

TR06-121 | 14th September 2006
Charanjit Jutla

A Simple Biased Distribution for Dinur's Construction

TR06-141 | 22nd November 2006
Venkatesan Guruswami, Kunal Talwar

Hardness of Low Congestion Routing in Directed Graphs

We prove a strong inapproximability result for routing on directed
graphs with low congestion. Given as input a directed graph on $N$
vertices and a set of source-destination pairs that can be connected
via edge-disjoint paths, we prove that it is hard, assuming NP
doesn't have $n^{O(\log\log n)}$ time randomized ... more >>>

TR07-093 | 27th July 2007
Andrei A. Bulatov

The complexity of the counting constraint satisfaction problem

Revisions: 1

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite
relational structure H can be expressed as follows: given a
relational structure G over the same vocabulary,
determine the number of homomorphisms from G to H.
In this paper we characterize relational structures H for which
#CSP(H) can be solved in ... more >>>

TR11-163 | 2nd December 2011
Libor Barto, Marcin Kozik

Robust Satisfiability of Constraint Satisfaction Problems

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least $(1-g(\varepsilon))$-fraction of the constraints given a $(1-\varepsilon)$-satisfiable instance, where $g(\varepsilon) \rightarrow 0$ as $\varepsilon \rightarrow 0$, $g(0)=0$.
Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction ... more >>>

TR13-125 | 11th September 2013
Venkatesan Guruswami, Euiwoong Lee

Complexity of approximating CSP with Balance / Hard Constraints

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>

TR19-040 | 19th February 2019
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

The Complexity of Finding {$S$}-factors in Regular Graphs

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.
The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ... more >>>

TR21-086 | 22nd June 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

Linear Space Streaming Lower Bounds for Approximating CSPs

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>

ISSN 1433-8092 | Imprint