patternMinor
Need help understanding this optimization problem on graphs
Viewed 0 times
thisunderstandingproblemneedgraphshelpoptimization
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#2100, answer score: 4
Revisions (0)
No revisions yet.