5.349. uses

Origin
Constraint

$\mathrm{𝚞𝚜𝚎𝚜}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right)$

Arguments
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝚖𝚒𝚗}\left(1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|\right)\ge \mathrm{𝚖𝚒𝚗}\left(1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

The set of values assigned to the variables of the collection of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ is included within the set of values assigned to the variables of the collection of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$.

Example
$\left(\begin{array}{c}〈3,3,4,6〉,\hfill \\ 〈3,4,4,4,4〉\hfill \end{array}\right)$

The $\mathrm{𝚞𝚜𝚎𝚜}$ constraint holds since the set of values $\left\{3,4\right\}$ assigned to the items of collection $〈3,4,4,4,4〉$ is included within the set of values $\left\{3,4,6\right\}$ occurring within $〈3,3,4,6〉$.

Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ are permutable.

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ are permutable.

• All occurrences of two distinct values in $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}.\mathrm{𝚟𝚊𝚛}$ or $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$ can be swapped; all occurrences of a value in $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}.\mathrm{𝚟𝚊𝚛}$ or $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$ can be renamed to any unused value.

Remark

It was shown in [BessiereHebrardHnichKiziltanWalsh05IJCAI] that, finding out whether a $\mathrm{𝚞𝚜𝚎𝚜}$ constraint has a solution or not is NP-hard. This was achieved by reduction from 3-SAT.

Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$

Arc generator
$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$
Graph property(ies)
$\mathrm{𝐍𝐒𝐈𝐍𝐊}$$=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$

Graph class
 $•$$\mathrm{𝙰𝙲𝚈𝙲𝙻𝙸𝙲}$ $•$$\mathrm{𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴}$ $•$$\mathrm{𝙽𝙾}_\mathrm{𝙻𝙾𝙾𝙿}$

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 $\mathrm{𝐍𝐒𝐈𝐍𝐊}$ 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.