A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to decide whether there are K solutions that achieve a given value.Garey and Johnson list several NP-hard Kth best problems: Kth Best Spanning Tree, Kth Shortest Path, Kth Largest Subset, and Kth Largest m-Tuple. However each of these problems can be solve in polynomial time if K is restricted to be polynomial in the size of the rest of the input.Is there a Kth best problem that is NP-hard even if K is restricted to be polynomial in the size of the rest of the input (but poly-time solvable for K=1)? The problem should be natural enough that other Kth best problems can reduce to it, or at least be a good example for how to show NP-hardness of a Kth best problem.
Kth best problem that is NP-hard for K polynomial
reference request;np hardness
Angulo, Ahmed, Dey, and Kaibel found an example. They establish that finding the $K$-best vertices of a bounded linear program is NP-hard when $K$ is polynomial, even though finding the optimal vertex is solvable. They reduce from a result by Boros, Elbassioni, Gurvich, and Tiwary that shows that it is NP-hard to enumerate a polynomial number of vertices of an integral polyhedron.