4
$\begingroup$

Suppose I have $k$ sets with $n$ elements in each. Define a selection as one element taken from each set.

A selection is unique if there's one and only one way it can happen—that is, one and only one mapping from the elements in the selection back onto the original sets. For example, if my sets are $\{1,2,3\}$ and $\{1,2,4\}$, then $(1,2)$ and $(1,3)$ are both valid selections, but only the second one is unique.

I'd like to find the number of unique selections, given a list of sets. But my first attempt is $O(n^k)$, which is pretty bad. (Generate all $n^k$ possible selections, then discard all duplicates, and count how many are left.)

Is it possible to do better than this? If so, how?

(If it simplifies things, you can assume the order of elements in a selection either does or does not matter. To switch from one "version" to the other, just multiply or divide by $k!$ at the end; no unique selection can contain two identical elements, after all.)

$\endgroup$
1
  • $\begingroup$ Is the problem to determine whether there exists one unique selection in P? If in P, is it NP-complete? $\endgroup$
    – John L.
    Jun 11, 2019 at 17:38

2 Answers 2

1
$\begingroup$

We will use the following method to efficiently solve your problem for the case $k = 2$ :

We will firstly compute: $$ \begin{array}{rl} S & := A \, \Delta \, B \\ & = (A \setminus B) \cup (B \setminus A) \\ & = (A \cup B) \setminus (A \cap B) \end{array} $$ i.e. the symmetric difference of $A$ and $B$ . Then, we have the following cases:

  • $card(S) = 0$ - There is no unique selection.
  • $card(S) > 0$ - There are unique selections. Let: $$\begin{array}{rl} x & := A \cap B \end{array}$$ and $$\begin{array}{rl} a & := S \cap A \\ & = A \setminus x \end{array}$$ and $$\begin{array}{rl} b & := S \cap B \\ & = B \setminus x \end{array}$$ Then, the unique selections are the elements of the set: $$ T := \Big( \big(a \times B \big) \cup \big(b \times A \big) \Big) \setminus \big( a \times b \big) $$ Since you are interested in the number of unique selections, you just have to calculate $card(T)$ .

You may find this article on symmetric difference useful, since it adapts your initial algorithm idea and makes it more efficient, at least for the case $k = 2$ (the new algorithm yields a worst-case time complexity of $O(m + n)$ for the symmetric difference of two arrays, with their respective lengths $n$ and $m$, where $n \le m$, instead of $O(n^2)$).

Best regards!

$\endgroup$
1
$\begingroup$

Partial answer: it is NP-hard to find a maximum-cardinality partial unique selection, at least if the condition "every set contains the same number of elements" is dropped.

Consider the problem in terms of bipartite graphs. As observed, selections with duplicated elements are not unique. Therefore, a selection corresponds to a bipartite matching (that uses all of the "set" vertices).

It turns out that a partial unique selection corresponds to an alternating cycle-free matching defined as [1]:

For a matching, a simple cycle is alternating if every other edge is in the matching. A matching is alternating cycle-free if the graph has no alternating cycle.

To see the equivalence, notice that the selection is not unique if and only if there exists a non-identity permutation of the used sets that retains the matching. Any non-identity cyclic component of that permutation corresponds to an alternating cycle.

Müller proved the maximum-cardinality alternating cycle-free matching problem in bipartite graphs is NP-hard [1]. However, it is not immediately clear how to reduce the maximizing problem to the problem of using all vertices of one side.

  • [1]: Müller, H. (1990). Alternating cycle-free matchings. Order, 7(1), 11-21.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.