<p>As Yury says, the problem is known as the Sparsest Cut. See Theorem 1.3 in &quot;Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut&quot; by Ambühl, Mastrolilli, and Svensson:</p>
<blockquote>
<p>Let <span class="math-container">$\epsilon &gt; 0$</span> be an arbitrarily small constant. If there is a PTAS for Sparsest Cut, Minimum Linear Arrangement, or Maximum Edge Biclique, then there is a (probabilistic) algorithm that decides whether a given SAT instance of size <span class="math-container">$n$</span> is satisfiable in time <span class="math-container">$2^{n^\epsilon}$</span>.</p>
</blockquote>
<p>So, PTAS seems unlikely since this almost (up to randomization) contradicts ETH. Maybe a stronger result exists.</p>

CC BY-SA 4.0
2024-09-11T18:01:33.017Z
2024-09-11T18:01:33.017Z
Dmitry
<p>Consider the task of clustering a graph, modelled as the balanced cut problem:</p>
<blockquote>
<p>Input: <span class="math-container">$G = (V, E)$</span> simple graph</p>
<p>Output: <span class="math-container">$S^* \subseteq V$</span> such that <span class="math-container">$S^* = \arg\min_{S \subseteq V} h(S)$</span>.
Here, <span class="math-container">$h(S)$</span> is the edge expansion of <span class="math-container">$S$</span> with respect to the graph <span class="math-container">$G$</span>,
<span class="math-container">$h(S) = |\{ \{v, v'\} \in E \mid v \in S, v' \in V \setminus S\}|/\min\{|S|, |V\setminus S|\}$</span>.</p>
</blockquote>
<p>The task is known to be NP-hard, see e.g. <a href="https://link.springer.com/chapter/10.1007/3-540-57182-5_65" rel="nofollow noreferrer">Wagner D., Wagner F. (1993) Between Min Cut and Graph Bisection</a>. Is it known in the literature whenever the task is APX or PTAS? In particular, do the Cheeger's inequalities and <a href="https://proceedings.mlr.press/v40/Peng15.html" rel="nofollow noreferrer">subsequent works in spectral clustering</a> contribute in this direction?</p>

CC BY-SA 4.0
2024-09-11T15:10:32.627Z
This problem is known as the Sparsest Cut problem (with uniform demands) and has been extensively studied. The state of the art algorithm by Arora, Rao, and Vazirani gives an $O(\sqrt{\log n})$ approximation. There are also algorithms for closely related problems such Minimum Bisection and Balanced Cut.
Yury
<approximation-hardness><clustering>
Approximations of graph clustering
incud
# Approximations of graph clustering

(Asked by: username_0 on 2024-09-11)

Consider the task of clustering a graph, modelled as the balanced cut problem:

> Input: $G = (V, E)$ simple graph
>
> Output: $S^\* \subseteq V$ such that $S^\* = \arg\min\_{S \subseteq V} h(S)$.
> Here, $h(S)$ is the edge expansion of $S$ with respect to the graph $G$,
> $h(S) = |\{ \{v, v'\} \in E \mid v \in S, v' \in V \setminus S\}|/\min\{|S|, |V\setminus S|\}$.

The task is known to be NP-hard, see e.g. [Wagner D., Wagner F. (1993) Between Min Cut and Graph Bisection](https://link.springer.com/chapter/10.1007/3-540-57182-5_65). Is it known in the literature whenever the task is APX or PTAS? In particular, do the Cheeger's inequalities and [subsequent works in spectral clustering](https://proceedings.mlr.press/v40/Peng15.html) contribute in this direction?

**Tags:** approximation-hardness, clustering

> **Comments:**
> **username_1**: This problem is known as the Sparsest Cut problem (with uniform demands) and has been extensively studied. The state of the art algorithm by Arora, Rao, and Vazirani gives an $O(\sqrt{\log n})$ approximation. There are also algorithms for closely related problems such Minimum Bisection and Balanced Cut.  

---

## 1 answers

### Answer by username_2 on 2024-09-11. Score: 4 | Accepted answer

As username_1 says, the problem is known as the Sparsest Cut. See Theorem 1.3 in "Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut" by Ambühl, Mastrolilli, and Svensson:

> Let $\epsilon > 0$ be an arbitrarily small constant. If there is a PTAS for Sparsest Cut, Minimum Linear Arrangement, or Maximum Edge Biclique, then there is a (probabilistic) algorithm that decides whether a given SAT instance of size $n$ is satisfiable in time $2^{n^\epsilon}$.

So, PTAS seems unlikely since this almost (up to randomization) contradicts ETH. Maybe a stronger result exists.


---

