Shortcutting directed and undirected networks with a degree constraint

Shortcutting is the operation of adding edges to a network with the intent to decrease its diameter. We are interested in shortcutting networks while keeping degree increases in the network bounded, a problem first posed by Chung and Garey. Improving on a result of Bokhari and Raza we show that, for any δ≥1, every undirected graph G can be shortcut in linear time to a diameter of at most O(log1+δn) by adding no more than O(n/log1+δn) edges such that degree increases remain bounded by δ. The result extends an estimate due to Alon et al. for the unconstrained case. Degree increases can be limited to 1 at only a small extra cost. For strongly connected, bounded-degree directed graphs Flaxman and Frieze proved that, if ϵn random arcs are added, then the resulting graph has diameter O(lnn) with high probability. We prove that O(n/lnn) edges suffice to shortcut any strongly connected directed graph to a graph with diameter less than O(lnn) while keeping the degree increases bounded by O(1) per node. The result is proved in a stronger, parameterized form. For general directed graphs with stability number α, we show that all distances can be shortcut to O(α⌈lnnα⌉) by adding only 4nlnn/α+αϕ edges while keeping degree increases bounded by at most O(1) per node, where ϕ is equal to the so-called feedback-dimension of the graph. Finally, we prove bounds for various special classes of graphs, including graphs with Hamiltonian cycles or paths. Shortcutting with a degree constraint is proved to be strongly NP-complete and W[2]-hard, implying that the problem is neither likely to be fixed-parameter tractable nor efficiently approximable unless FPT=W[2].