2
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
0

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.