4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ This is a question coming from University of Waterloo assignment the linked PDF gives more detail and examples about the question. $\endgroup$
    – Vitaly Olegovitch
    Commented May 27, 2012 at 8:00
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented May 27, 2012 at 11:55

1 Answer 1

Reset to default
4
$\begingroup$

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)}$.

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ I thought it was about finding the consistent ordering which has the smallest cost. I don't understand. Could you please explain better? $\endgroup$
    – Vitaly Olegovitch
    Commented May 27, 2012 at 12:55
  • $\begingroup$ @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. $\endgroup$
    – Raphael
    Commented May 27, 2012 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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