0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is [$v_i,v_j$]? $\endgroup$ – William Elliot Feb 27 '18 at 21:58
  • $\begingroup$ it is just a pair of two vertices. $\endgroup$ – Thomas Edison Feb 27 '18 at 22:45
  • $\begingroup$ An unordered pair is {x,y}; an ordered pair is (x,y). $\endgroup$ – William Elliot Feb 28 '18 at 2:23
  • $\begingroup$ 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. $\endgroup$ – Thomas Edison Feb 28 '18 at 6:42
  • $\begingroup$ 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. $\endgroup$ – N.Bach Mar 6 '18 at 12:39

Your Answer

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

Browse other questions tagged or ask your own question.