# Vertex isoperimetric number of a graph - NP-hard?

The vertex isoperimetric number of a graph $G=(V,E)$ is
$i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$.
Several academic papers state that the problem of computing the vertex isoperimetric number of a graph is NP-hard, without proof or reference.

Can you give a reference where the following problem is shown NP-complete: given a graph $G$ and a number $t$, the question is to decide whether $G$ has vertex isoperimetric number at most $t$?

• Isn't this close to max cut? – Saeed Apr 5 '17 at 21:05
• Max Cut is actually closer to the Cheeger constant, where, in the above definition, $|N(S)|$ is replaced by the number of edges with one endpoint in $S$ and the other one in $N(S)$. For the Cheeger constant, NP-hardness proofs are easily found in the literature. – Serge Gaspers Apr 5 '17 at 23:39
• The following may be helpful. sciencedirect.com/science/article/pii/0020019081900508 – Chandra Chekuri May 6 '17 at 22:04