<p>We can get a $(2,2)$ bi-criteria approximation as follows (or more generally $(1+\varepsilon, 1 + 1/\varepsilon)$ bi-criteria approximation).</p>

<p>We may assume that we know the cost of the optimal solution. Denote it by $OPT$. Let 
$$w'(u,v) = \frac{w(u,v)}{OPT} + \frac{1}{k}.$$
Consider the optimal solution $(V_1, V_2)$. Then
$$\sum_{(u,v) \in E(V_1, V_2)} w'(u,v) = \sum_{(u,v) \in E(V_1, V_2)} \left(\frac{w(u,v)}{OPT} + \frac{1}{k}\right) = 1 + \frac{|E(V_1,V_2)|}{k} \leq 2.$$</p>

<p>Our algorithm finds the minimum directed $s$-$t$ cut $(V_1', V_2')$ in $G$ with edge weights $w'$. The cost of this cut is at most $2$. Therefore, the cut $(V_1', V_2')$ cuts at most
$$E(V_1', V_2') = \sum_{(u,v)\in E(V_1',V_2') } 1 \leq k \sum_{(u,v)\in E(V_1',V_2')} w'(u,v) \leq 2k$$
edges. The cost of the cut is at most
$$\sum_{(u,v)\in E(V_1',V_2')} w(u,v) \leq OPT \sum_{(u,v)\in E(V_1',V_2')} w'(u,v) \leq 2OPT.$$</p>

CC BY-SA 3.0
2013-03-27T11:48:15.153Z
Thanks a lot. Your algorithm is very interesting and insightful.
Unfortunately it seems that a bicriteria approximation algorithm is not enough for us, as we need every approximate solution to be feasible w.r.t the cardinality constraint.
Do you know if any such result is known in literature?

Thanks again!
Steven
CC BY-SA 3.0
2013-03-27T20:39:06.607Z
Using this approach, you can get $k$-approximation. Probably, you can also get $(k+1)/2$ approximation using LP. But getting anything better than that seems to be pretty difficult. In particular, there is an LP integrality gap for the natural LP relaxation. Let $V={s,t,x}$. Connect $s$ to $x$ with $(k+1)/2$ edges of weight 1 each, connect $x$ to $t$ with $k+1$ edges of weight 0. The optimal combinatorial solution has cost $(k+1)/2$. The optimal LP solution assign $x_e=2/(k+1)$ to edges from $s$ to $x$, and $x_e=1-2/(k+1)$ to edges from $x$ to $t$. Its cost is $1$. The gap is $(k+1)/2$.
Yury
CC BY-SA 3.0
2013-04-05T15:20:42.370Z
Thanks for your answer, what you say hints that it might be hard to develop a "good" monocreteria approximation for the problem as even the $(k+1)/2$-apx can be fairly bad.
Thanks again for your insights! :)
Steven
CC BY-SA 3.0
2013-03-25T18:30:19.227Z
2013-03-25T18:30:19.227Z
Yury
<p>We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature.</p>

<p>The problem is defined as follows:</p>

<p><strong>Instance:</strong> A directed graph $G=(V,E)$, a cost function $w : E \to \mathbb{R_0^+}$, two vertices $s,t \in V$ and an integer $k$.</p>

<p><strong>Solution:</strong> An $s$-$t$-cut, i.e. a partition of $V$ into two sets $V_1, V_2$ such that $s \in V_1$, $t \in V_2$ and the number of edges that cross the cut is at most $k$, i.e. $|\{ (u,v) \in E: u \in V_1, v \in V_2 \}| \le k$.</p>

<p><strong>Measure (to minimize):</strong> The cost of the cut: $$ \sum_{ (u,v) \in E : u \in V_1, v \in V_2 } w(u,v) $$</p>

<p>In "<a href="https://www.lri.fr/~bentz/docs_inria/JDA_09.pdf">Cardinality constrained and multicriteria (multi)cut problems</a>" the autors prove that this problem is strongly NP-Hard even for undirected graphs.</p>

<p>We are mainly interested in approximation algorithms for directed graphs, but approximation results for the undirected case might also be useful.</p>

<p>Thank you for any insights.</p>

CC BY-SA 4.0
2019-08-10T21:36:23.130Z
Sorry it is not an answer, actually I want to ask how to transfer the bi-criteria approximation into the mono-criteria approximation? please forgive me.
Jianhao Ma
<ds.algorithms><graph-theory><co.combinatorics><graph-algorithms><approximation-algorithms>
Approximation algorithms for Directed Minimum Cut with Cardinality Constraints
Steven
# Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

(Asked by: username_0 on 2013-03-25)

We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature.

The problem is defined as follows:

**Instance:** A directed graph $G=(V,E)$, a cost function $w : E \to \mathbb{R\_0^+}$, two vertices $s,t \in V$ and an integer $k$.

**Solution:** An $s$-$t$-cut, i.e. a partition of $V$ into two sets $V\_1, V\_2$ such that $s \in V\_1$, $t \in V\_2$ and the number of edges that cross the cut is at most $k$, i.e. $|\{ (u,v) \in E: u \in V\_1, v \in V\_2 \}| \le k$.

**Measure (to minimize):** The cost of the cut: $$ \sum\_{ (u,v) \in E : u \in V\_1, v \in V\_2 } w(u,v) $$

In "[Cardinality constrained and multicriteria (multi)cut problems](https://www.lri.fr/~bentz/docs_inria/JDA_09.pdf)" the autors prove that this problem is strongly NP-Hard even for undirected graphs.

We are mainly interested in approximation algorithms for directed graphs, but approximation results for the undirected case might also be useful.

Thank you for any insights.

**Tags:** ds.algorithms, graph-theory, co.combinatorics, graph-algorithms, approximation-algorithms
> **Comments:**
> **username_1**: Sorry it is not an answer, actually I want to ask how to transfer the bi-criteria approximation into the mono-criteria approximation? please forgive me.  

---

## 1 answers

### Answer by username_2 on 2013-03-25. Score: 11

We can get a $(2,2)$ bi-criteria approximation as follows (or more generally $(1+\varepsilon, 1 + 1/\varepsilon)$ bi-criteria approximation).

We may assume that we know the cost of the optimal solution. Denote it by $OPT$. Let
$$w'(u,v) = \frac{w(u,v)}{OPT} + \frac{1}{k}.$$
Consider the optimal solution $(V\_1, V\_2)$. Then
$$\sum\_{(u,v) \in E(V\_1, V\_2)} w'(u,v) = \sum\_{(u,v) \in E(V\_1, V\_2)} \left(\frac{w(u,v)}{OPT} + \frac{1}{k}\right) = 1 + \frac{|E(V\_1,V\_2)|}{k} \leq 2.$$

Our algorithm finds the minimum directed $s$-$t$ cut $(V\_1', V\_2')$ in $G$ with edge weights $w'$. The cost of this cut is at most $2$. Therefore, the cut $(V\_1', V\_2')$ cuts at most
$$E(V\_1', V\_2') = \sum\_{(u,v)\in E(V\_1',V\_2') } 1 \leq k \sum\_{(u,v)\in E(V\_1',V\_2')} w'(u,v) \leq 2k$$
edges. The cost of the cut is at most
$$\sum\_{(u,v)\in E(V\_1',V\_2')} w(u,v) \leq OPT \sum\_{(u,v)\in E(V\_1',V\_2')} w'(u,v) \leq 2OPT.$$

> **Comments:**
> **username_0**: Thanks a lot. Your algorithm is very interesting and insightful. Unfortunately it seems that a bicriteria approximation algorithm is not enough for us, as we need every approximate solution to be feasible w.r.t the cardinality constraint. Do you know if any such result is known in literature?  Thanks again!  
> **username_2**: Using this approach, you can get $k$-approximation. Probably, you can also get $(k+1)/2$ approximation using LP. But getting anything better than that seems to be pretty difficult. In particular, there is an LP integrality gap for the natural LP relaxation. Let $V={s,t,x}$. Connect $s$ to $x$ with $(k+1)/2$ edges of weight 1 each, connect $x$ to $t$ with $k+1$ edges of weight 0. The optimal combinatorial solution has cost $(k+1)/2$. The optimal LP solution assign $x_e=2/(k+1)$ to edges from $s$ to $x$, and $x_e=1-2/(k+1)$ to edges from $x$ to $t$. Its cost is $1$. The gap is $(k+1)/2$.  
> **username_0**: Thanks for your answer, what you say hints that it might be hard to develop a "good" monocreteria approximation for the problem as even the $(k+1)/2$-apx can be fairly bad. Thanks again for your insights! :)  

---

