On the Complexity of Edge Packing and Vertex Packing

Details On the Complexity of Edge Packing and Vertex Packing On the Complexity of Edge Packing and Vertex Packing

2011-03-29

arxiv.org/abs/1103.5560v2

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Edge Packing and Vertex Packing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of Edge Packing and Vertex Packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Edge Packing and Vertex Packing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162925