Complexity of learning matchings and half graphs via edge queries

Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev

The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic ty…