Let $G=(V,E)$ be a complete bipartite graph with $2n$ vertices and $M \subset E$ some unknown perfect matching of $G$.

The goal is to determine $M$ by repeatedly choosing some perfect matching $M_i \subset E$ and asking for $|M \cap M_i|=m_i$.

Question: What would be a good strategy of choosing the matchings $M_i$ if I want to minimize the times I have to ask?

My first idea was to create a heuristic that assigns to each pair of vertices $(a,b)$ the number $m_{(a,b)}=\max \{m_i \mid (a,b) \in M_i\}$, and maximizing $\sum_{(a,b)} m_{(a,b)}$. The problem is that this algorithm would just choose $M_i = M_1$ everytime, so maybe a certain percentage of the matching $M_i$ should be randomized, I don't know.


1 Answer 1


This is a variant of the Mastermind game, a classical problem of black-box optimization. This problem (reformulated with permutations instead of perfect matchings, but it's exactly the same) is addressed here : https://www.sciencedirect.com/science/article/pii/0196677486900131

They give a polynomial-time algorithm with $O(n \log(n))$ queries, and conjecture that it is optimal in number of queries.


Your Answer

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

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