# Linear programming for prefix of graph

Question: Consider an arbitrary directed graph $$G$$ with weighted vertices, the weights can be positive, negative or $$0$$. The prefix of $$G$$ is a subset of vertices $$P$$ such that there's no edge $$(u \rightarrow v)$$ if $$v \in P$$ and $$u \not\in P$$. Find an integer linear programming to describe the maximum weight prefix of G.

I'm new to linear programming and struggling in come up a LP solution.

The objective function seems trivial, we let $$x_v$$ be a variable to indicate whether that vertex in or not in the prefix. Thus we have, $$\sum_{v \in V} w(v)x_v$$

However, I'm not sure how to impose the prefix constraint such that if we pick a vertex $$v$$, we must have to pick its prefix vertex say $$u$$, if there's a directed edge from $$u$$ to $$v$$. So it seems like we have to check all edges, for each directed edge $$(u \rightarrow v)$$, if $$v \in P$$ then $$u \in P$$. I can only describe this verbally, any suggestion is highly appreciated.

• It seems that you are looking for an integer linear program. Nov 18 at 19:31
• That's right, sorry I forgot to mention this. Nov 18 at 19:32
• Please edit the question to correct the problem statement based on the feedback you have received. Don't just append "Edit: some more stuff". Instead, revise it so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755
– D.W.
Nov 19 at 23:34

To encode the fact that if $$(u,v)$$ is an edge then you you cannot have $$u \not\in P$$ and $$v \in P$$ you can add (for each edge) the following constraint:
$$(1-x_u) + x_v \le 1,$$
equivalently: $$x_v - x_u \le 0.$$