I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths.
When $b_i=1$ for all the vertices, the problem can be solved in polynomial time. But I am searching for the complexity of the problem when $b_i>1$ for at least one vertex $v_i$, do you know about any results that may help me?
This problem can be solved with minimum-cost flow in polynomial time.
The flow network should should contain source and sink vertices $s$ and $t$, and for each vertex $v \in V$ two vertices, $v_{in}$ and $v_{out}$. The vertex $v_i$ should have an edge form $v_{in}$ to $v_{out}$ with capacity $b_i$ and cost $-3$. For each original edge $(u, v) \in A$, create an edge from $u_{out}$ to $v_{in}$ with capacity $\infty$ and cost $0$. For each $v$, create an edge from source $s$ to $v_{in}$ with capacity $\infty$ and cost $1$ and an edge from $v_{out}$ to sink $t$ with capacity $\infty$ and cost $1$.
Now in optimal flow, the cost will be $2 \cdot P -3 \cdot \sum b_i$, where $P$ is the optimal number of paths used.
