Undirected min cut has a well known poly sized LP formulation by expressing the problem as one of finding a certain metric on the vertices minimizing the sum of distances on edges. Can this be extended to directed min cut? If not, is there a different, simple, poly-sized LP for the problem?

  • $\begingroup$ I don't see what the existence of an NC reduction has to do with the problem. "Is not the empty string" is P-complete under P reductions, but saying that this captures SDPs because you can solve the SDP first is not an interesting statement by any stretch of the imagination. I tried to make it clear I'm looking for an encoding not quite as unhelpful. $\endgroup$ – user58140 Sep 10 '16 at 15:58
  • $\begingroup$ OK. Can you be a bit more precise about what the problem statement for directed min cut is? What are the inputs and what's the desired output? Is it: given a directed graph $G$ and vertices $s,t$, find the minimum $s,t$-cut? Or is it: given a graph $G$, find the minimum cut overall? If the former, what's wrong with using the max-flow-min-cut theorem to reduce to network flow, then reduce from there to LP? What have you tried? Also, if you want to know whether that specific "well known" formulation can be extended, it would help to sketch it in a self-contained way. $\endgroup$ – D.W. Sep 11 '16 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.