New Applied Problems in the Theory of Acyclic Digraphs

Abstract

The following two optimization problems on acyclic digraph analysis are solved. The first of them consists of determining the minimum (in terms of volume) set of arcs, the removal of which from an acyclic digraph breaks all paths passing through a subset of its vertices. The second problem is to determine the smallest set of arcs, the introduction of which into an acyclic digraph turns it into a strongly connected one. The first problem was solved by reduction to the problem of the maximum flow and the minimum section. The second challenge was solved by calculating the minimum number of input arcs and determining the smallest set of input arcs in terms of the minimum arc coverage of an acyclic digraph. The solution of these problems extends to an arbitrary digraph by isolating the components of cyclic equivalence in it and the arcs between them.

Keywords

• acyclic digraph
• maximal flow
• minimal cut
• minimal arc cover
• bipartite digraph