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

<p>Using <span class="math-container">$x_e$</span> to denote whether edge <span class="math-container">$e$</span> is chosen(<span class="math-container">$x_e=1$</span>) or not(<span class="math-container">$x_e=0$</span>), this problem can be formulated as an integer programming:</p>

<p><span class="math-container">$$\begin{array}{rcl}
&amp;\min \sum_{e\in E} x_e w_e\\ \\
&amp;\sum_{e\in \delta(S)} x_e \ge 1 &amp; \forall S\subseteq V \text{ s.t. } \delta(S)\le k \\
&amp;x_e\in \{0,1\} \quad &amp; \forall e\in E 
\end{array}$$</span></p>

<p>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. </p>

<p>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?  </p>

CC BY-SA 4.0
2020-06-02T06:31:04.743Z
By Karger's algorithm the number of min cuts is at most $\binom{n}{2}$ ([link](https://en.wikipedia.org/wiki/Karger%27s_algorithm)), so the number of constraints is in fact polynomial.
smapers
CC BY-SA 4.0
2020-06-02T13:59:36.373Z
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)}$.
Chandra Chekuri
CC BY-SA 4.0
2020-06-02T15:21:03.463Z
The following paper on Capacitated Network Design that I co-wrote maybe relevant to your question and problem. https://link.springer.com/article/10.1007/s00453-013-9862-4
Chandra Chekuri
CC BY-SA 4.0
2020-06-02T16:07:15.940Z
The paper [Multicriteria Minimum Cuts](https://scholar.google.com/scholar?hl=en&as_sdt=1%2C22&q=Multicriteria+Global+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.
Neal Young
CC BY-SA 4.0
2020-06-02T16:27:03.293Z
Good ref @NealYoung.
Chandra Chekuri
<approximation-algorithms><linear-programming><integer-programming>
Separation oracle for hitting all small cut on a graph?
Mengfan Ma
# Separation oracle for hitting all small cut on a graph?

(Asked by: username_0 on 2020-06-02)

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?

**Tags:** approximation-algorithms, linear-programming, integer-programming

> **Comments:**
> **username_1**: By Karger's algorithm the number of min cuts is at most $\binom{n}{2}$ ([link](https://en.wikipedia.org/wiki/Karger%27s_algorithm)), so the number of constraints is in fact polynomial.  
> **username_2**: 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)}$.  
> **username_2**: The following paper on Capacitated Network Design that I co-wrote maybe relevant to your question and problem. https://link.springer.com/article/10.1007/s00453-013-9862-4  
> **username_3**: The paper [Multicriteria Minimum Cuts](https://scholar.google.com/scholar?hl=en&as_sdt=1%2C22&q=Multicriteria+Global+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.  
> **username_2**: Good ref @NealYoung.  

---

## 0 answers

