Building tractable disjunctive constraints

ABSTRACT

Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.

REFERENCES

• 1: ASPVALL, B., PLASS, M., AND TARJAN, R. 1979. A linear time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Proc. Lett. 8, 121-123.
• 2: Elisa Bertino , Claudio Bettini , Elena Ferrari , Pierangela Samarati, An access control model supporting periodicity constraints and temporal reasoning, ACM Transactions on Database Systems (TODS), v.23 n.3, p.231-285, Sept. 1998 [doi>10.1145/293910.293151]
• 3: V. Chandru , J. N. Hooker, Extended Horn sets in propositional logic, Journal of the ACM (JACM), v.38 n.1, p.205-221, Jan. 1991 [doi>10.1145/102782.102789]
• 4: COHEN, D., JEAVONS, P., AND KOUBARAKIS, M. 1997. Tractable disjunctive constraints. In Proceedings of the 3rd International Conference on Constraint Programming:CP'97 (Linz, Austria, October). Lecture Notes in Computer Science, vol. 1330. Springer-Verlag, New York, pp. 478-490.
• 5: Martin C. Cooper , David A. Cohen , Peter G. Jeavons, Characterising tractable constraints, Artificial Intelligence, v.65 n.2, p.347-361, Feb. 1994 [doi>10.1016/0004-3702(94)90021-3]
• 6: Rina Dechter , Judea Pearl, Tree clustering for constraint networks (research note), Artificial Intelligence, v.38 n.3, p.353-366, April 1989 [doi>10.1016/0004-3702(89)90037-4]
• 7: DENENBERG, H., AND LEWIS, H. R. 1984. The complexity of the satisfiability problem for Krom formulas. Theoret. Comput. Sci. 30, 319-341.
• 8: DEVILLE, Y., BARETTE, O., AND VAN HENTENRYCK, P. 1997. Constraint satisfaction over connected row convex constraints. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI'97). pp. 405-411.
• 9: DRAKENGREN, T. 1997. Algorithms and Complexity for Temporal and Spatial Formalisms. Ph.D. dissertation. Dept. of Computer and Information Science, Linko~ping University. Available from http://www.ida.liu.se/ext/pur/tphd/0498.html.
• 10: DRAKENGREN, T., AND JONSSON, P. 1997. Qualitative reasoning about sets applied to spatial reasoning. (Paper #7 in {Drakengren 1997}).
• 11: DRAKENGREN, T., AND JONSSON, P. 1998. Reasoning about set constraints applied to tractable inference in intuitionistic logic. J. Logic Comput. 8, 855-875.
• 12: Eugene C. Freuder, A sufficient condition for backtrack-bounded search, Journal of the ACM (JACM), v.32 n.4, p.755-761, Oct. 1985 [doi>10.1145/4221.4225]
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: Marc Gyssens , Peter G. Jeavons , David A. Cohen, Decomposing constraint satisfaction problems using database techniques, Artificial Intelligence, v.66 n.1, p.57-89, March 1994 [doi>10.1016/0004-3702(94)90003-5]
• 15: JACKSON, T. 1975. Number Theory. Routledge and Kegan Paul.
• 16: Peter Jeavons , David Cohen , Martin C. Cooper, Constraints, consistency and closure, Artificial Intelligence, v.101 n.1-2, p.251-265, May 1998 [doi>10.1016/S0004-3702(98)00022-8]
• 17: Peter Jeavons , David Cohen , Marc Gyssens, A Unifying Framework for Tractable Constraints, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.276-291, September 19-22, 1995
• 18: Peter Jeavons , David Cohen , Marc Gyssens, Closure properties of constraints, Journal of the ACM (JACM), v.44 n.4, p.527-548, July 1997 [doi>10.1145/263867.263489]
• 19: Peter G. Jeavons , Martin C. Cooper, Tractable constraints on ordered domains, Artificial Intelligence, v.79 n.2, p.327-339, Dec. 1995 [doi>10.1016/0004-3702(95)00107-7]
• 20: Peter Jonsson , Christer Bäckström, A unifying approach to temporal constraint reasoning, Artificial Intelligence, v.102 n.1, p.143-155, June 1998 [doi>10.1016/S0004-3702(98)00031-9]
• 21: F. Kabanza , J.-M. Stévenne , P. Wolper, Handling infinite temporal data, Journal of Computer and System Sciences, v.51 n.1, p.3-17, Aug. 1995
• 22: KHACHIAN, L. 1979. A polynomial time algorithm for linear programming. Soviet Math. Dokl. 20, 191-194.
• 23: Lefteris M. Kirousis, Fast parallel constraint satisfaction, Artificial Intelligence, v.64 n.1, p.147-160, Nov. 1993 [doi>10.1016/0004-3702(93)90063-H]
• 24: KOUBARAKIS, M. 1992. Dense time and temporal constraints with ~. In Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference (KR'92) (San Mateo, Calif.), B. Nebel, C. Rich, and W. Swartout, eds., Morgan-Kaufmann, San Francisco, Calif., pp. 24-35.
• 25: Manolis Koubarakis, From Local to Global Consistency in Temporal Constraint Networks, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.53-69, September 19-22, 1995
• 26: KOUBARAKIS, M. 1996. Tractable disjunctions of linear constraints. In Proceedings of the 2nd International Conference on Constraint Programming:CP'96 (Boston, Mass., Aug.). Lecture Notes in Computer Science, vol. 1118. Springer-Verlag, New York, pp. 297-307.
• 27: Jean-Louis Lassez , Ken McAloon, Independence of Negative Constraints, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 1: Advanced Seminar on Foundations of Innovative Software Development I and Colloquium on Trees in Algebra and Programming, p.19-27, March 13-17, 1989
• 28: Jean-Louis Lassez , Ken McAloon, A constraint sequent calculus, Constraint logic programming: selected research, MIT Press, Cambridge, MA, 1993
• 29: Jean-Louis Lassez , Ken McAloon, A canonical form for generalized linear constraints, Journal of Symbolic Computation, v.13 n.1, p.1-24, Jan. 1992 [doi>10.1016/0747-7171(92)90002-L]
• 30: D. Lesaint , N. Azarmi , R. Laithwaite , P. Walker, Engineering Dynamic Scheduler for Work Manager, BT Technology Journal, v.16 n.3, p.16-29, July 1998 [doi>10.1023/A:1009609327253]
• 31: MACKWORTH, A. 1977. Consistency in networks of relations. Artif. Int. 8, 99-118.
• 32: MONTANARI, U. 1974. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci. 7, 95-132.
• 33: Bernhard Nebel , Hans-Jürgen Bürckert, Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra, Journal of the ACM (JACM), v.42 n.1, p.43-66, Jan. 1995 [doi>10.1145/200836.200848]
• 34: PURVIS, L., AND JEAVONS, P. 1999. Constraint tractability theory and its application to the product development process for a constraint-based scheduler. In Proceedings of the 1st International Conference on the Practical Applications of Constraint Technologies and Logic Programming -PACLP'99. pp. 63-79.
• 35: Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
• 36: Peter van Beek , Rina Dechter, On the minimality and global consistency of row-convex constraint networks, Journal of the ACM (JACM), v.42 n.3, p.543-561, May 1995 [doi>10.1145/210346.210347]
• 37: Pascal Van Hentenryck , Yves Deville , Choh-Man Teng, A generic arc-consistency algorithm and its specializations, Artificial Intelligence, v.57 n.2-3, p.291-321, Oct. 1992 [doi>10.1016/0004-3702(92)90020-X]
• 38: Marc Vilain , Henry Kautz , Peter van Beek, Constraint propagation algorithms for temporal reasoning: a revised report, Readings in qualitative reasoning about physical systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 39: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Relation systems

General Terms:
Algorithms, Theory

Keywords:
NP-completeness, complexity, constraint satisfaction problem, disjunctive constraints, independence, relations