Given a directed network G $=($V$,$ E$)$ with a root node s and a set of

terminals T $$ V $,$ we want to disconnect many terminals from s while cutting relatively few edges.

For a set of edges F $$ E$,$ let n$($F $)$ denote the number of nodes t in T such that there is no s $$ t

path in the subgraph $($V$,$ E $$ F $).$ Your task is to design a polynomial$-$time algorithm to find a

set F of edges that maximizes the quantity n$($F $)|$F $|.$ Prove its correctness and perform time

complexity analysis. $($Note that setting F equal to the empty set is an option.$)$

$1$