A master solution for an instance of a combinatorial problem is a solution with the property that it is optimal for any sub instance. For example, a master tour for an instance of the traveling salesman problem (TSP) has the property that shortcutting the solution on any subset S results in an optimal solution for S. The problem of deciding if a TSP instance has a master tour is known to be polynomially solvable.

In this talk, I will show that the master tour problem is Delta_2^p-complete in the scenario setting, that means, the subsets S are restricted to some given sets. I will also give a brief introduction on the complexity class Delta_2^p and the polynomial hierarchy. Similar results for the master versions of Steiner tree and maximum satisfiability will also be discussed. In the end, there will be time for questions and discussion.

This is joint work with René Sitters, published in the proceedings of MFCS 2015.