  This paper studies the computational complexity of the Edge Packing problem
and the Vertex Packing problem. The edge packing problem (denoted by
$\bar{EDS}$) and the vertex packing problem (denoted by $\bar{DS} $) are linear
programming duals of the edge dominating set problem and the dominating set
problem respectively. It is shown that these two problems are equivalent to the
set packing problem with respect to hardness of approximation and parametric
complexity. It follows that $\bar{EDS}$ and $\bar{DS}$ cannot be approximated
asymptotically within a factor of $O(N^{1/2-\epsilon})$ for any $\epsilon>0$
unless $NP=ZPP$ where, $N$ is the number of vertices in the given graph. This
is in contrast with the fact that the edge dominating set problem is
2-approximable where as the dominating set problem is known to have an $O(\log$
$|V|)$ approximation algorithm. It also follows from our proof that $\bar{EDS}$
and $\bar{DS}$ are $W[1]$-complete.
