<p><a href="https://arxiv.org/abs/1309.2545" rel="nofollow noreferrer">Angulo, Ahmed, Dey, and Kaibel found an example.</a> 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 href="https://link.springer.com/article/10.1007/s10479-010-0690-5" rel="nofollow noreferrer">a result by Boros, Elbassioni, Gurvich, and Tiwary</a> that shows that it is NP-hard to enumerate a polynomial number of vertices of an integral polyhedron.</p>

CC BY-SA 3.0
2017-02-27T00:25:53.263Z
2017-02-27T00:25:53.263Z
xeqql
<p>Here is an example of something fairly contrived, but which might be a good starting place for reductions to other problems:</p>
<blockquote>
<p><strong>Input:</strong>  a boolean formula <span class="math-container">$\phi$</span> and a satisfying assignment <span class="math-container">$x$</span>.</p>
<p><strong>Goal:</strong>  find a satisfying assignment <span class="math-container">$y$</span> to <span class="math-container">$\phi$</span> which has as few variables set to true as possible, but at least as many variables set to true as in <span class="math-container">$x$</span></p>
</blockquote>
<p>This (well, its decision variant) is obviously in <span class="math-container">$\mathsf{P}$</span> (<span class="math-container">$x$</span> is itself a solution), but finding the next-best assignment (forcing <span class="math-container">$y \ne x$</span>) is <span class="math-container">$\mathsf{NP}$</span>-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.</p>

CC BY-SA 3.0
2016-06-24T17:27:50.250Z
2016-06-24T17:27:50.250Z
2020-06-17T09:38:08.363Z
Andrew Morgan
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-06-24T00:56:33.990Z
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?)
D.W.
<reference-request><np-hardness>
Kth best problem that is NP-hard for K polynomial
xeqql
# Kth best problem that is NP-hard for K polynomial

(Asked by: username_0 on 2016-06-23)

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.

**Tags:** reference-request, np-hardness

> **Comments:**
> **username_1**: 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?)  

---

## 2 answers

### Answer by username_0 on 2017-02-27. Score: 4 | Accepted answer

[Angulo, Ahmed, Dey, and Kaibel found an example.](https://arxiv.org/abs/1309.2545) 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](https://link.springer.com/article/10.1007/s10479-010-0690-5) that shows that it is NP-hard to enumerate a polynomial number of vertices of an integral polyhedron.


---

### Answer by username_2 on 2016-06-24. Score: 4

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.


---

