6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Sure, it's easy to construct an artificial problem that is constructed to make it easy to find the best solution but hard to find subsequent solutions. Do you really want to accept an example like that as a valid answer? If not, please edit the question to specify additional requirements that rule out such trivial cases. (How do you plan to use answers? How do you plan to evaluate them?) $\endgroup$
    – D.W.
    Jun 24, 2016 at 0:56

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$

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.