On the approximability of the vertex cover and related problems
| dc.creator | Han, Qiaoming | |
| dc.creator | Punnen, Abraham P. | |
| dc.date | 2007-12-20 | |
| dc.date.accessioned | 2026-07-07T08:50:31Z | |
| dc.date.available | 2026-07-07T08:50:31Z | |
| dc.description | In this paper we show that the problem of identifying an edge $(i,j)$ in a graph $G$ such that there exists an optimal vertex cover $S$ of $G$ containing exactly one of the nodes $i$ and $j$ is NP-hard. Such an edge is called a weak edge. We then develop a polynomial time approximation algorithm for the vertex cover problem with performance guarantee $2-\frac{1}{1+σ}$, where $σ$ is an upper bound on a measure related to a weak edge of a graph. Further, we discuss a new relaxation of the vertex cover problem which is used in our approximation algorithm to obtain smaller values of $σ$. We also obtain linear programming representations of the vertex cover problem for special graphs. Our results provide new insights into the approximability of the vertex cover problem - a long standing open problem. | |
| dc.identifier | https://arxiv.org/abs/0712.3333 | |
| dc.identifier | http://arxiv.org/abs/0712.3333 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/144630 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2; G.2.2; G.1.6 | |
| dc.title | On the approximability of the vertex cover and related problems | |
| dc.type | text |