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.

Here is the link to David's answer, http://cstheory.stackexchange.com/questions/3338/graph-classes-in-which-clique-is-known-to-be-np-hard/3356#3356 — Mohammad Al-Turkistany, Dec 01 '10 at 22:03

score 7 · Answer 1 · answered Dec 15 '12 at 17:22

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

score 7 · Answer 2 · answered Dec 02 '10 at 07:21

7

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.

answered Dec 02 '10 at 07:21

Anthony Labarre

3,264
1
25
33

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

score 4 · Answer 3 · answered Dec 15 '12 at 20:49

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.

answered Dec 15 '12 at 20:49

Chandra Chekuri

6,999
31
39

score 4 · Answer 4 · edited Apr 13 '17 at 12:32

4

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.

edited Apr 13 '17 at 12:32

Community

1

answered Dec 02 '10 at 07:38

Hsien-Chih Chang 張顯之

7,638
4
44
83

In-approximability results in severely restricted graph classes

4 Answers4