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.

  • $\begingroup$ It seems that you are looking for an integer linear program. $\endgroup$
    – Steven
    Nov 18 at 19:31
  • $\begingroup$ That's right, sorry I forgot to mention this. $\endgroup$
    – hh vh
    Nov 18 at 19:32
  • $\begingroup$ 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 $\endgroup$
    – 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. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.