## complexity theory – Inapproximability of graph problems on a restricted setting

I am considring the following problem $$mathcal{P}$$.

$$mathcal{P}$$: Given an undirected graph $$G$$, and an integer $$k$$, find a set of vertices $$S subseteq V(G)$$, with $$|S| = k$$, such that the number of edges in the subgraph induced by $$S$$ is minimized.

which is clearly NP-hard, as the answer is 0 iff there is an independent set of size $$k$$ in $$G$$. So I am interested in studying whether the problem can be approximated assuming $$mathrm{P} neq mathrm{NP}$$ (assumption implicit from now on).

Now, for the restricted setting, imagine $$c > 0$$ is an arbitrary constant, and then define $$cmathcal{P}$$ as the same problem but with the restriction that $$|V(G)| geq c cdot k$$. The question I am wondering is whether, given the following claims 1) and 2), it is true that 1) implies 2).

1. There is a constant $$rho > 1$$ such that $$mathcal{P}$$ cannot be approximated by a factor better than $$rho$$.
2. There is a constant $$rho’ > 1$$ such that for any constant $$c > 0$$ the problem $$cmathcal{P}$$ cannot be approximated by a factor better than $$rho’$$.

I would appreciate any help, or pointers to problems when something like that is proven.

Posted on Categories Articles

## approximation – Polynomial variable of inapproximability after reduction

I proved the inapproximability of a problem that, given a multigraph $$G = (V, E)$$ and a set of vertices $$U subseteq V$$ tries to maximize a score $$f(U)$$ whose value depends on the edges of the graph, so it takes values in $${0, dots, m}$$, $$m$$ being the number of edges in the graph.

As the result was obtained by (exactly) reducing from the Maximum Independent Set which is known for being inapproximable within $$n^{1- epsilon}$$, I am not sure how this is translated to my problem: Is it inapproximable within $$n^{1- epsilon}$$ or within $$m^{1- epsilon}$$ (as, in a certain sense, it counts the number of edges)?

(In the proof we build a multigraph in which each edge contributing to the score is associated with an independent vertex in the original graph and vice versa)

Posted on Categories Articles