Fast parallel constraint satisfaction

Lefteris M. Kirousis

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A Constraint Satisfaction Problem (CSP) involves searching for an assignment of values to a given set of variables so that the values assigned satisfy a given set of constraints. The general CSP is NP-complete. To confront the intractability of the general CSP, relaxation procedures have been devised: instead of searching for a globally consistent assignment of values to the variables, try to restrict the domain of values of each variable in a way that ensures local consistency only. The relaxation procedures are efficient, but have been proved to be inherently sequential. In this paper, we define a class of CSPs for which a global solution can be found by a fast parallel algorithm. No relaxation preprocessing is needed for the parallel algorithm to work. The result is motivated from the problem of labelling a 2-D line drawing of a 3-D object by the Clowes-Huffman-Malik labelling scheme--an important application of CSP in computer vision. For such a labelling CSP, the constraint graph can be general, but the constraint relations are usually of the type we call implicational. It is shown here that a CSP with this type of constraint relations (and no restrictions on its graph) can be solved by an efficient (i.e., with polynomial time complexity) sequential algorithm. Also, it is shown that it can be solved by a fast parallel algorithm that executes in time O(log3n) with O((m + n3)/logn) processors on a Exlusive-Read-Exclusive-Write Parallel Random Access Machine (n is the number of variables and m is the number of constrain relations-the constraint relations may have arity more than two).

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings
EditorsAndrzej Lingas, Rolf Karlsson, Svante Carlsson
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540569398
StatePublished - 1993
Event20th International Colloquium on Automata, Languages and Programming, ICALP 1993 - Lund, Sweden
Duration: Jul 5 1993Jul 9 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume700 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Colloquium on Automata, Languages and Programming, ICALP 1993

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Fast parallel constraint satisfaction'. Together they form a unique fingerprint.

Cite this