# Partition into paths in a Directed Acyclic Graphs

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?

• I don't know if this helps, but since the problem is reduced to matching in bipartite gaphs you can check the b-matching problem in bipartite graphs. It also has a min-max characterization so a similar proof should work Dec 20, 2019 at 21:45

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.