1
$\begingroup$

I am trying to understand whether this intuition is true or false.

Given a minimum spanning tree (MST) of an undirected positive graph $G=(V,E)$.

Consider a MST $T\subseteq G$. Removing any single edge from $T$ would generate two separate Steiner trees with nodes partitioned in $V_1,V_2$. Are these minimal Steiner trees for the subsets of terminals $V_1,V_2$?

$\endgroup$
2
  • $\begingroup$ Do you mean removing any single edge? $\endgroup$
    – prubin
    Commented Apr 11, 2023 at 18:29
  • $\begingroup$ No, just one, so to create 2 trees. There was a type. Thanks! $\endgroup$ Commented Apr 11, 2023 at 18:31

1 Answer 1

1
$\begingroup$

I think the answer is yes, but I recommend triple-checking my logic. I assume by "positive graph" you mean positive edge weights.

I'll equate a tree with a set of edges from $E$ and use the notation $\ell(\hat{E})$ to be the sum of the edge weights for any subset $\hat{E} \subseteq E$ of edges. A key observation is that in an undirected graph with positive edge weights, any minimum weight subgraph covering all vertices must be acyclic (else you could reduce weight by removing a cycle), so a MST is a minimum weight connected cover of the vertices.

Let $T\subseteq E$ be your MST, let $\bar{e}$ be the edge you delete, and let $T_1$ and $T_2$ be the resulting subtrees (so that $T=T_{1}\dot{\cup}\left\{ \bar{e}\right\} \dot{\cup}T_{2}$). Now suppose $T_1$ is not a Steiner tree for the terminals $V_1.$ That means there is a set of nodes $\hat{V}\subseteq V_2$ from the other subtree that you can "borrow" to produce a tree $\hat{T}$ connecting all the nodes in $V_1\dot{\cup}\hat{V}$ such that $\ell(\hat{T}) < \ell(T_1).$ In that case, the set of edges $E^* = \hat{T} \cup T_2$ produces a connected graph (not necessarily a tree) covering all of $V$ (because all nodes in $V_1$ are connected by $\hat{T},$ all nodes in $V_2$ are connected by $T_2,$ and at least one node in $V_1$ is connected to at least one node in $\hat{V} \subseteq V_2$ via $\hat{T}$). The sum of the edge weights in $E^*$ is $$\ell(E^*) = \ell(\hat{T}) + \ell(\hat{T_2}) < \ell(T_1) + \ell(T_2) = \ell(T),$$ contradicting $T$ being a MST.

$\endgroup$
2
  • $\begingroup$ Thank you. Yes, this reasoning made me think that MST have also this property. It seems like there is no interest though in such a property. Do you have any reference? $\endgroup$ Commented Apr 11, 2023 at 22:54
  • $\begingroup$ Sorry, no, I do not have any references. $\endgroup$
    – prubin
    Commented Apr 12, 2023 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.