A Generalized Cheeger Inequality

The generalized conductance $ϕ(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_H(S,\bar{S})},$ where $cap_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 $λ(L_G,L_H)$ of the pair of Laplacians $L_G$ and $L_H$ satisfies $λ(L_G,L_H) \geq ϕ(G,H) ϕ(G)/8,$ where $ϕ(G)$ is the usual conductance of $G$. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to $λ(L_G,L_H)$. The inequality complements a recent proof that $ϕ(G)$ cannot be replaced by $Θ(ϕ(G,H))$ in the above inequality, unless the Unique Games Conjecture is false.

No reviews yet.

No comments yet.