I'm looking for examples of hard optimization problems, for which we have an optimal approximation (not that this is not the same as $PTAS$, as we require a completely tight approximation, and not $1+\epsilon$-multiplicative approximation), in a sense defined as follows:

Formally, let $L\subseteq\Sigma^*\times \mathbb N$ be the decision version of some minimization (or maximization, flipping the definitions) problem, i.e. $$\forall n\leq m:(w,n)\in L\implies (w,m)\in L$$

Which examples of such known languages $L$ is $NP$-hard, but if we are allowed of a minimal relaxation, it is poly time solvable.

By minimal relaxation I mean that there exists a TM such that given an input $(w,n)$:

  • The machine accepts if $(w,n+1)\in L$.
  • The machine rejects if $(w,n-1)\not \in L$.
  • The machine may act arbitrarily on other cases.

An example for such problem is the Degree-constrained spanning tree, where the problem is finding an MST with minimal maximum vertex degree.

Which other languages are NP-hard but subject to optimal approximation in poly time?

  • 2
    $\begingroup$ 3-coloring problem on planar graphs is $NP$-hard while every planar graph is 4-colorable in polynomial time (by the four color theorem). $\endgroup$ – Mohammad Al-Turkistany Feb 1 '15 at 15:51
  • $\begingroup$ I guess there is an issue of discretization that is tricky. For example, if we want to formalize Max-Cut in this framework, what is the meaning of $n+1$ and $n-1$? $\endgroup$ – usul Feb 1 '15 at 16:27
  • 2
    $\begingroup$ Maybe better term for optimal approximation or minimal relaxation is approximation with additive constant error. $\endgroup$ – Saeed Feb 1 '15 at 18:29
  • 1
    $\begingroup$ @Saeed, can you explain how that's equivalent? I think the issue is that I still don't understand what the role of the constant $1$ is in the definition. $\endgroup$ – usul Feb 2 '15 at 0:17
  • 1
    $\begingroup$ @usul I didn't understand what you don't understand. But you can search about additive constant error to understand what it is, assuming you know this, OP's question is about additive error 1 (replace constant with 1) $\endgroup$ – Saeed Feb 2 '15 at 8:05

One example is the chromatic index (edge-coloring number) of undirected graphs. By Vizing's theorem, the chromatic index either equals the max-degree $\Delta$ or equals $\Delta+1$.

  • Vizing's proof gives a polynomial time (inductive) procedure for finding a coloring with $\Delta+1$ colors.
  • Holyer has proved that deciding whether the chromatic index equals $\Delta$ is NP-complete.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.