patternMinor
Maximal Minimum Spanning Tree by Removing $k$ Edges
Viewed 0 times
edgesremovingminimummaximalspanningtree
Problem
The problem is as follows:
Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0
Repeat this $k$ times. This doesn't seem very efficient though. This would be something like $O(k \cdot n \cdot (n + m))$ I think. We could optimize this a bit by keeping track of an ordered set of edges on the cuts.
I am wondering if there exists an algorithm that is $O(km \log n)$ or better. Any approaches / advice would be appreciated.
Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0
- Determine the next smallest edge $e'$ spanning $T_1$ and $T_2$ in $G$.
- Keep track of $e$ such that it maximizes $w(e') - w(e)$.
Repeat this $k$ times. This doesn't seem very efficient though. This would be something like $O(k \cdot n \cdot (n + m))$ I think. We could optimize this a bit by keeping track of an ordered set of edges on the cuts.
I am wondering if there exists an algorithm that is $O(km \log n)$ or better. Any approaches / advice would be appreciated.
Solution
This is known as the $k$ most vital edges for the minimum spanning tree problem. It has been proved as NP-hard [1].
For fixed $k$, Weifa Liang proposed an $O\left(n^k\alpha((k+1)(n-1),n)\right)$ algorithm where $\alpha$ is a functional inverse of Ackermann’s function [2], and can be improved to $O\left(n^k\log\alpha((k+1)(n-1),n)\right)$ using Seth Pettie's sensitivity analysis [3].
[1] Frederickson, G. N., & Solis-Oba, R. (1999). Increasing the weight of minimum spanning trees. Journal of Algorithms, 33(2), 244-266.
[2] Liang, W. (2001). Finding the k most vital edges with respect to minimum spanning trees for fixed k. Discrete Applied Mathematics, 113(2-3), 319-327.
[3] Pettie, S. (2005, December). Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In International Symposium on Algorithms and Computation (pp. 964-973). Springer, Berlin, Heidelberg.
For fixed $k$, Weifa Liang proposed an $O\left(n^k\alpha((k+1)(n-1),n)\right)$ algorithm where $\alpha$ is a functional inverse of Ackermann’s function [2], and can be improved to $O\left(n^k\log\alpha((k+1)(n-1),n)\right)$ using Seth Pettie's sensitivity analysis [3].
[1] Frederickson, G. N., & Solis-Oba, R. (1999). Increasing the weight of minimum spanning trees. Journal of Algorithms, 33(2), 244-266.
[2] Liang, W. (2001). Finding the k most vital edges with respect to minimum spanning trees for fixed k. Discrete Applied Mathematics, 113(2-3), 319-327.
[3] Pettie, S. (2005, December). Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In International Symposium on Algorithms and Computation (pp. 964-973). Springer, Berlin, Heidelberg.
Context
StackExchange Computer Science Q#106457, answer score: 3
Revisions (0)
No revisions yet.