On the Complexity of the Minimum-($k,\ddot{I}$)-Shortcut Problem

Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt +1

We consider the Minimum-$(k,\ddot{I})$-$\mathrm{Shortcut}$ problem ($\min (k,\ddot{I})\text{-}\mathrm{Shortcut}$), where the goal is to find the smallest set of shortcut edges such that every v…