Vertex Cover without integer programming Is there a way to formulate an LP(linear programming) for minimum vertex cover problem without forcing the variables to be integers (no integer programming)? The number of variables are not restricted as long as they are finite. I googled it for so long, but all I could find was 2-approximation algorithm. 

To add to Mark's answer:
It has been shown here that the factor 2 cannot be improved.
On the other hand, if your graph is bipartite, the relaxed version of the ILP gives integer solutions, since then the constraint matrix is totally unimodular.
So, this version of the problem can be solved efficiently.
See e.g. here.
