4
$\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!

$\endgroup$
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.

$\endgroup$
  • $\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 Feb 23 '17 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. Feb 23 '17 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 Feb 23 '17 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. Feb 23 '17 at 19:44

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.