Shortcutting directed and undirected networks with a degree constraint

Abstract

Short-cutting is the operation of adding edges to a network with the intent to decrease its diameter. We are interested in short-cutting graphs while keeping degree increases bounded, a problem first posed by Chung and Garey. We prove sharp bounds for the problem, both in general and for special classes of graphs. Shortcutting with a degree constraint is proved to be NP-complete and W2-hard. Many other bounds are shown.