Polynomial algorithm for problem in graphs which can also be solved as a linear programming problem. I have an (undirected) graph $G = (V, E)$. For each vertex $i \in V$ we have a cost associated $v_i$ and for each edge $e \in E$ we have a prize associated $x_e$. 
My problem is to find $W \subseteq V$ which:
1) has the maximum value for $\sum_{e \in E(W)} x_e - \sum_{i \in W} v_i$
2) and contains a specific vertex $k$ ($k \in W$, $k$ is known a priori).
$E(W)$ are edges with both endpoints in $W$.
Edit due to question by wece: In my specific problem, both prizes and costs are nonnegative ($\mathbb{R}^+$). However, the value for $\sum_{e \in E(W)} x_e - \sum_{i \in W} v_i$ can very well be negative.
This problem can be modelled as an integer programming problem whose constraints matrix I have already proved to be totally unimodular. So I know it can be solved polynomially, since if I solve its linear relaxation I will get an integral solution and I can use an interior points method with polynomial complexity. 
Is this problem known? I mean, does it have a specific name in the scientific literature? I am trying to find a polynomial algorithm for it instead of solving the LP via interior points, any ideas? I think (but may be wrong) that we cannot use the max flow/min cut algorithm here.
Thanks.
 A: First we rule out the $k$. Since we know it belongs to $W$ we can remove it from the graph. We also modify the cost of the neighbour of $k$ in order to take into account the prize received from the edge with $k$. Thus the new cost of $i$ is $v_i-x_{(k,i)}$.
(Notice that if a cost is now negative we know that this vertex belongs to $W$ hence we can repeat that).
Now we will compute the set $W$.
To do so we use multiple iteration of a max flow algorithm. 
Let $G=(V,E)$ be an undirected graph. 
We define $G_0=(V_0,E_0)$ as:


*

*$V_0=V\cup E\cup\{s,t\}$

*$E_0=\{(s,e)\mid e\in E\}\cup \{(i,t)\mid i\in V\}\cup \{(e,i)\mid e=(i,i')\}$


We define the capacity $C$ as follow:


*

*$C(s,e)=x_e$

*$C(i,t)=v_i$

*$C(e,i)=+\infty$


Run the max flow algorithm. We denote $U$ the set of all vertices such that the flow outgoing the vertex is smaller than the capacity i.e. such that $F(i,t)<C(i,t)$.
The idea is that we know that $U\cap W=\emptyset$ hence we can remove the vertices $U$ from $V$.
Repeat the construction on the graph $G'=(V\setminus U,E(V\setminus U))$, the max flow and again until for all vertices $F(i,t)=C(i,t)$. At this point the vertices left are exactly $W$.
I let the proof to you but the idea is to show that at each step you keep the vertices of $W$. This is true because the edges of $E(W)$ are enough to fill the capacity of the $W$ vertices. This gives you an inclusion, for the other inclusion you can proceed by absurd, assume that the set you get does not maximize the sum. You know that the set you have is bigger than $W$. Reason on the sum of the prize gained by the additional edges compared to the prices, you know it's positive since the flow was maximal thus contradiction.
(Sorry it's very late and I'm a bit tired. I hope my idea are clear enough and that I didn't made a mistake)
