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 >>>

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 >>>

more >>>

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 >>>

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 >>>