I am trying to find some generic upper bounds on the "standard" graph partitioning problem. Say I have a graph with $|V|$ vertices and $|E|$ edges I want to partition it into two equal $N/2$ (or approximately equal if easier) parts while minimizing the cut i.e. $\min(|C|)$ where $C$ is the set of edges with nodes on either side of the partition (similarly nodes that the cut goes through).

So far this is standard stuff and clearly the optimal solution depends on the details of the graph. However, what I want is an upper bound on $\min(|C|)$ in terms of $|V|$ and $|E|$ without knowing anything else about the graph. If no upper bound then even some type of average case estimate would help.

Also, the same thing for a multigraph.

  • 1
    $\begingroup$ What is the answer for the complete graph $K_n$ on $n$ vertices? You may assume $n$ is even. $\endgroup$ – Pål GD Apr 9 at 13:09
  • $\begingroup$ Do you think that you could get a bigger cut than that for a simple graph? $\endgroup$ – Pål GD Apr 9 at 14:35
  • $\begingroup$ @PålGD The complete graph has a fixed structure (I know what the graph looks like) and so it is easy to find an exact solution ($n^2/4$). However what If I say for example $|E|=|V|=n$ ? Will the worst case solution be 2, as in the case where the graph is a polygon ? $\endgroup$ – Aharon Brodutch Apr 9 at 14:43
  • $\begingroup$ Okay, so let $|E| = |V| = n$ and let $G \supseteq K_\sqrt{n}$. $\endgroup$ – Pål GD Apr 9 at 14:55
  • $\begingroup$ If I understand you correctly the answer for this subset of cases is 0 since less than n/2 of the vertices have edges. So I just put all the edges in one partition. But I already know of a case (my comment above) where the answer is 2 so the upper bound is at least 2. $\endgroup$ – Aharon Brodutch Apr 9 at 15:04

This is an area in which I'm not very familiar, but what you are looking for are so-called expander graphs.

A graph $G$ has edge expansion $$h(G) = \min_{0 \leq |S| \leq \frac n 2} \frac{|\partial S|}{|S|},$$ where $\partial S$ is the boundary of $S$, i.e., the edges with exactly one endpoint in $S$.

This isn't exactly what you ask for, but you can also consider only $S$ of size exactly $\frac n 2$. There are $d$-regular expander graph classes. Perhaps that will point you towards something.


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.