On strongly connected digraphs with bounded cycle length (Q1923587)

Let \(G\) be a strongly connected digraph with cycles of length 3 or less. We wish to find a strongly connected spanning subgraph of \(G\) with the least number of edges. The authors show that this problem is equivalent to the minimum bipartite edge cover problem. This equivalence allows the authors to improve the performance of the best approximation algorithm to the general problem with no cycle bounds.