Shortcutting directed and undirected networks with a degree constraint

详细信息    查看全文

• 作者：Richard B. Tan^a ; ^{rbtan@usao.edu} ; Erik Jan van Leeuwen^b ; ^{erikjan@mpi-inf.mpg.de} ; Jan van Leeuwen^c ; ^{J.vanLeeuwen1@uu.nl}
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：31 March 2017
• 年：2017
• 卷：220
• 期：Complete
• 页码：91-117
• 全文大小：687 K
• 卷排序：220

文摘

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δ≥1, every undirected graph GG can be shortcut in linear time to a diameter of at most O(log1+δn)O(log1+δn) by adding no more than O(n/log1+δn)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 11 at only a small extra cost. For strongly connected, bounded-degree directed graphs Flaxman and Frieze proved that, if ϵnϵn random arcs are added, then the resulting graph has diameter O(lnn)O(lnn) with high probability. We prove that O(n/lnn)O(n/lnn) edges suffice to shortcut any strongly connected directed graph to a graph with diameter less than O(lnn)O(lnn) while keeping the degree increases bounded by O(1)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)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]W[2]-hard, implying that the problem is neither likely to be fixed-parameter tractable nor efficiently approximable unless FPT=W[2]FPT=W[2].