# In-approximability results in severely restricted graph classes

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.

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 for details.
• It seems to depend on how you bound them. This other paper 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. Dec 2 '10 at 8:33
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".
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 within $n^{1/4-\epsilon}$ for any $\epsilon>0$) even on trees, see the post by Shiva Kintali.
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.