5.174. k_same

Origin

[ElbassioniKatrielKutzMahajan05]

Constraint

k_same​(SETS)​

Type(s)

VARIABLES

collection​(var−dvar)​

Argument(s)

SETS	collection​(set−VARIABLES)​

Restriction(s)

required​(VARIABLES,​var)​

|VARIABLES|>​0

required​(SETS,​set)​

|SETS|>​1

same_size​(SETS,​set)​

Purpose

Given |SETS| sets, each containing the same number of domain variables, the k_same constraint enforces that the multisets of values assigned to each set are all identical.

Example

( 〈 set−〈1,​9,​1,​5,​2,​1〉,​ set−〈9,​1,​1,​1,​2,​5〉,​ set−〈5,​2,​1,​1,​9,​1〉 〉 )

The k_same constraint holds since:

• The first and second collections of variables are assigned to the same multiset.

• The second and third collections of variables are also assigned to the same multiset.

Remark

It was shown in [ElbassioniKatrielKutzMahajan05] that, finding out whether the k_same constraint has a solution or not is NP-hard when we have more than one same constraint. This was achieved by reduction from 3-dimensional-matching in the context where we have 2 same constraints.

See also

same.

Key words

combinatorial object: permutation, multiset.

complexity: 3-dimensional-matching.

constraint type: system of constraints, decomposition.

modelling: equality between multisets.

Arc input(s)

SETS

Arc generator

PATH↦collection​(set1,​set2)​

Arc arity

2

Arc constraint(s)

same​(set1.set,​set2.set)​

Graph property(ies)

NARC=|SETS|−1

---

Graph model

Parts (A) and (B) of Figure 5.174.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a same constraint.

Figure 5.174.1. Initial and final graph of the k_same constraint

(a)	(b)