What is this linear programming trying to do?

Question

Given $G=(V,E)$, let $\mathbb{R}^V$ be the set of all real vectors $x=(x_v)_{v\in V}$ where each component $x_v$ corresponds to a vertex $v\in V$. Let $Q_G$ be defined $$Q_G:=\{x\in\mathbb{R}^V\;|\;x_u+x_v\geq1\text{ for all }\{u,v\}\in E\text{ and }x_v\geq0\text{ for all }v\in V\}$$

Consider the linear program $$\text{min}\left\{\sum_{v\in V}x_v\;|\;x\in Q_G\right\}$$ Explain what this LP is trying to do.

I was told that this is a famous graph theory problem, but I can't find the name of it. Just interpreting the notation, I think we are summing up all the costs of the vertices denoted $x_v$ and minimizing the edge costs between vertices.

Answer 1

It is the minimum vertex cover issue as explained in paragraph 4 of this clearly written document.

Answer 2

Jean Marie mentioned this is the minimum vertex cover problem, which is correct. However, the problem you formulated has no integrality constraints (e.g. $x_v\in \{0,1\}$), so it is the linear relaxation of the minimum vertex cover problem. So answering your question, it is trying to find a fractional minimum vertex cover.