# NP-complete problems with optimal approximation in poly-time

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?

• 3-coloring problem on planar graphs is $NP$-hard while every planar graph is 4-colorable in polynomial time (by the four color theorem). Feb 1, 2015 at 15:51
• 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$?
– usul
Feb 1, 2015 at 16:27
• Maybe better term for optimal approximation or minimal relaxation is approximation with additive constant error. Feb 1, 2015 at 18:29
• @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.
– usul
Feb 2, 2015 at 0:17
• @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) Feb 2, 2015 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.