<p>The labelled perfect matching problem, which consists in finding a perfect matching in an edge-coloured graph that uses the minimum number of colours, is not in APX for subcubic bipartite graphs (but it is $2$-approximable if the maximum degree is $2$ instead of $3$). See <a href="http://www.lamsade.dauphine.fr/~monnot/index_fichiers/Rairo_HardLM.pdf">Monnot</a> for details.</p>

CC BY-SA 2.5
2010-12-02T07:40:40.260Z
Thanks Anthony for this interesting example, Does it remain in-approximable if the number of colors is bounded?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-02T08:33:11.337Z
It seems to depend on how you bound them. [This other paper](http://dx.doi.org/10.1016/j.disopt.2010.02.003) answers your question positively in the case where "every colour appears in the graph at most $r$ times and $r$ is an increasing function of $n$". I don't know about other particular cases, but there may very well exist other such results.
Anthony Labarre
CC BY-SA 2.5
2010-12-02T07:21:57.857Z
2010-12-02T07:21:57.857Z
Anthony Labarre
<p>The Bandwidth problem remains NP-hard to approximate within any constant factor even when restricted to caterpillars (a special class of trees where all vertices of degree $&gt;2$ lie on a path). This is shown by Dubey, Feige and Unger in <a href="http://www.wisdom.weizmann.ac.il/~feige/mypapers/DubeyFeigeUnger.pdf">"Hardness results for approximating the bandwidth"</a>.</p>

CC BY-SA 3.0
2012-12-15T17:22:36.217Z
2012-12-15T17:22:36.217Z
Michael Lampis
<p>The Group Steiner problem is $\Omega(\log^{2-\epsilon} n)$ hard on trees. The multicut problem is APX-hard on trees. The maximum integer flow problem is also APX-hard in capacitated trees.</p>

CC BY-SA 3.0
2012-12-15T20:49:08.870Z
2012-12-15T20:49:08.870Z
Chandra Chekuri
<p>There are problems like <strong>common subtree problem</strong> remains NP-complete/hard and inapproximable within constant factors (in the case of common subtree problem, it is <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node168.html" rel="nofollow noreferrer">inapproximable</a> within $n^{1/4-\epsilon}$ for any $\epsilon&gt;0$) even on trees, see <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees">the post</a> by Shiva Kintali.</p>

CC BY-SA 2.5
2010-12-02T07:38:30.293Z
2010-12-02T07:47:47.497Z
2017-04-13T12:32:28.167Z
Hsien-Chih Chang 張顯之
<p>Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path <span class="math-container">$\notin APX$</span> unless <span class="math-container">$P=NP$</span>). I don't know if it remains in-approximable in cubic bipartite Hamiltonian graphs. Maximum independent set is not in <span class="math-container">$APX$</span> unless <span class="math-container">$P=NP$</span> but it is in <span class="math-container">$APX$</span> for cubic graphs. David Eppstein pointed out that it is <span class="math-container">$NP$</span>-complete to find maximum clique in claw-free graphs and it is not clear to me if it is any easier to approximate than in general graphs. </p>

<ul>
<li>I'm interested in optimization problems that remains in-approximable in <strong>severely restricted</strong> classes of graphs (for instance, cubic planar bipartite graphs or trees of bounded degree).</li>
</ul>

<p>A problem <span class="math-container">$L$</span> is In-approximable means that  <span class="math-container">$L \notin APX$</span>. It is <span class="math-container">$NP$</span>-hard to approximate to any constant factor in polynomial-time.</p>

CC BY-SA 2.5
2010-12-01T22:03:54.573Z
Here is the link to David's answer, http://cstheory.stackexchange.com/questions/3338/graph-classes-in-which-clique-is-known-to-be-np-hard/3356#3356
Mohammad Al-Turkistany
<cc.complexity-theory><approximation-hardness><apx>
In-approximability results in severely restricted graph classes
Mohammad Al-Turkistany
# In-approximability results in severely restricted graph classes

(Asked by: username_0 on 2010-12-01)

Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$ unless $P=NP$). I don't know if it remains in-approximable in cubic bipartite Hamiltonian graphs. Maximum independent set is not in $APX$ unless $P=NP$ but it is in $APX$ for cubic graphs. David Eppstein pointed out that it is $NP$-complete to find maximum clique in claw-free graphs and it is not clear to me if it is any easier to approximate than in general graphs.

* I'm interested in optimization problems that remains in-approximable in **severely restricted** classes of graphs (for instance, cubic planar bipartite graphs or trees of bounded degree).

A problem $L$ is In-approximable means that $L \notin APX$. It is $NP$-hard to approximate to any constant factor in polynomial-time.

**Tags:** cc.complexity-theory, approximation-hardness, apx

> **Comments:**
> **username_0**: Here is the link to David's answer, http://cstheory.stackexchange.com/questions/3338/graph-classes-in-which-clique-is-known-to-be-np-hard/3356#3356  

---

## 4 answers

### Answer by username_1 on 2010-12-02. Score: 7

The labelled perfect matching problem, which consists in finding a perfect matching in an edge-coloured graph that uses the minimum number of colours, is not in APX for subcubic bipartite graphs (but it is $2$-approximable if the maximum degree is $2$ instead of $3$). See [Monnot](http://www.lamsade.dauphine.fr/~monnot/index_fichiers/Rairo_HardLM.pdf) for details.

> **Comments:**
> **username_0**: Thanks Anthony for this interesting example, Does it remain in-approximable if the number of colors is bounded?  
> **username_1**: It seems to depend on how you bound them. [This other paper](http://dx.doi.org/10.1016/j.disopt.2010.02.003) answers your question positively in the case where "every colour appears in the graph at most $r$ times and $r$ is an increasing function of $n$". I don't know about other particular cases, but there may very well exist other such results.  

---

### Answer by username_2 on 2012-12-15. Score: 7

The Bandwidth problem remains NP-hard to approximate within any constant factor even when restricted to caterpillars (a special class of trees where all vertices of degree $>2$ lie on a path). This is shown by Dubey, Feige and Unger in ["Hardness results for approximating the bandwidth"](http://www.wisdom.weizmann.ac.il/~feige/mypapers/DubeyFeigeUnger.pdf).


---

### Answer by username_3 on 2012-12-15. Score: 4

The Group Steiner problem is $\Omega(\log^{2-\epsilon} n)$ hard on trees. The multicut problem is APX-hard on trees. The maximum integer flow problem is also APX-hard in capacitated trees.


---

### Answer by username_4 on 2010-12-02. Score: 4

There are problems like **common subtree problem** remains NP-complete/hard and inapproximable within constant factors (in the case of common subtree problem, it is [inapproximable](http://www.nada.kth.se/~viggo/wwwcompendium/node168.html) within $n^{1/4-\epsilon}$ for any $\epsilon>0$) even on trees, see [the post](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees) by Shiva Kintali.


---

