Let $G=(V(G), E(G))$ be a graph on $n$ vertices and let $S$ be a subset of $V(G)$. The boundary of $S$, denoted by $\partial S$, is the set of edges $(i, j)$ such that $i \in S$ and $j \in V(G) \setminus S$.  

The expansion ratio of $G$, denoted by $h(G)$, is
\begin{equation}
h(G)= \min\_{S\subset V, 0<|S|\leq \frac{n}{2}}\frac{|\partial S|}{|S|}.
\end{equation}


Is calculating $h(G)$ NP-hard?



The complexity of expansion ratio (Cheeger constant) of a graph
[This paper](https://arxiv.org/pdf/2005.05812.pdf) says it is NP-hard and gives three references.


