5
$\begingroup$

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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Yes, it's possible.

It's trivially possible that every problem in P can be reduced to LP in polynomial time, for uninteresting reasons: given an instance of the decision problem, the reduction solves the decision problem (in polynomial time), then either outputs a feasible LP instance or an infeasible LP instance (where these instances are hardcoded). I realize that's pretty uninteresting and probably not what you wanted.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't think that this approach will work. In your answer, the key ingredient to `ensure' that we have a tree is to force that, for each node except for the root, there is exactly one edge leaving the node. However, this does not prevent the solution to contain several simple cycles in addition to a tree since these cycles fulfill the same properties. That's similar to the reason why we need subtour elimination constraints in the case of Hamilton, TSP, or the Most Negative Cycle problem. I doubt that we can get rid of this (exponential-sized) set of constraints. $\endgroup$
    – user1742364
    Commented Feb 23, 2017 at 11:40
  • $\begingroup$ @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? $\endgroup$
    – D.W. ♦
    Commented Feb 23, 2017 at 15:09
  • $\begingroup$ Maybe I am missing something as well...you claim that y_u = 1 means that the corresponding node is reachable from the root. However, it actually only models that some edge in the solution leaves u. For example, if we consider spanning trees, a solution in which y_u = 1 for each node u and in which the x-variables induce a tree plus a set of disjoint simple cycles would be feasible as well in my opinion since each node (except for the root node) has an outgoing edge. $\endgroup$
    – user1742364
    Commented Feb 23, 2017 at 17:19
  • $\begingroup$ @user1742364, you're right. Thank you! My mistake entirely -- and thank you for patiently explaining where I went wrong. I'll delete that eronneous answer to the other question, and remove the erroneous claim in this answer. Thanks again. $\endgroup$
    – D.W. ♦
    Commented Feb 23, 2017 at 19:44
0
$\begingroup$

There are IP formulations for MST with polynomially many constraints, see, e.g., "Optimal trees" by Magnati and Wolsey. For example, you can use the max-flow/min-cut theorem to find an equivalent formulation to the cut-based one that you mentioned: Replace each edge by two anti parallel arcs. Select one vertex as the root. Require that for each other vertex there is a unit flow from the root to this vertex. Very surprisingly, there are problems in P that you provably cannot formulate as an LP with polynomially many constraints. I would recommend the book "Integer programming" by Conforti et. al. for more Details.

Improve this answer
$\endgroup$

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.