Partial arc consistency

Nick D. Dendris, Lefteris M. Kirousis, Yannis C. Stamatiou, Dimitris M. Thilikos

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


A constraint network is arc consistent if any value of its variables is compatible with at least one value of any other variable. Enforcing arc consistency in a constraint network is a commonly used preprocessing step before identifying the globally consistent value assignments to all the variables. Since many constraint networks that arise in practice are overconstrained, any global assignment of values to the variables involved, is expected to include constraint violations. Therefore, it is often necessary to enforce some weak form of consistency, to avoid excessive value elimination due to the existence of many constraints. It is also necessary that this form of consistency be enforced fast. In this paper, we introduce a notion of weak local consistency that we call partial arc consistency. We then give an algorithm that, for any constraint network of n variables, outputs a partially arc consistent subnetwork of it in sublinear (0(√nlog n)) parallel time using 0(n2) processors. This algorithm removes at least a constant fraction of the local inconsistencies of a general constraint network, without eliminating any globally consistent assignment of values. To our knoweldge, it is the first sublinear-time parallel algorithm with polynomially many processors that achieves this extent of local consistency. Moreover, we propose several approximation schemes to a total solution of the arc consistency problem. We show that these approximation schemes are inherently sequential (more formally, they are P-complete), a fact indicating that the approach of partial solutions, rather than that of approximation schemes, is more promising for parallelism.

Original languageEnglish (US)
Title of host publicationOver-Constrained Systems
EditorsMichael Jampel, Eugene Freuder, Michael Maher
PublisherSpringer Verlag
Number of pages8
ISBN (Print)3540614796, 9783540614791
StatePublished - 1996
EventWorkshop on Over-Constrained Systems, held as part of 1st International Conference on Principles and Practice of Constraint Programming, CP 1995 - Marseilles, France
Duration: Sep 18 1995Sep 18 1995

Publication series

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


ConferenceWorkshop on Over-Constrained Systems, held as part of 1st International Conference on Principles and Practice of Constraint Programming, CP 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Partial arc consistency'. Together they form a unique fingerprint.

Cite this