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

  • $\begingroup$ Isn't this close to max cut? $\endgroup$ – Saeed Apr 5 '17 at 21:05
  • $\begingroup$ 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. $\endgroup$ – Serge Gaspers Apr 5 '17 at 23:39
  • $\begingroup$ The following may be helpful. sciencedirect.com/science/article/pii/0020019081900508 $\endgroup$ – Chandra Chekuri May 6 '17 at 22:04

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.

| cite | improve this answer | |
  • 2
    $\begingroup$ 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)|. $\endgroup$ – Gamow Apr 6 '17 at 14:25
  • 1
    $\begingroup$ I see, you are right. $\endgroup$ – user53923 Apr 6 '17 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.