Where's the flaw in my algorithm? (Linear program to solve NP-hard problem)
In your program specification, "$\forall e\in E: x_e \ge 0$" should be "$\forall e\in E: x_e=0\text{ or } 1$". 

"Each LP-program runs in polynomial time". However, your instance is an instance of integer linear programming (ILP), which is NP-hard, even when all variables are restricted to be either 0 or 1. In particular, this answer shows that the instances of ILP as given in this question is NP-complete.