# Minimum spanning tree formulation as integer program

The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a constraint for every subset of vertices, so the number of constraints would be exponential.

That makes me wonder, is it is possible to write down the constraints for a IP corresponding to MST such that the number of constraints is polynomial in the number of vertices? Furthermore, if it is possible, does it hold that every problem in P can be written as a LP with at most polynomial number of constraints?

Thank you very much!

• @user1742364, my approach also requires that every vertex is reachable from the root (see the $y$-variables at the link). Thus, the solution can't contain a simple cycle: it'd have to be disjoint from the tree, and then those vertices wouldn't be reachable. That takes care of your concern about cycles, I think. Have I missed something? – D.W. Feb 23 '17 at 15:09