Optimal algorithm for converting an acyclic digraph to a cluster | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 54. DOI: 10.17223/20710410/54/4

For a bipartite digraph G, in which all arcs go from the first part to the second, the problem of finding the minimum set of arcs, whose complement transforms it into a strongly connected digraph, is solved. It is proved that the minimum number of additional arcs that transform a bipartite digraph G into a strongly connected one is equal to the maximum of the number of vertices of the first and second parts. An algorithm is constructed for determining the minimum set of additional arcs that transform a given digraph into a strongly connected one. This algorithm is based on the selection of the minimum edge coverage, as a set of unconnected stars in the digraph G, and on the construction of arcs connecting these stars. The result is used to find the minimum set of arcs that transform an arbitrary acyclic digraph into a strongly connected digraph by selecting the edges connecting the stars in the minimum edge cover. This problem arose in the analysis of biotechnological solutions that increase the stability of the functioning of protein networks by introducing feedbacks into them.