2
$\begingroup$

This question is from Erickson's textbook on algorithms, p. 376, question 18.

Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in classes as “students”, to ensure that every class they offer is completely full. Because actors are expensive, the university wants to hire as few of them as possible.

Building on their previous leadership experience at the now-defunct Sham-Poobanana University, the administrators at Potemkin have given you a directed acyclic graph $G = (V, E)$, whose vertices represent classes, and where each edge $i \rightarrow j$ indicates that the same “student” can attend class $i$ and then later attend class $j$. In addition, you are also given an array $cap[1\cdots V]$ listing the maximum number of “students” who can take each class. Describe an analyze an algorithm to compute the minimum number of “students” that would allow every class to be filled to capacity.

My best solution is $O(cV^3)$, where $c$ is the max of class capacities $\max_i \{ cap[i] \}$. Is there a better solution? Because I have a feeling there is.


My solution:

  1. Initialise $x$, the minimum number of students to fill each class to capacity, as 0.
  2. For each vertex $i, j$ where $i \neq j$, combine all the $i \rightarrow j$ edges into a single edge with capacity equals the number of original $i \rightarrow j$ edges.
  3. Set the capacity of each vertex $v$ as $cap[v]$.
  4. Since this is a DAG, there are source vertices and sink vertices. Add a vertex $v_\text{in}$ with outgoing edge of infinite capacity to each source vertex. Add outgoing edge of infinite capacities from each sink vertex to a another new vertex $v_\text{out}$.
  5. Find the max $(v_\text{in}-v_\text{out})$ flow. $|f|$. Increment $x$ by this value $|f|$. Decrement the capacity of each vertex and edge in the graph by the component flow through it.
  6. Remove $v_\text{in}, v_\text{out}$, and their edges. Remove all vertices and edges with capacity zero.
  7. Repeat steps 4 to 6 until no vertices are left in the graph.

Time complexity:

This solution runs Orlin's $x$ times, but $x$ is bounded from above by the maximum of class capacities, previously denoted $c$. So, $O(cVE) = O(cV^3)$.

$\endgroup$

1 Answer 1

2
$\begingroup$

You can use the min-cost max-flow algorithm to solve this more efficiently. (The Ford Fulkerson algorithm is only changed slightly to achieve this for DAGs). In your graph construction, instead of adding edges from a dummy source to all "source-vertices" on the original graph, add them to all vertices instead; do the same for the dummy sink.

For each edge added from the dummy source, give it some positive cost and keep the cost of all other edges 0. With this new graph, solve the min-cost max flow problem to get the desired result.

min cost max flow has the same complexity as max flow so your answer should be $\mathcal{O}(V^3)$.

$\endgroup$

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.