5.349. uses
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
The set of values assigned to the variables of the collection of variables is included within the set of values assigned to the variables of the collection of variables .
- Example
-
The constraint holds since the set of values assigned to the items of collection is included within the set of values occurring within .
- Symmetries
Items of are permutable.
Items of are permutable.
All occurrences of two distinct values in or can be swapped; all occurrences of a value in or can be renamed to any unused value.
- Remark
It was shown inΒ [BessiereHebrardHnichKiziltanWalsh05IJCAI] that, finding out whether a constraint has a solution or not is NP-hard. This was achieved by reduction from 3-SAT.
- See also
-
related: .
- Keywords
-
constraint arguments: constraint between two collections of variables.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph class
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.349.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, the sink vertices of the final graph are stressed with a double circle. Note that all the vertices corresponding to the variables that take values 9 or 2 were removed from the final graph since there is no arc for which the associated equality constraint holds.
Figure 5.349.1. Initial and final graph of the constraint
(a) 
(b)