这是indexloc提供的服务，不要输入任何密码
Skip to main content
Springer Nature Link
Log in

Tractable cases of the extended global cardinality constraint

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain \(D(x) \subseteq D\) for each variable x, and a “cardinality set” K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption  FPT ≠ W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Beldiceanu, N., Carlsson, M. & Rampon, J.-X. (2005). Global constraint catalog. Technical Report T2005:08, Swedish Institute of Computer Science, Stockholm, Sweden.

  2. Bessiére, C., Hebrard, E., Hnich, B., & Walsh, T. (2004). The tractability of global constraints. In Proceedings of the 10th international conference on principles and practice of constraint programming (CP’04), LNCS (Vol. 3258, pp. 716–720). New York: Springer.

    Google Scholar 

  3. Bessiére, C., Hebrard, E., Hnich, B., Kiziltan, Z., Quimper, C.-G., & Walsh, T. (2008). The parameterized complexity of global constraints. In Proceedings of the 23rd AAAI conference on artificial intelligence (AAAI’08) (pp. 235–240). Menlo Park: AAAI.

    Google Scholar 

  4. Bodlaender, H. L. (1993). A tourist guide through treewidth. Acta Cybernetica, 11(1–2), 1–22.

    MATH  MathSciNet  Google Scholar 

  5. Bodlaender, H. L. (1996). A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6), 1305–1317.

    Article  MATH  MathSciNet  Google Scholar 

  6. Bodlaender, H. L. (2005). Discovering treewidth. In Proceedings of the 31st conference on current trends in theory and practice of computer science (SOFSEM’05), LNCS (Vol. 3381, pp. 1–16). New York: Springer.

    Google Scholar 

  7. Bourdais, S., Galinier, P., & Pesant, G. (2003). HIBISCUS: A constraint programming application to staff scheduling in health care. In Proceedings of the 9th international conference on principles and practice of constraint programming (CP’03), LNCS (Vol. 2833, pp. 153–167). New York: Springer.

    Google Scholar 

  8. Caseau, Y., Guillo, P.-Y., & Levenez, E. (1995). A deductive and object-oriented approach to a complex scheduling problem. Journal of Intelligent Information Systems, 4(2), 149–166.

    Article  Google Scholar 

  9. Cohen, D., & Jeavons, P. (2006). The complexity of constraint languages. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (chapter 8, pp. 245–280). Amsterdam: Elsevier.

    Chapter  Google Scholar 

  10. Cornuéjols, G. (1988). General factors of graphs. Journal of Combinatorial Theory, Series B, 45(2), 185–198.

    Article  MATH  MathSciNet  Google Scholar 

  11. Cornuéjols, G., Hartvigsen, D., & Pulleyblank, W. (1982). Packing subgraphs in a graph. Operations Research Letters, 1, 139–143.

    Article  MATH  Google Scholar 

  12. Courcelle, B. (1990). Graph rewriting: An algebraic and logic approach. In J. van Leeuwen (Ed.), Handbook of theoretical computer science: Formal models and semantics (Vol. B, chapter 5, pp. 193–242). Amsterdam: Elsevier.

    Google Scholar 

  13. Dechter, R. (2006). Tractable structures for constraint satisfaction problems. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (chapter 7, pp. 209–244). Amsterdam: Elsevier.

    Chapter  Google Scholar 

  14. Downey, R. G., & Fellows, M. R. (1999). Parameterized complexity. New York: Springer.

    Google Scholar 

  15. Flum, J., & Grohe, M. (2006). Parameterized complexity theory. New York: Springer.

    Google Scholar 

  16. Gottlob, G., & Pichler, R., & Wei, F. (2006). Bounded treewidth as a key to tractability of knowledge representation and reasoning. In Proceedings of the 21st AAAI conference on artificial intelligence (AAAI’06) (pp. 250–256). Menlo Park: AAAI.

    Google Scholar 

  17. van Hoeve, W.-J., & Katriel I. (2006). Global constraints. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (chapter 6, pp. 169–208). Amsterdam: Elsevier.

    Google Scholar 

  18. Kloks, T. (1994). Treewidth: Computations and approximations. New York: Springer.

    MATH  Google Scholar 

  19. Koster, A. M. C. A., Bodlaender, H. L., & van Hoesel, S. P. M. (2001). Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics, 8, 54–57.

    Article  Google Scholar 

  20. Lovász, L. (1970). The factorization of graphs. In Combinatorial structures and their applications (pp. 243–246). New York: Gordon and Breach.

    Google Scholar 

  21. Lovász, L. (1972). The factorization of graphs II. Acta Mathematica Academiae Scientiarum Hungaricae, 23, 223–246.

    Article  MATH  MathSciNet  Google Scholar 

  22. Micali, S., & Vazirani, V. V. (1980). An \({O}(\sqrt{|{V}|}\cdot |{E}|)\) algorithm for finding a maximum matching in general graphs. In Proceedings of the 21st annual IEEE symposium on foundations of computer science (SFCS’80) (pp. 17–27). IEEE Computer Society.

  23. Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press.

    Book  MATH  Google Scholar 

  24. Pietrzak, K. (2003). On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences, 67(4), 757–771.

    Article  MATH  MathSciNet  Google Scholar 

  25. Quimper, C.-G., López-Ortiz, A., van Beek, P., & Golynski, A. (2004). Improved algorithms for the global cardinality constraint. In Proceedings of the 10th international conference on principles and practice of constraint programming (CP’04), LNCS (Vol. 3258, pp. 542–556). New York: Springer.

    Google Scholar 

  26. Régin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings of the 13th AAAI conference on artificial intelligence (AAAI’96) (pp. 209–215). Menlo Park: AAAI.

    Google Scholar 

  27. Régin, J.-C., & Gomes, C. P. (2004). The cardinality matrix constraint. In Proceedings of the 10th international conference on principles and practice of constraint programming (CP’04), LNCS (Vol. 3258, pp. 572–587). New York: Springer.

    Google Scholar 

  28. Rossi, F., van Beek, P., & Walsh, T. (Eds.) (2006). Handbook of constraint programming. Amsterdam: Elsevier.

    MATH  Google Scholar 

  29. Samer, M., & Szeider, S. (2008). Tractable cases of the extended global cardinality constraint. In Proceedings of the 14th computing: The Australasian theory symposium (CATS’08), Theory of Computing 2008, CRPIT (Vol. 77, pp. 67–74). Canberra: Australian Computer Society.

    Google Scholar 

  30. Sellmann, M., Gellermann, T., & Wright, R. (2007). Cost-based filtering for shorter path constraints. Constraints, 12(2), 207–238.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, TU Darmstadt, Darmstadt, Germany

    Marko Samer

  2. Department of Computer Science, Durham University, Durham, UK

    Stefan Szeider

Authors
  1. Marko Samer
    View author publications

    Search author on:PubMed Google Scholar

  2. Stefan Szeider
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Marko Samer.

Additional information

Preliminary version published in the Proceedings of the 14th Computing:

The Australasian Theory Symposium (CATS’08) [29].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Samer, M., Szeider, S. Tractable cases of the extended global cardinality constraint. Constraints 16, 1–24 (2011). https://doi.org/10.1007/s10601-009-9079-y

Download citation

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s10601-009-9079-y

Keywords