用于删除最少边缘以强制增加未加权无向图中最短路径长度的算法

Question

给定一个未加权无向图的邻接矩阵，是否有一种有效的方法(多项式算法)来扩展/增加任何给定的两个节点 s 和 t 之间的最短路径的长度？

示例:

在下面的示例中，从顶点 s=1 到顶点 t=5 有 5 条不同的“最短路径”，每条路径的长度为 3。我想删除最少数量的边，以便最短路径长度被强制为变成4个或更多。 (断开图形是可以的。)

邻接矩阵(扩展以更正示例):

 0 1 0 0 0 1 1 1 0 1 0 
 1 0 1 1 0 0 0 0 0 0 0  
 0 1 0 0 1 0 0 0 0 0 1 
 0 1 0 0 1 1 0 0 0 0 0  
 0 0 1 1 0 1 0 0 0 0 0 
 1 0 0 1 1 0 0 0 1 0 0 
 1 0 0 0 0 0 0 0 1 0 0 
 1 0 0 0 0 0 0 0 1 0 0 
 0 0 0 0 0 1 1 1 0 0 0
 1 0 0 0 0 0 0 0 0 0 1
 0 0 1 0 0 0 0 0 0 1 0 

代表这张图:

强制最短路径长度从 3 增加到 4 的最小成本是移除两条边 (1,2) 和 (5,9)

目标:

您能否给出一个通用算法的任何想法，该算法可以找到在一般情况下必须删除的边集？

---

更正:正如我在评论中指出的那样，这个例子并不完整。通过添加另外两个顶点 10 和 11(以红色显示)，该示例得以挽救。

Answer 1

输入:G = (V,E)、顶点s、t和正整数d。

问题:最小化需要删除的边数，使得 dist(s,t) >= d。

这个问题对于 d > 3 是 NP-hard，对于 d 的其他值是多项式可解的。

问题是 FPT 在距离 d 和允许删除的边数 k 上参数化:算法如下:找到长度最多为 d 的 (s,t)-path 并在 d 边上分支你可以删除。这导致算法运行时间为 O(d^k * n^2)。

当仅由 d(resp.just k)参数化时，它是 para-NP-complete(resp.W[1]-hard)。

引用:有界长度的路径及其切割:参数化的复杂性和算法，Golovach，P.A.和 Thilikos, D.M.，离散优化第 8 卷，第 1 期，第 72 - 86 页，2011 年，出版商 E​​lsevier。