<p>The following paper:
<em>On an isoperimetric problem for Hamming graphs
L.H. Harper.</em> contains the following:</p>

<blockquote>
  <p>The vertex-isoperimetric problem is NP-complete [8] in
  general, so no polynomially bounded solution is known and it is unlikely that one
  exists.</p>
</blockquote>

<p>Where reference [8] is
<em>M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness</em>, </p>

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

CC BY-SA 3.0
2017-04-06T14:25:35.640Z
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
CC BY-SA 3.0
2017-04-06T14:31:41.520Z
I see, you are right.
user53923
CC BY-SA 3.0
2017-04-06T11:26:35.690Z
2017-04-06T11:26:35.690Z
user53923
<p>The <em>vertex isoperimetric number</em> of a graph $G=(V,E)$ is<br>
$i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$.<br>
Several academic papers state that the problem of computing the vertex isoperimetric number of a graph is NP-hard, without proof or reference.</p>

<p>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$?</p>

CC BY-SA 3.0
2017-04-05T21:05:58.393Z
Isn't this close to max cut?
Saeed
CC BY-SA 3.0
2017-04-05T23:39:19.770Z
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
CC BY-SA 3.0
2017-05-06T22:04:38.757Z
The following may be helpful. http://www.sciencedirect.com/science/article/pii/0020019081900508
Chandra Chekuri
<reference-request><graph-theory><np-hardness>
Vertex isoperimetric number of a graph - NP-hard?
Serge Gaspers
# Vertex isoperimetric number of a graph - NP-hard?

(Asked by: username_0 on 2017-04-05)

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$?

**Tags:** reference-request, graph-theory, np-hardness

> **Comments:**
> **username_1**: Isn't this close to max cut?  
> **username_0**: 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.  
> **username_2**: The following may be helpful. http://www.sciencedirect.com/science/article/pii/0020019081900508  

---

## 1 answers

### Answer by username_3 on 2017-04-06. Score: 1

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

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

Where reference [8] 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.

> **Comments:**
> **username_4**: 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)|.  
> **username_3**: I see, you are right.  

---

