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

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

CC BY-SA 3.0
2015-02-01T16:01:17.887Z
2015-02-01T16:01:17.887Z
Gamow
<p>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:</p>

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

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

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

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

<p>An example for such problem is the <a href="http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree" rel="nofollow">Degree-constrained spanning tree</a>, where the problem is finding an MST with minimal maximum vertex degree.</p>

<blockquote>
  <p><strong>Which other languages are NP-hard but subject to optimal approximation in poly time?</strong></p>
</blockquote>

CC BY-SA 3.0
2015-02-01T15:51:18.620Z
3-coloring problem on planar graphs is $NP$-hard while every planar graph is 4-colorable in polynomial time (by the four color theorem).
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-02-01T16:27:35.627Z
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
CC BY-SA 3.0
2015-02-01T16:55:21.650Z
@usul - since Max-Cut is a maximization problem you'll need to reverse the definitions: given an instance $<G,k>$, accept if there exists a cut with at least $k-1$ edges, reject if there is no cut with $k+1$ edges. Since Max-Cut is $APX$-hard, I don't think it is a good candidate here.
R B
CC BY-SA 3.0
2015-02-01T17:22:52.083Z
OK, I see. I was thinking that $k$ was a fraction of edges in the graph.
usul
CC BY-SA 3.0
2015-02-01T18:29:41.423Z
Maybe better term for optimal approximation or minimal relaxation is approximation with additive constant error.
Saeed
CC BY-SA 3.0
2015-02-02T00:17:44.437Z
@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
CC BY-SA 3.0
2015-02-02T08:05:36.360Z
@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)
Saeed
CC BY-SA 3.0
2015-02-02T14:19:05.807Z
So for instance, if we flip the definition from minimization to maximization, then this class would contain the language $L = \{(w,k) : w$ is a graph on $n$ nodes with a maximum cut of at most $k n^2\}$. Similarly when we change to $\alpha k n^2$ for various values of the constant $\alpha$. But (under common assumptions) this class does not contain $L = (w,k): w$ a graph with a max cut of at most $k$. Is that right?
usul
<cc.complexity-theory><np-hardness><approximation-algorithms>
NP-complete problems with optimal approximation in poly-time
R B
# NP-complete problems with optimal approximation in poly-time

(Asked by: username_0 on 2015-02-01)

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](http://en.wikipedia.org/wiki/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?**

**Tags:** cc.complexity-theory, np-hardness, approximation-algorithms
> **Comments:**
> **username_1**: 3-coloring problem on planar graphs is $NP$-hard while every planar graph is 4-colorable in polynomial time (by the four color theorem).  
> **username_2**: 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$?  
> **username_0**: @usul - since Max-Cut is a maximization problem you'll need to reverse the definitions: given an instance $<G,k>$, accept if there exists a cut with at least $k-1$ edges, reject if there is no cut with $k+1$ edges. Since Max-Cut is $APX$-hard, I don't think it is a good candidate here.  
> **username_2**: OK, I see. I was thinking that $k$ was a fraction of edges in the graph.  
> **username_3**: Maybe better term for optimal approximation or minimal relaxation is approximation with additive constant error.  
> **username_2**: @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.  
> **username_3**: @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)  
> **username_2**: So for instance, if we flip the definition from minimization to maximization, then this class would contain the language $L = \{(w,k) : w$ is a graph on $n$ nodes with a maximum cut of at most $k n^2\}$. Similarly when we change to $\alpha k n^2$ for various values of the constant $\alpha$. But (under common assumptions) this class does not contain $L = (w,k): w$ a graph with a max cut of at most $k$. Is that right?  

---

## 1 answers

### Answer by username_4 on 2015-02-01. Score: 3 | Accepted answer

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.


---

