Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Here is the link to David's answer, cstheory.stackexchange.com/questions/3338/… –  Mohammad Al-Turkistany Dec 1 '10 at 22:03
add comment

4 Answers 4

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.