# Optimal Blocking of Undesired Nodes in Digraph

Tsitsiashvili Gurami*

Institute for Applied Mathematics FEB RAS, Russia

Received Date: April 14, 2020;  Published Date: May 18, 2020

#### Abstract

This paper provides a complete solution to the problem of minimizing the number of edges in the protein network, the removal of which blocks all paths that pass through a set of undesirable nodes. The minimization problem is reduced to the problem of minimum cut and maximum flow in a specially constructed weighted digraph with a source and a drain.

Keywords: Digraph;Ford-Fulkerson Theorem;Sub-graph; Optimal Blocking.

#### Problem Statement

Consider a digraphG, representing a protein network with finite sets V and E of nodes and edges respectively. In the setV there is a subset W ⊂V of undesired nodes. Contrast to the set W the subset Q ⊆W of output nodes from which edges exit to the subset U =V \W and the subset P ⊆W of input nodes to which edges enter from U.

Denoten( p) a number of edges, entering to p∈P from U, and N(q) a number of edges, exiting from q∈Q to U. Our problem is to find subsets so that their removing from the sets breaks all paths, which transit to W from the set U , pass through W and exit back. And the number of edges to delete is minimal: In  the digraphG*with the nodes set W and edges, connecting them in digraph G, is constructed. The set W of the digraph G* nodes is divided into classes of cyclical equavalence (clusters) and a relation of partial order between these clusters is defined a* ≥ b* if in the digraph G* there is a path from clustera*to clusterb*. A bipartite digraphΓ with the set of input clusters P* , the set of output clustersQ* , and the set of edges: R: (p*,q*), if p*≥q*, if p* ≥ q* This design allows for simultaneous input and output clusters, to be included into the sets P* , Q* and an edge between them is to be introduced.

The bipartite digraphΓ is divided into connectivity componenets (after deleting of edges direction) and isolated clusters are removed. In each connectivity component input or output edges are removed, depending on which number is less. But this solution is not optimal.

#### Search for an Optimal Solution by the Ford- Fulkerson Theorem  The Ford-Fulkerson algorithm  with improved additions of Edmonds-Carp  and Dinits  is used to find the maximum flow f . All algorithms for determining the maximum flow consistently find paths that increase the amount of flow. For the maximum flow found, the minimum cut is determined using well known recurrent algorithm .

None.

#### Conflict of Interest

The authors declare no conflict of interest exists.

Article Details
Citation
Keywords
Scroll to
Scroll to Top