4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – narek Bojikian Dec 20 '19 at 21:45
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.