Inverse Minimum Spanning Tree Problems

In this chapter, we delve into the inverse minimum spanning tree (IMST) problems under various norm constraints, including the l 1 $$l_1$$ , l ∞ $$l_\infty $$ norms and the weighted Hamming distance. We present mathematical formulations and propose efficient algorithms tailored to each scenario. The bounded IMST problem under the unit l 1 $$l_1$$ norm is reformulated as a maximum flow problem, which can be effectively solved within O ( m 8 log m ) $$O(m^8 \log m)$$ . In contrast, the unbounded IMST problem under the unit l 1 $$l_1$$ norm is transformed into an unbalanced assignment problem, solvable in O ( n 2 m ) $$O(n^2m)$$ time. Furthermore, this problem is also cast as a minimum cost flow problem, solvable in O ( n 2 log n ) $$O(n^2 \log n)$$ time. When considering the unbounded IMST problem under the weighted l 1 $$l_1$$ norm, it is mapped onto an unbalanced transportation problem, with a solution time of O ( n 2 m log ( nc ) ) $$O(n^2m\log (nc))$$ , where C = max { | c j | : a j ∈ A } $$C = \max \{|c_j| : a_j \in A\}$$ . The unbounded IMST problem under the unit l ∞ $$l_\infty $$ norm is more straightforward, admitting a solution in O ( n 2 ) $$O(n^2)$$ time. For the bounded IMST problem under the weighted sum Hamming distance, we have transformed it into a minimum-weight node cover problem of a bipartite graph, which can be addressed in O ( n 3 m ) $$O(n^3m)$$ time. Employing the binary method, the constrained bounded IMST problem under the weighted bottleneck Hamming distance is also transformed into a minimum-weight node cover problem of a bipartite graph, with a solution time of O ( n 3 m log m ) $$O(n^3m\log m)$$ .