We are given as input an undirected graph $G=(V,E)$, weights $w_e \ge 0$ for all $e\in E$ and an positive integer $k$. We aim to select a set of edges with the minimum weight, such that the cut set of every small cut are hitted. A cut is defined as a subset of $V$. A small cut is defined as a cut whose cut set contains at most $k$ edges. The cut set of a cut $S\subseteq V$, denoted by $\delta(S)$, is the set of edges having exactly one endpoint in $S$.

Using $x_e$ to denote whether edge $e$ is chosen($x_e=1$) or not($x_e=0$), this problem can be formulated as an integer programming:

$$\begin{array}{rcl} &\min \sum_{e\in E} x_e w_e\\ \\ &\sum_{e\in \delta(S)} x_e \ge 1 & \forall S\subseteq V \text{ s.t. } \delta(S)\le k \\ &x_e\in \{0,1\} \quad & \forall e\in E \end{array}$$

Considering its similarity to set cover porblem, I try designing approximation algorithms by rounding the optimal solution for the linear programming relaxation of above IP. However, there is, exponentially many constraints. In order to slove the LP relaxation by ellipsoid method, a separation oracle is needed. I try to design a separation oracle by the max-flow min-cut theorem but failed.

Is it possible to design a separation oracle for the LP relaxation by the max-flow min-cut theorem or any other way? Or any suggestions on designing approximation algorithms for this problem?

  • 1
    $\begingroup$ By Karger's algorithm the number of min cuts is at most $\binom{n}{2}$ (link), so the number of constraints is in fact polynomial. $\endgroup$ – smapers Jun 2 '20 at 6:31
  • 1
    $\begingroup$ We can assume graph is connected, hence mincut value is at least 1. The number of $\alpha$-approximate mincuts is known to be at most $n^{O(\alpha)}$ and these can be also found in time $n^{O(\alpha)}$. Here $\alpha = k$ and hence one has a separation oracle that runs in time $n^{O(k)}$. $\endgroup$ – Chandra Chekuri Jun 2 '20 at 13:59
  • $\begingroup$ The following paper on Capacitated Network Design that I co-wrote maybe relevant to your question and problem. link.springer.com/article/10.1007/s00453-013-9862-4 $\endgroup$ – Chandra Chekuri Jun 2 '20 at 15:21
  • 1
    $\begingroup$ The paper Multicriteria Minimum Cuts by Armon and Zwick seems to give an $O(mn^4)$-time algorithm for the oracle (e.g. finding a minimum-weight small cut). Note that you can also use a Lagrangian-relaxation algorithm on the dual (with the same oracle). It may be more practical than Ellipsoid, if you can tolerate $(1+\epsilon)$-approximate solutions. $\endgroup$ – Neal Young Jun 2 '20 at 16:07
  • $\begingroup$ Good ref @NealYoung. $\endgroup$ – Chandra Chekuri Jun 2 '20 at 16:27

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.