Removing edges from a digraph to obtain the smallest digraph

93 Views Asked by At

Say that I have a connected digraph $D$ composed by $N$ nodes and $E$ edges, and a root node root. Assume now that I want to play the following game: I remove $K$ edges from $D$ (with $K < E$), and then remove any node that is not reachable from the root.

Which $K$ edges should I choose to have the smallest resulting graph $D$ at the end?

Can this game be reduced to any known graph problems?