A Generalized Cheeger Inequality

Ioannis Koutis, Gary Miller, Richard Peng

The generalized conductance $\varphi (G,H)$ between two graphs $G$ and $H$ on the same vertex set $V$ is defined as the ratio $$ ϕ(G,H) = \min_{S\subseteq V} \frac{cap_G(S,\bar{S})}{ cap_…