# 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$). 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.

-
Thanks Anthony for this interesting example, Does it remain in-approximable if the number of colors is bounded? – Mohammad Al-Turkistany Dec 2 '10 at 7:40
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. – Anthony Labarre 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.

-