2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

This paper says it is NP-hard and gives three references.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .