If we consider the decision version of the classical graph coloring problem, then we have some graph $G$ and some integer $k$ and we want to color $G$ with at most $k$ colors. It is well known that, given an oracle which tells us True or False for a tuple $(G,k)$, we can find the minimal $\hat{k}$ for which $G$ is $\hat{k}$ colorable using something like binary search in polynomial time.

Assume now that we consider an (abstract) slightly different problem, where we do not just have one parameter $k$, but rather two parameters $k_1$ and $k_2$ (these could be for example a bound on the number of colors and a bound of the number of different colors contained in some induced subgraph or something along these lines). Now consider some objective like $\min \{k_1,k_2\}$ or $k_1+k_2$ or something similar.

Note that we only use coloring as an example here, the question is more concerned with the general case of $\mathbb{NP}$ hard problems with several parameters.

Given an oracle for $(G,k_1,k_2)$ is it possible to solve this extended problem in polynomial time? Or is there some constraint on the objective function which has to be fulfilled in order to guarantee existance? Or what about the more general case where there are parameters $k_1,...,k_n$, with $n$ depending on the input size?

  • 2
    $\begingroup$ I imagine it will depend on the specifics; it seems unlikely to be able to answer such a broad question when the problem is unstated, and the meaning of $k_1,k_2$ are unstated, and the objective function is left unstated. I suspect you should be able to find some trivial counterexamples by choosing sufficiently complex objective functions. Also it would help to give a precise statement of the optimization problem and the decision problem, rather than force us to infer that. $\endgroup$
    – D.W.
    Mar 7 '21 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.