Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST

In the internet I only could find the LP formulations, but no motivation for the constraints.

The need for topological constraints seems contradictory to me, because demanding the number of edges to be $n-1$, together with the requirement, that at least one edge be adjacent to each vertex, suffice for a connected graph of $n$ vertices to ensure connectivity and a tree topology. Fractional solutions seem also counter-intuitive.

So, where does the need for topoligical constraints in the LP formulation of the MST problem actually come from, resp. when does it arise?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I'm not sure that I understand your question properly but the constraints you propose do not ensure connectivity. As far as I guess, you propose to use the following polytope to describe the spanning trees of a graph $G(V,E): \sum_{e\in E} x_e=|V|-1; \sum_{v\in e\in E} x_e\geq 1$ for all $v\in V$ and $x_e\geq 0, e\in E$. But then, for instance, in $K_5$ a triangle and a disjoint edge constitute a vertex of your polytope.

share|improve this answer
    
thanks for the clarification –  Manfred Weis Jul 22 '13 at 10:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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