Generalize minimum path cover

212 Views Asked by At

Let $G=(V,E)$ be a directed acyclic graph (DAG). A vertex $u$ reaches a vertex $v$ if there is a directed path from $u$ to $v$. Let $R \subseteq \{ [v_i, v_j] | v_i,v_j \in V$ and $v_i$ reaches $v_j\}$. I want to find a set of directed paths $\mathcal P$ in $G$ of minimum cardinality (i.e, the smallest number of paths) that cover $R$, that is, any pair in $R$ belongs to at least a path in $\mathcal P$. A pair $[u,v]$ belongs to a path $p$ if the vertices $u,v$ belong to $p$. This problem is NP-hard. I think that it is still NP-hard even for one special case where $R = \{ [v_i, v_j] | v_i,v_j \in V$ and $v_i$ reaches $v_j\}$but I have no idea to prove it. Does anyone have any idea? Or what is algorithm to solve it?