caa a22 4500 445879203 CHVBK 20180317145537.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s10601-009-9079-y doi (NATIONALLICENCE)springer-10.1007/s10601-009-9079-y Tractable cases of the extended global cardinality constraint [Elektronische Daten] [Marko Samer, Stefan Szeider] We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a setX of variables, a setD of values, a domain$D(x) \subseteq D$ for each variablex, and a "cardinality set”K(d) of non-negative integers for each valued. The problem is to instantiate each variablex with a value inD(x) such that for each valued, the number of variables instantiated withd belongs to the cardinality setK(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. Springer Science+Business Media, LLC, 2009 Global constraints nationallicence General factor problem nationallicence Domain consistency nationallicence Bounded treewidth nationallicence Parameterized complexity nationallicence Samer Marko Department of Computer Science, TU Darmstadt, Darmstadt, Germany aut Szeider Stefan Department of Computer Science, Durham University, Durham, UK aut Constraints Springer US; http://www.springer-ny.com 16/1(2011-01-01), 1-24 1383-7133 16:1<1 2011 16 10601 https://doi.org/10.1007/s10601-009-9079-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10601-009-9079-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Samer Marko Department of Computer Science, TU Darmstadt, Darmstadt, Germany aut NATIONALLICENCE 700 1- Szeider Stefan Department of Computer Science, Durham University, Durham, UK aut NATIONALLICENCE 773 0- Constraints Springer US; http://www.springer-ny.com 16/1(2011-01-01), 1-24 1383-7133 16:1<1 2011 16 10601 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer