In-approximability results in severely restricted graph classes

Question

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.

Answer 1

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.

Answer 2

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".

Answer 3

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.

Answer 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.