Inverse max $$+$$ + sum spanning tree problem under Hamming distance by modifying the sum-cost vector

The inverse max $$+$$ + sum spanning tree (MSST) problem is considered by modifying the sum-cost vector under the Hamming Distance. On an undirected network G(V, E, w, c), a weight w(e) and a cost c(e) are prescribed for each edge $$e\in E$$ e ∈ E . The MSST problem is to find a spanning tree $$T^*$$ T ∗ which makes the combined weight $$\max _{e\in T}w(e)+\sum _{e\in T}c(e)$$ max e ∈ T w ( e ) + ∑ e ∈ T c ( e ) as small as possible. It can be solved in $$O(m\log n)$$ O ( m log n ) time, where $$m:=|E|$$ m : = | E | and $$n:=|V|$$ n : = | V | . Whereas, in an inverse MSST problem, a given spanning tree $$T_0$$ T 0 of G is not an optimal MSST. The sum-cost vector c is to be modified to $$\bar{c}$$ c ¯ so that $$T_0$$ T 0 becomes an optimal MSST of the new network $$G(V,E,w,\bar{c})$$ G ( V , E , w , c ¯ ) and the cost $$\Vert \bar{c}-c\Vert $$ ‖ c ¯ - c ‖ can be minimized under Hamming Distance. First, we present a mathematical model for the inverse MSST problem and a method to check the feasibility. Then, under the weighted bottleneck-type Hamming distance, we design a binary search algorithm whose time complexity is $$O(m log^2 n)$$ O ( m l o g 2 n ) . Next, under the unit sum-type Hamming distance, which is also called $$l_0$$ l 0 norm, we show that the inverse MSST problem (denoted by IMSST $$_0$$ 0 ) is $$NP-$$ N P - hard. Assuming $${\textit{NP}} \nsubseteq {\textit{DTIME}}(m^{{\textit{poly}} \log m})$$ NP ⊈ DTIME ( m poly log m ) , the problem IMSST $$_0$$ 0 is not approximable within a factor of $$2^{\log ^{1-\varepsilon } m}$$ 2 log 1 - ε m , for any $$\varepsilon >0$$ ε > 0 . Finally, We consider the augmented problem of IMSST $$_0$$ 0 (denoted by AIMSST $$_0$$ 0 ), whose objective function is to multiply the $$l_0$$ l 0 norm $$\Vert \beta \Vert _0$$ ‖ β ‖ 0 by a sufficiently large number M plus the $$l_1$$ l 1 norm $$\Vert \beta \Vert _1$$ ‖ β ‖ 1 . We show that the augmented problem and the $$l_1$$ l 1 norm problem have the same Lagrange dual problems. Therefore, the $$l_1$$ l 1 norm problem is the best convex relaxation (in terms of Lagrangian duality) of the augmented problem AIMSST $$_0$$ 0 , which has the same optimal solution as that of the inverse problem IMSST $$_0$$ 0 .