# On the Complexity of Edge Packing and Vertex Packing

Source: [On the Complexity of Edge Packing and Vertex Packing](<https://www.sota2.com/research/paper/68fa603f1e209131ce9ee685>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:56:27.047Z

Authors: Sameera Muhamed Salam, K. N. Parvathy, K. S. Sudeep, K. Murali Krishnan

Published: 2011-03-29T07:53:17.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1103.5560>)

[PDF](<https://arxiv.org/pdf/1103.5560.pdf>)