I am studying a research paper which is concerned with finding paths from a source nodes to a single sink node keeping in mind 2 things.1.The security of the path.2.The optimality of the path.Research paper transmission cost minimization with vulnerability constraintThe vulnerability model of paper says that the link that is shared by greater number of paths is more vulnerable to be attacked by some attacker. For example if there are 5 source nodes and 1 sink node, and say there is a link shared by 3 out of 5 paths and a link shared by only 1 out of 5 paths, then the latter link is more secure.It basically defines the vulnerability of a link by the value of $No(e)$, where $e$ is the edge and it applies a constraint that the link cannot be used by more than $No(e)$ paths for the link to be secure, other wise it is likely to get attacked.Here are important points about the research paper.To guarantee network security, the constraint vulnerability for each  link $e$ is set to $No(e)$, which is a positive integer.$s$ is the single sink node and $P$ is the set of sources.Definition 1: An $s-P$ cut (Ecut) is defined as the set of links  satisfying that if these links are removed, node $s$ and nodes in set $P$  are disconnected, meaning all the sources will be disconnected from  the sink node. The weight of $s-P$ node cut is defined as $\sum{(No(e))}$ $\forall e \in$ cut $s-P$.The $s-P$ node cut with minimum weight is defined as $C_{min}$. This also  serves as the upper bound for the number of sources allowed to  transmit, or mathematically it means$$   |P| \leq C_{min}$$Up to this point I have understood it completely. The upper bound on $|P|$ can be very easily derived, by analysing the boundary condition. Suppose we allow exactly $C_{min}$ number of sources to transmit and $C_{min} = \sum{No(e)}$ for all the edges in the cut with minimum weight. Now say $No(e)$ paths go through first edge in the cut, No(e) paths go through second edge in the cut and so on. But if anywhere $No(e)+1$ paths go through an edge keeping everything same(or in other words having sources $C_{min} + 1$) then vulnerability constraint is broken as link can at most be used by $No(e)$ paths.Further the research paper is:Which I am not comfortable with isProposed AlgorithmsLet us use a strategy to convert undirected to directed graph with the  objective of devising an algorithm with the help of network flow  theory.For each link $(u,v)$ in graph, replace it by two directed arcs, $(u,v)$  and $(v,u)$, the cost of both arcs is same as cost of link in undirected  graph. Let us denote the new network with $G(N,A)$, $E$ being replaced by  $A$.Now for each directed arc $(u,v) \in A$, we define $f(u,v)$ as the current  unit flow from node $u$ to node $v$. We initialize $f(u,v)$ as $No(u,v)$.Algorithm 1: Computing the number of source nodes using each arc for the data transmission. I understood that the number of source nodes using an arc for data transmission(or the number of times an arc is being used in various paths) is $$r(u,v) = |No(u,v) - f(u,v)|$$But my question is why was the need for arcs, we could have applied the dijkstra on undirected graph and then could have also got this, what is that I am missing.Further the paper proposes that the cost $r(u,v)$ is added to each link in the undirected graph but does not specify whether both $r(u,v)$ and $r(v,u)$ is addedThe second alogirthm, which i could not understand as to why the deletion of links is happening and also minimal explanation in paper of it is given.Can somebody explain the second algorithm and its link with the first one and try to explain the bigger picture so that I can understand what is going on.
Graph algorithms for vulnerability and optimality of network
algorithms;graphs