Need help understanding this optimization problem on graphs Has anyone seen this problem before? It's suppose to be NP-complete.


  We are given vertices $V_1,\dots ,V_n$ and possible parent sets for each vertex. Each parent set has an associated cost. Let $O$ be an ordering (a permutation) of the vertices. We say that a parent set of a vertex $V_i$ is consistent with an ordering $O$ if all of the parents come before the vertex in the ordering. Let $mcc(V_i, O)$ be the minimum cost of the parent sets of vertex $V_i$ that are consistent with ordering $O$. I need to find an ordering $O$ that minimizes the total cost: $mcc(V_1, O), \dots ,mcc(V_n, O)$.


I don't quite understand the part "...if all of the parents come before the vertex in the ordering." What does it mean?
You can think of the parent sets as incident nodes; that is if $V_i$ is in the parent set of $V_j$, there is a (directed) edge from $V_i$ to $V_j$.

An ordering "consistent" with this graph in the sense of the exercise is a topological sorting, that is a topological ordering $V_{\pi(1)}, \dots, V_{\pi(n)}$ has no pair $(i,j)$ with $i&lt;j$ so that there is an edge from $V_{\pi(j)}$ to $V_{\pi(i)}$.

The problem is then to find an ordering as consistent with the graph as possible.