Can any expert explain the reasoning behind the constraint in the following formulation of the minimum spanning tree?

To formulate the minimum-cost spanning tree (MST) problem as an LP, we associate a variable $x_e$ with every edge $e \in E$. Each spanning tree $T$ corresponds to its incidence vector $x^T$, which is defined by $x^T_e = 1$ if $T$ contains $e$ and $x^T_e = 0$ otherwise. Let $\Pi$ denote the set of all partitions of the vertex set $V$, and suppose that $\pi \in \Pi$. The rank $r(\pi)$ of $\pi$ is the number of parts of $\pi$. Let $E_\pi$ denote the set of edges whose ends lie in different parts of $\pi$. Consider the following LP: $$ \begin{align*} \min &\sum_{e \in E} c_ex_e \\ \text{s.t. } &\sum_{e \in E_\pi} x_e \geq r(\pi) - 1 \quad \forall \pi \in \Pi, \\ & x \geq 0. \\ \end{align*} $$

  • 2
    $\begingroup$ As I suggested the last time you asked a similar question, I suggest working through a small example by hand, and see what happens if you include that constraint and what happens if you leave it out. $\endgroup$ – D.W. Jan 16 '20 at 22:19
  • $\begingroup$ I tried but still not clear. $\endgroup$ – user3489173 Jan 17 '20 at 0:24
  • 2
    $\begingroup$ Cool, why don't you share with us a summary of what you've come up with and show some examples that illustrate why this is interesting/unclear? $\endgroup$ – D.W. Jan 17 '20 at 0:50

The constraint expresses the following fact:

Let $T$ be a spanning tree, and suppose that we partition the vertex set into $r$ parts. There are exactly $r-1$ edges of $T$ which connect different parts.

For example, if $T$ is a tree and $C,\overline{C}$ is a cut, then exactly one edge of $T$ crosses the cut, that is, connects $C$ and $\overline{C}$.

  • $\begingroup$ Thank you for your comment. My question was the reasoning behind the constraint, not what it means. Ie, my question was why such a constraint should hold. $\endgroup$ – user3489173 Jan 16 '20 at 21:50
  • $\begingroup$ Well, that's a nice exercise. $\endgroup$ – Yuval Filmus Jan 16 '20 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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