The integer linear programming formulation for the multicut problem for the given graph $G = (V,E)$ and distinguished source-sink pairs of vertices $(s_1,t_1),...,(s_k,t_k)$ is:

\begin{alignat}{3} \text{minimize} & \quad \sum_{e \in E} c_ex_e \\ \text{subject to} &\quad \sum_{e\in P} x_e \geq 1, & \quad \forall P \in \mathcal{P}_i , 1 \leq i \leq k \\ & \quad x_e \in \{0,1\}, & \quad \forall e \in E \end{alignat}

where $c_e$ is the cost of edge $e$ and $\mathcal{P}_i$ is the set of all paths $P$ joining $s_i$ and $t_i$. The number of paths in the graph may be exponential in the the size of the input so the number of constraint in this formulation may be exponential. In the book The Design of Approximation Algorithms they provided a separation oracle for the LP relaxation of this ILP by allowing $x_e$ to be a positive real number. But it is also stated in the book that it is possible to give a LP with polynomial number of constraints, equivalent to the LP relaxation stated above i.e. any optimal solution to either one can be transformed in polynomial time to an optimal solution to the other one. What is the main idea to reduce the number of constraints?

EDIT: It seems to me that this question is quite relevant to the following post but I can't understand it clearly: Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.