An experimental study of algorithms for obtaining a singly connected subgraph

\begin{abstract} \normalsize{\noindent A directed graph $G = (V,E)$ is singly connected if for any two vertices $v,u \in V$, the directed graph $G$ contains at most one simple path from $v$ to $u$. In this paper, we study different algorithms to find a feasible but necessarily optimal solution to the following problem. Given a directed acyclic graph $G=(V,E)$, find a subset $H \subseteq E$ of minimum size such that the subgraph $(V,E \setminus H)$ is singly connected. Moreover, we prove that this problem can be solved in polynomial time for a special kind of directed graphs.} \end{abstract}