3
$\begingroup$

I am looking for an algorithm that, given an undirected, planar graph $G = (V,E)$ with node weights, meets the following conditions:

  1. Creates balanced (within some margin) $k$ partitions of $V$ according to node weight.
  2. All partitions have to be connected.
  3. It cannot minimize communication volume, or edge cuts.

My graphs are planar, all vertex weights are positive integers, and the reason that I want #3 is that I need to be able to generate $n$ distinct partitions from the graph that I have. I have found that if I use GPMetis, no matter what options and seed I pass it (currently using -seed=40 -ctype=rm -iptype=random -ptype=kway). The options have an impact only if I scale up the number of vertexes (on my graphs that have less than 100 nodes, it always gives the same answer).

Are there algorithms that exist to create balanced partitions by vertex weight that meet these conditions? It doesn't need to ignore edge counts/weight entirely, so long as I can still make the result different via some seed. Willing to take either a research paper, or fully functional code.

As background:

  • I know that a vertex separator can be found in polynomial time for planar graphs, but I need all my vertices.
  • There are several edge cut algorithms that also run in near polynomial time, but these have the problem listed above of not being able to inject sufficient randomness.
$\endgroup$
  • $\begingroup$ Woa, this is becoming too broad! Please restrict yourself to one type of algorithm: deterministic/correct, stochastic, approximation, ... Also, please state which similar problems you know solutions for; that can help potential answerers! $\endgroup$ – Raphael Aug 3 '15 at 19:19
  • $\begingroup$ @Raphael is this better? $\endgroup$ – soandos Aug 4 '15 at 4:15
  • $\begingroup$ You did not address my queries specifically, but I think the question improved, yes. I added what your input is. I don't understand #3 or how it is consistent with #1, but that may be my lack of expertise. $\endgroup$ – Raphael Aug 4 '15 at 6:06
  • $\begingroup$ @Raphael it has to do edge cuts, but it does not have to minimize them? Or am I missing something? $\endgroup$ – soandos Aug 4 '15 at 13:36
  • $\begingroup$ Maybe you can find some references in PTAS for MAX-BISECTION on planar and geometric graphs by Jansen et al. $\endgroup$ – Pål GD Aug 4 '15 at 14:55
2
$\begingroup$

One general method is to perturb the node weights slightly, find a good partition, and repeat that $n$ times with $n$ different perturbations.

The basic algorithm is something like this:

  • Repeat until you have $n$ distinct balanced partitions of $G$:

    1. Copy $G$ to $G'$. Randomly perturb the weight of each node in $G'$ by a tiny amount (a different random change for each node).

    2. Find a balanced partition of $G'$. This corresponds to a partition of $G$.

    3. If this is a legal, balanced partition of $G$ and you haven't seen this partition of $G$ before, add it to your list of distinct partitions.

If you choose the amount of the perturbation correctly, then you can expect this will need only $O(n)$ iterations of the loop to find $n$ distinct partitions.

Let's see in a little more detail how to make this work in your setting and why it works. The basic idea is to add a tiny, tiny random perturbation to each node's weight. This won't affect the total weight of any group in your partition by very much: the sum of a bunch of of tiny numbers is still quite small, and in particular, we can ensure it will be much smaller than 1. Since the total weight of any group of vertices in $G$ has to be an integer, the change in its total weight can't be enough to make it jump up to the next integer. Consequently, this won't change the relative order of vertex-groups (if one vertex-group has a smaller weight than another vertex-group, after perturbation its weight cannot become larger); all it can do is break ties.

However, this basic idea has a problem: after perturbation, the vertex weights in $G'$ are no longer integers. It's possible that your underlying algorithm (e.g., Metis) requires the vertex weights to be integers. If so, here is how we can fix things up and preserve the integrality of node weights. The idea is to first scale up all of the weights by a large integer constant $c_1$, then add a small integer perturbation to each node weight. Formally, let $w_v$ be the weight on node $v$. We're going to pick integer constants $c_1,c_2$ and for each node $v$ set

$$w'_v = c_1 w_v + r_v,$$

where $r_v$ is a random integer chosen from $\{0,1,\dots,c_2\}$ (chosen independently for each node). We'll use $w'_v$ as the weight of node $v$ in $G'$.

How do we choose $c_1,c_2$? Basically, we need $c_2$ to be large enough so that each iteration is likely to give you a new partition, and we need $c_1/c_2$ large enough so that a balanced partition of $G'$ is likely to also be a balanced partition of $G$. One reasonable setting is to use $c_2=100n$ and $c_1 = 100 |V| c_2$. Alternatively, if your underlying algorithm is OK with non-integer vertex weights, you could instead pick $r_v$ randomly from the range $[0,1/(100|V|)]$ and just leave $c_1=1$.

Why does this work? Well, first note if we divide all the weights in a graph by a constant, that has no effect on the set of balanced partitions -- so we might as well consider the weights to be $w''_v = w_v + r_v/c_1$. Now I claim that a balanced partition of $G'$ is almost certainly a balanced partition of $G$. Any single group in the partition has at most $|V|$ vertices, and the weight of each node in the group has been randomly increased by at most $c_2/c_1$, so the total increase in the weight of that group is at most $|V|c_2/c_1=0.01$. Originally the total weight of a vertex-group has to be integer, so this perturbation is not enough to make it jump up to the next integer. Now, depending upon your definition of balanced, most likely the following will be true: any balanced partition in $G'$ has a high probability of being a balanced partition in $G$.

Also, the random perturbations ensure that, if you look at two perturbed graphs $G'_1,G'_2$, it is unlikely that the optimum partition of $G'_1$ is the same as the optimum partition of $G'_2$.

So, I suggest you give this a try.


Important caveats: There are no guarantees this will work. From a theoretical perspective, it's not guaranteed to work. Indeed, I suspect your problem might be NP-hard, so it would be too much to expect this to always work. But in practice, this often works, if you are in a situation where your underlying algorithm (e.g., Metis) is able to find the optimum partition in a reasonable amount of time. As a pragmatic guideline, it's more likely to work if the underlying algorithm can find an exact optimum rather than an approximate-optimum (e.g., maximally balanced rather than close-to-maximally-balanced). However, as I said, there are no guarantees, so the best way to find out whether it will work in your particular situation is to try it out and see.

$\endgroup$
  • $\begingroup$ Ill try it later today. As an aside, I am almost positive that for this to be scaleable (should anyone else need that) it might will be necessary to expand the underlying data type to a 64 bit type to prevent the new total weight of the graph from going above int max $\endgroup$ – soandos Aug 4 '15 at 19:45

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.