Decision vs Optimization version for Problems of two Parameters

Question

Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.

Now the corresponding decision problem $foo(M)$ would be:
Is there a solution to foo with quality at least $M$ of size $k$.

For problems on one parameter (for example vertex cover) it is obvious that solving the optimization problem sovles the decision problem.

But here I do not see such a correspondance between the $k$-foo optimization problem and the $foo(M)$ decision problem. How does for example showing that $foo(M)$ is NP-hard implies that $k$-foo is NP-hard?

The $k$-center problem is an example of such a problem where the decision version takes the radius as input and asks wether a solution of size $k$ exists.

Answer 1

Having more than one input doesn't change anything:

Consider an optimization problem $MinQ$:

Input: $x, k$
Output: find $y$ satisfying $Q(x,k,y)$ which minimizes $f(x,k,y)$: $$g(x,k) = \min_{y : Q(x,k,y)} f(x,k,y)$$

The corresponding decision problem $Q$ is:

Input: $x, k, l$
Query: is there a $y$ satisfying $Q(x,k,l)$ such that $f(x,k,y) \leq l$?

To solve the decision problem, we can solve the optimization problem, then check if the output is less than $l$. I.e. there is a very easy reduction from $Q$ to $MinQ$:

input: $x,k,l$
1. $m = MinQ(x,k)$
2. return $m \leq k$