7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

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

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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