Kth best problem that is NP-hard for K polynomial 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.
Here is an example of something fairly contrived, but which might be a good starting place for reductions to other problems:

Input:  a boolean formula $\phi$ and a satisfying assignment $x$.
Goal:  find a satisfying assignment $y$ to $\phi$ which has as few variables set to true as possible, but at least as many variables set to true as in $x$

This (well, its decision variant) is obviously in $\mathsf{P}$ ($x$ is itself a solution), but finding the next-best assignment (forcing $y \ne x$) is $\mathsf{NP}$-hard: you can force all satisfying assignments to an arbitrary formula to have a superfluous 1, and then plant the all-zeros assignment. You can also fairly easily plant as many (polynomially many, possibly more if you're clever) assignments as you want.