Relation between decision and optimization versions of precedence
constrained scheduling:

Problem Precedence constrained scheduling (PCS):
Inputs: Directed Acyclic Graph G = (V,E), integer p.
Output: minimum length schedule for executing G using p processors
such that for every edge (u,v) vertex u is scheduled before vertex v.

Problem DPCS:
Input: G,p as above and integer k.
Output: YES if there exists a schedule of length k, NO otherwise.

Claim: If DPCS can be solved in polynomial time, then so can PCS.

Proof: Let us assume that there exists a O(n^c) time algorithm for
solving DPCS, where n is the number of vertices.  We will show that we
can use this as a subroutine to solve PCS.

Here is the algorithm for PCS:

PCS(G,p){
0.  t = 1
1.  for k=1 to n
      if DPCS(G,p,k) then break
    end for

    // At this point k = length of optimal schedule.

2.  For each edge e in G
	If DPCS(G union e, p, k) then G = G union e.

3.  Let V' denote set of vertices in G not having predecessors.
    Schedule V' at step t.  t = t+1

4.  If G has vertices remove V' from G and go to step 3.
}

Claim: V' has size at most p.
Proof: First consider the set V' that we get after step 2.

Suppose V' has size more than p.  We do know that G can be scheduled
in k steps.  Clearly, some V'' of these V' must get scheduled in step
1 of the optimal schedule.  Let u be a vertex in V' but not in V''.  u
is not scheduled in step 1, so if we add an edge from some vertex v'
in V' to u, the resulting graph will still have a schedule that takes
only k steps.  But this edge (u,v') would then have been added in step
2 when we considered adding all possible edges.  But then u must have
an ancestor.  So we have a contradiction.  Hence the
vertices V' not having a predecessor has to be at most p.

We can similarly argue when step 3 is entered from step 4.
----

Claim: An optimal schedule is produced by the algorithm.
Proof: We know that the G that results at the end of step 2 has a
schedule of length k, and since it only contains more edges than the
original G, the new schedule will respect all the previous
constraints.  Hence it suffices to construct a schedule for the final
graph G resulting after step 2.

Now, we showed that G must have at most p vertices without
predecessors.  Thus there has to exist an optimal schedule having
these vertices in step 1 (no other vertices can be in step 1, if a
given optimal schedule does not have all of V' in step 1, then clearly
we can move them from later steps to step 1).  The same thing applies
to the graph resulting after each iteration of step 4.
-----

The only thing that remains now is to argue that the algorithm PCS
takes time O(n^b) for some constant b.  We know that step 1 takes time
n.n^c.  Step 2 takes time m.n^c, where m is the number of edges in the
graph, which can be at most n^2.  In step 3 we find the nodes without
any incoming edges.  This takes at most O(n) time.  Step 4 removes all
nodes found in step 3.  This can take at most O(m) steps since edges
also have to be removed.  Since both step 3 and step 4 need to be
executed at most n times, the total time for steps 3 and 4 is at most
O(n(n+m)).  Given that c is a constant, and m at most n^2, the total
time is at most O(n^b), for some constant b.

(Steps 3,4 can be done faster using topological sort, but it doesnt
matter if we want to show that the total time taken is a polynomial.)

--------------