On the Complexity of the Minimum-($k,\rho$)-Shortcut Problem

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

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