# 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?

• This is a question coming from University of Waterloo assignment the linked PDF gives more detail and examples about the question. – Виталий Олегович May 27 '12 at 8:00
• Should the total cost be $mcc(V_1, O) + \dots + mcc(V_n, O)$? Are all parent sets considered, or only consistent ones? Are all orderings considered, or only consistent ones? (the latter tow questions are interdependent) Please make sure that the "quote" is exact and not paraphrased by you; often such reformulations are the root of the problem. – Raphael May 27 '12 at 11:55

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<j$ so that there is an edge from $V_{\pi(j)}$ to $V_{\pi(i)}$.
• @VitalijZadneprovskij: The text does not say that the minimisation is only performed over consistent orderings. I assumed that $mcc$ was chosen such that inconsistency is more expensive. But then, the text can also be read so that inconsistent parent sets are ignored. – Raphael May 27 '12 at 13:01