# 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

## 1 Answer

The following paper: On an isoperimetric problem for Hamming graphs L.H. Harper. contains the following:

The vertex-isoperimetric problem is NP-complete  in general, so no polynomially bounded solution is known and it is unlikely that one exists.

Where reference  is M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,

This book usually either contains a proof or a reference to the proof. Unfortunately I have no access to the book at the moment.

• But the NP-hard problem variant in Harper's paper is different: given a graph G and an integer k, find a subset S of the vertices with |S|=k that minimizes |N(S)|. – Gamow Apr 6 '17 at 14:25
• I see, you are right. – user53923 Apr 6 '17 at 14:31