6
$\begingroup$

I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted.

My questions are: what are the definitions that best match the primary sources and the current use? Does what follows sound right?

(1) The Cheeger constant of a graph, denoted $h$ is

$h(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ |S|, |V-S| \}}$

where $\textrm{Edges}(S,V-S)$ denotes the number of (or the total weight of) edges with one endpoint in $S$ and one endpoint not in $S$.

(2) The uniform sparsest cut of a graph, denoted $\phi$ is

$\phi(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{|S| \cdot |V-S|}$

Notes:

  • $h$ is also called the edge expansion of $G$
  • $h$ and $|V|\cdot \phi$ are within a factor of 2, so approximating one problem is equivalent to approximating the other, up to a constant loss in the approximation ratio

(3) The conductance of a graph, unfortunately also usually denoted $\phi$. Maybe we should use $\sigma$ for the sparsest cut parameter?

$\textrm{conductance}(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ \textrm{vol}(S), \textrm{vol}(V-S) \}}$

where $\textrm{vol}(S)$ is the sum of the degrees of the vertices of $S$

Note:

  • If $G$ is $d$-regular, then $\textrm{conductance}(G) = h(G)/d$. In the irregular case, the conductance is incomparable with $h$ and $\phi$

(4) Finally, as an intermediate problem to use to give relaxations of the conductance problem, I have seen the following problem, that does not seem to have a name ("volume-weighted sparsest cut"? what letter should be used to denote it?)

$\min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\textrm{vol}(S) \cdot \textrm{vol}(V-S)}$

which is $\phi/d^2$ in regular graphs, and that scaled by $\textrm{vol}(V)$ is within a factor of 2 from the conductance.

$\endgroup$
  • $\begingroup$ I'd add edge isoperimetric parameter and (edge) isoperimetric number to this list, both of which are also sometimes used in an ambiguous way. $\endgroup$ – Holger Feb 4 '11 at 14:27
5
$\begingroup$

I think (2) is called the uniform sparsest cut. The term non-uniform is used for the version where each pair ij of vertices has a separate demand d(ij) and the cut sparsity is E(S,V-S)/d(S,V-S) where d(S,V-S) is the demand between S and V-S.

$\endgroup$
  • $\begingroup$ You are right, and I meant to write "uniform", I'll edit the post $\endgroup$ – Luca Trevisan Jan 30 '11 at 22:25
3
$\begingroup$

If I am not mistaken, (4) is called normalized cuts.

$\endgroup$

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.