A Generalized Cheeger Inequality

Abstract

The generalized conductance $\varphi (G,H)$ between two graphs $G$ and $H$ on the same vertex set $V$ is defined as the ratio $$\varphi (G,H)=\underset{S\subseteq V}{\min }\frac{ca{p}_G(S,\bar{S})}{ca{p}_H(S,\bar{S})},$$ where $ca{p}_G(S,\bar{S})$ is the total weight of the edges crossing from $S$ to $\bar{S}=V-S$. We show that the minimum generalized eigenvalue $\lambda (L_G,L_H)$ of the pair of Laplacians $L_G$ and $L_H$ satisfies $$\lambda (L_G,L_H)\ge \varphi (G,H)\varphi (G)/8,$$ where $\varphi (G)$ is the usual conductance of $G$. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to $\lambda (L_G,L_H)$. The inequality complements a recent proof that $\varphi (G)$ cannot be replaced by $\Theta (\varphi (G,H))$ in the above inequality, unless the Unique Games Conjecture is false.