# Generalize minimum path cover

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?

• What is [$v_i,v_j$]? – William Elliot Feb 27 '18 at 21:58
• it is just a pair of two vertices. – Thomas Edison Feb 27 '18 at 22:45
• An unordered pair is {x,y}; an ordered pair is (x,y). – William Elliot Feb 28 '18 at 2:23
• It is an order pair, but it does not matter. [x,y] is belong to a path P if $x\in P$ and $y\in P$. For example, if P = x->y->z, then [x,y],[x,z],[y,z] belongs to P. – Thomas Edison Feb 28 '18 at 6:42
• This looks a lot like a minimum set cover problem. Any single path "covers" a fixed set of pairs of vertices. Restrict that to $R$ and you're done. – N.Bach Mar 6 '18 at 12:39