Topological sort, but with some fixed values
There's a natural algorithm:


Arbitrarily pick any vertex all of whose predecessors have already been labelled; call it $v$.
If $v$ is constrained to have a specific index, label $v$ with that integer.  Otherwise, pick the smallest integer greater than all of the labels on the predecessors of $v$, and label $v$ with that integer.
If at least one vertex remains unabelled, go to step 1.


This is an adaptation of Kahn's algorithm for topological sorting, and it can be implemented so it runs in linear time.

The crucial thing that makes your problem feasible is that the labels don't need to be unique.  If the labels need to be unique, I suspect the problem becomes much harder; at least, this algorithm doesn't work, and a generalization of the problem becomes NP-hard.