Problem on a Directed Graph subcase of load time scheduling

Question

I have the following graph optimization problem. In a directed graph G, each node $v$ is assigned a number $n(v)$ which is initially 0. At any time, I can make a move to assign the number $ max \{ n(u)+1: \ \ uv \in E(G) \} $ to vertex $v$. Given a large number $N$, what is the minimum number of moves to assign to each vertex a number greater than $N$?

Can one get any reasonable approximation for this problem?

This is a special case of the load time scheduling problem on DAGs.

• Antoine Amarilli 'a3nm': Hi, you mention DAGs at the end -- are you assuming that the graph is a DAG? Or is "load time scheduling" an existing known problem?
• Antoine Amarilli 'a3nm': Also, do you know whether the problem on the question is NP-hard? What about restricted input graphs, e.g., DAGs, directed trees?
• Hao S: @AntoineAmarilli'a3nm' Load time scheduling is a known problem sciencedirect.com/science/article/abs/pii/…. I don't assume the graph is a DAG actually the problem as I have defined it would be trivial on DAGs as I could start by making the source as large as I wanted and work from there so I only need one step per vertex.
• Antoine Amarilli 'a3nm': I see. Yes, I agree that on DAGs in fact it is clear that the optimal solution always takes Nr+(n-r) moves, where r is the number of sources and n is the number of vertices
• Antoine Amarilli 'a3nm': And I now understand that the last sentence of your post may mean "when restricting the problem of the question to DAGs, then the problem coincides with the load time scheduling problem"

Answer 1

The instance is feasible if and only if no source strongly connected component is a singleton without a self loop. A source singleton with a self loop is pumpable because each move raises it by 1ドル$, while a source singleton without a self loop can never be updated. When the instance is feasible, the exact optimum number of moves is $$ \operatorname{OPT}(G,N)\ =\ Ns\ +\ |V| $$ where $s$ is the number of source SCCs of $G$. The value and an implicit optimal schedule are computable in $O(|V|+|E|)$ time, and writing out the full schedule takes $\Theta(Ns+|V|)$ time.

For the upper bound, first pump one vertex in each source SCC to exceed $N$. Fix a source SCC $S_i$ and choose a directed cycle $C=x_0\to x_1\to\cdots\to x_{\ell-1}\to x_0$. If we update around $C$ in order, then after $t$ moves restricted to $C$ the minimum label on $C$ is $$ \min_{v\in C} n(v)\ =\ \max{0,\ t-|C|+1}. $$ In particular, after $N+1$ such moves some vertex of $S_i$ has label $>N$. Doing this independently in all $s$ source SCCs costs $(N+1)s$ moves and leaves a pumped vertex $r_i$ with $n(r_i)>N$ in each source SCC. Now process SCCs in condensation DAG order. For a source SCC, use $r_i$ as the root and update every other vertex exactly once along a directed out arborescence inside that SCC, which uses $|S_i|-1$ moves there. For a non source SCC, pick a root that has an incoming edge from some already $>N$ vertex in a predecessor SCC, update that root once via that incoming edge, then update every remaining vertex exactly once along an internal arborescence. Counting globally, exactly the $s$ pumped roots need no further update and every other vertex is updated once, so the propagation phase uses $|V|-s$ moves. The total is $$ (N+1)s\ +\ (|V|-s)\ =\ Ns+|V|. $$

For the lower bound, consider any schedule that ends with $n(v)>N$ for all $v$. For each source SCC $S_i$ let $t_i$ be the earliest time at which some vertex of $S_i$ receives its last update. At that moment the chosen vertex $v$ has $n(v)>N$. There is a predecessor $u\to v$ with $n(u)=n(v)-1$ just before, created by an earlier update. Repeating this $N$ times produces a chain of $N+1$ updates strictly increasing in time that lie entirely inside $S_i$. Hence at least $N$ updates in $S_i$ occur strictly before $t_i$ and none of these is a last update in $S_i$. Summing over the $s$ source SCCs gives at least $Ns$ non last updates. Every vertex has exactly one last update, which adds $|V|$ more moves. Therefore any schedule uses at least $Ns+|V|$ moves, which matches the upper bound.

If $G$ is strongly connected and contains a directed cycle then $s=1$ and the optimum is $N+|V|$. If $G$ is a DAG under the exact rule then a source has empty in neighborhood and no self loop, so the instance is infeasible for all $N\ge0$. If instead a source can be set to any value in one move, a single topological pass gives $|V|$ moves. If a source can only be incremented by one per move starting from 0ドル$, the cost is $$ (N+1)r\ +\ (|V|-r) $$ where $r$ is the number of sources.