We study the 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) ? 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 \ne W) 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.
|Cite as: Samer, M. and Szeider, S. (2008). Tractable Cases of the Extended Global Cardinality Constraint. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds. ACS. 67-74. |
(local if available)