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?