5.349. uses

DESCRIPTIONLINKSGRAPH
Origin

[BessiereHebrardHnichKiziltanWalsh05IJCAI]

Constraint

𝚞𝚜𝚎𝚜(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2)

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš–πš’πš—(1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|)β‰₯πš–πš’πš—(1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
Purpose

The set of values assigned to the variables of the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 is included within the set of values assigned to the variables of the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.

Example
3,3,4,6,3,4,4,4,4

The 𝚞𝚜𝚎𝚜 constraint holds since the set of values {3,4} assigned to the items of collection 〈3,4,4,4,4βŒͺ is included within the set of values {3,4,6} occurring within 〈3,3,4,6βŒͺ.

Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 are permutable.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are permutable.

  • All occurrences of two distinct values in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be swapped; all occurrences of a value in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› 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

generalisation: πšŒπš˜πš–πš–πš˜πš—.

implied by: 𝚞𝚜𝚎𝚍_πš‹πš’.

related: πš›πš˜πš˜πšπšœ.

Keywords

complexity: 3-SAT.

constraint arguments: constraint between two collections of variables.

final graph structure: acyclic, bipartite, no loop.

modelling: inclusion.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|

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
ctrs/usesA
(a)
ctrs/usesB
(b)