Determine bijective mapping using minimal number of lookups in subset mapping - standard problem / perspectives?

Question

This seems like it should be a "textbook"/standard problem but I wasn't able to find anything about it, so I'd like to know if anyone else has seen something like it before or can suggest more keywords I could search for / perspectives I could view it from:

Informal problem statement

Informally, the situation is that we have a bunch of input values and an unknown (to us) mapping we want to determine which maps them to output values. We can gain information on the mapping by calling a fairly expensive query/lookup function with one or multiple input values and it will return the corresponding output values in a random order (so we don't know which given input corresponds to which output unless we called it with only one input). The task is to come up with an algorithm that completely determines the mapping using the least number of calls to the query/lookup function.

Formal problem statement

So, formally, we have an input set $X = \{ x_1, …, x_n \}$ and an output set $Y = \{ y_1, …, y_n \}$. There is an unknown bijective mapping $f: X \rightarrow Y$ between them that we want to determine by making as few calls to a function $q: \mathcal{P}(X) \rightarrow \mathcal{P}(Y); \ \{ x_i, x_j, … \} \mapsto \{ f(x_i), f(x_j), … \}$ as possible, where $\mathcal{P}(S)$ denotes the power set (set of all subsets) of $S$.

Question

I already have a fairly naive algorithm for it based on the idea that we can find out a part of the mapping whenever a single value is shared between two input sets that the query function was called with, because then we can find the corresponding output value by looking at which value appears in both query function results. By developing this a bit further, e.g. a 38-element mapping can be fully determined with only 11 calls.

But as I wrote at the beginning, my question is really if this is some kind of standard problem or if there are any perspectives I could view it from to reduce it to one.

Answer 1

An algorithm

I have never seen this problem before, but I can suggest a randomized algorithm for this problem.

• Create a bipartite graph, with left vertices $X$ and right vertices $Y$, and initially containing all edges $X \times Y$.

• Repeat the following until the algorithm terminates:

  • Pick a random set $S$ of $n/2$ values from $X$. Query $S$, to learn the set $F(S)$.

  • For each $x \in S$ and each $y \notin F(S)$, remove the edge $(x,y)$ from the graph. For each $x \notin S$ and each $y \in F(S)$, remove the edge $(x,y)$.

  • Run a bipartite matching algorithm on this bipartite graph. If the graph has only a single perfect matching, output it as the mapping and terminate. Otherwise, continue on to the next iteration. [An alternate version of this step: If each vertex has degree 1, i.e., maps to exactly one other vertex, then output the mapping given by this graph and terminate; otherwise continue on to the next iteration.]

Correctness

Hopefully it is clear why this algorithm is correct, i.e., if it terminates, then it outputs the correct solution.

Running time

How efficient is this algorithm? I argue that the number of iterations of the loop is $O(\log n)$. It follows that the number of queries to the lookup function is $O(\log n)$. Why? Well, consider a single $x \in X$, and a $y \in Y$ such that $y \ne f(x)$. Thanks to the random choice of $S$, $\Pr[x \in S] \approx 1/2$, and of those, $\Pr[y \notin F(S)] \approx 1/2$, so after one iteration, the probability that the edge $(x,y)$ remains in the graph is about $3/4$; and this probability drops to $(3/4)^r$ after $r$ repetitions of the loop. In particular, after $r = 4.8 \lg n + 2.4 c$ repetitions, then the probability that $(x,y)$ remains is about $2^{-2\lg n - c} \approx 2^{-c}/n^2$. Using a union bound and summing over all $y \in Y \setminus \{f(x)\}$, we find that the probability that $x$ has an edge to any vertex other than $f(x)$ is at most $2^{-c}/n$. Using a union bound again and summing over all $x \in X$, we find that the probability that the graph has any edge other than $\{(x,f(x)) \mid x \in X\}$ is at most about $2^{-c}$.

In short, after $4.8 \lg n + 2.4 c$ queries to the lookup function, this will almost surely terminate with the correct solution: the probability it doesn't is at most $2^{-c}$, i.e., exponentially small. Most of the time, it will terminate within about $4.8 \lg n$ repetitions.

Optimality

Could there be a better algorithm? It's possible, but I have an information-theoretic heuristic which suggests to me that this is approximately optimal. In particular, if we query the lookup function with a set of size $k$, then out of the $n!$ possible mappings, only $k! (n-k)!$ will remain consistent with the output of the lookup function. Therefore, the result from this query can be expected to give us about $\lg(n!) - \lg(k! (n-k)!)$ bits of information. This is $\lg {n \choose k}$. Heuristically, it seems natural to choose $k$ to maximize the number of bits of information provided by the oracle. The value of $k$ that maximizes ${n \choose k}$ is $k=n/2$, and then

$$\lg {n \choose k} = \lg {n \choose n/2} \approx n - 0.5 \lg n + 1.$$

So each query can provide at most about $n$ bits of information. Moreover, there are $n!$ mappings, so it requires $\lg(n!)$ bits of information to specify a mapping; since $\lg(n!) \approx n \log n -n + O(\log n)$, it follows that we need at least about $\log n - 1$ queries to uniquely recover the mapping. So the algorithm above should be close to optimal.