3
$\begingroup$

I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same size (either in terms of number of nodes or sum total of node weight), and the sum total weight of edges that cross between components is minimized. Problems of this nature are generally NP-hard, but I am aware of the software METIS which can obtain good quality partitions very quickly. METIS also has the feature that it can enforce the constraint that each component in the resulting partition be contiguous ("connected").

What I am looking for is an algorithm or some sort of software package that is similar to METIS, but can also enforce the constraint that each partition is still contiguous when only a certain subset of edges from the original graph are considered.

Here is an example:

enter image description here

The graph on the left is the original graph. All nodes have the same weight. If I want to partition the graph into two components, while enforcing contiguity constraints, I would choose the highlighted groups. This partition has a "cost" of 5. But what I actually want to do is partition the graph on the left, while enforcing the constraint that each component be contiguous if it only had the edges in the graph in the middle. This obviously results in a different partition (which is actually the only feasible partition in this small example). This partition has a cost of 9 (note I am still counting the edges from the original graph), but it satisfies the constraints.

I would be interested in algorithms that solve this problem directly, or that transform the problem into something that can be solved by currently-existing software, e.g. METIS.

It is not sufficient to just perform graph partitioning on the middle graph, because that ignores the potential cost of the additional edges that may or may not cross between different components in the resulting partition.

(For those wondering the use case, I am interested in redistricting. I have a graph that quantifies the relationships between different precincts, but I need to enforce a contiguity constraint on the graph that represents which precincts actually border each other, which is much smaller than my input graph.)

$\endgroup$
8
  • 2
    $\begingroup$ Does "contiguous" mean that each component is connected? $\endgroup$
    – D.W.
    May 5, 2023 at 4:28
  • $\begingroup$ Sounds very hard. I'm not sure how METIS does it, but note that the resulting solution has a natural tendency to produce connected components: since you want to cut less edges, you have more edges in each part, which makes it likely that each part is connected. I suspect that they just run the usual solution, and then fix it to satisfy the connectivity constraint (and it might be your best bet to do the same). Also, how large are your graphs? Maybe there is some rule for IP or SAT solvers. $\endgroup$
    – Dmitry
    May 5, 2023 at 4:41
  • $\begingroup$ @D.W. Yes, exactly $\endgroup$
    – Ike348
    May 5, 2023 at 11:51
  • $\begingroup$ @Dmitry Ideally most graphs I am interested in would be tens of thousands of nodes but the largest could be up to 500000 nodes. I briefly played around with the METIS source code but as I am not familiar with the algorithm itself it was tough to figure out exactly what I needed to change. But if your hunch is true and the contiguity constraints are just enforced as a "fix" after the partition is built, it may be a lot easier $\endgroup$
    – Ike348
    May 5, 2023 at 12:24
  • $\begingroup$ OK, I looked at the code, and what I said is not exactly true, but not that far from the truth either. The partitioning calls RefineKWay, which at different stages calls EliminateComponents with some balancings after that. EliminateComponents looks like some kind of greedy local search, you may try to mimic what they do there. $\endgroup$
    – Dmitry
    May 5, 2023 at 16:27

2 Answers 2

0
$\begingroup$

If your graphs aren't too large, you could try to solve this using an integer linear programming (ILP) solver.

Introduce 0-or-1 variables $x_{i,v}$, to indicate that vertex $v$ is part of the $i$th component. You can enforce that each component is connected ("contiguous") using the techniques in Boolean constraints for a connected component of a graph. You can enforce that the components partition the graph with a linear equality $\sum_i x_{i,v}=1$ for all $v$. You can enforce that the components are all about the same size by introducing a new variable $w$ and constraining $w-10 \le \sum_v x_{i,v} \le w+10$ for each $i$ (you can change 10 to whatever constant you find acceptable; this requires them to be all about the same, +/- 10). You want to minimize the sum of the edges that cross between different components. This can be expressed by introducing new 0-or-1 variables $y_{u,v}$, one for each edge $(u,v)$ in the graph, and requiring $x_{u,i} + x_{v,j} - 1 \le y_{u,v}$ for every $i,j$ with $i\ne j$. Then, minimize the sum $\sum \text{wt}(u,v) y_{u,v}$. This is a linear objective function, with a set of linear inequalities as constraints, so you can solve this with an off-the-shelf ILP solver.

Whether this will work well or not will likely depend on the size of the graph. You've have to try it to see how well it works in practice.

$\endgroup$
2
  • $\begingroup$ Thank you. I never even considered a "basic" ILP. Unfortunately my graphs are fairly big (tens of thousands of nodes) so I will have a lot of decision variables / constraints. But it is a good idea to try this with a smaller graph first and see how well it scales $\endgroup$
    – Ike348
    May 5, 2023 at 11:54
  • $\begingroup$ @Ike348, oof. I don't expect this method will work well on graphs of that size. Sorry. $\endgroup$
    – D.W.
    May 5, 2023 at 17:53
0
$\begingroup$

I do not have a good answer for you, as this is an active research area and we simply don't know any good algorithms, or indeed if there exists any, but here are some pointers.

  1. The problem is NP-complete, even with 2 sets where one set has size 2 (Van 't Hof et al., 2009)
  2. The problem is NP-complete, even on planar graphs (Grey et al., 2012)
  3. The problem for 2 partitions on planar graphs is fixed-parameter time tractable parameterized by the sum of the sizes of the partitions, which in your case would be $n$, so that's not really great (Bentert et al., 2023)
  4. You can try to use idea's from Karger's algorithm, similarly to what was done for multiway cut. (Calinescu et al., 1999)

A small observation, for planar graphs, there's a duality between a minimal cut in $G$ and a simply cycle in $G^*$, the dual graph of $G$. A 3-way cut corresponds to two simple cycles in $G^*$, unfortunately, they do not necessarily behave so nicely; either $C_1$ and $C_2$ are disjoint, $C_1$ is contained inside $C_2$, or $C_1$ and $C_2$ share a path.

Keywords here are: cut-uncut, $k$-way cut, multiway cut.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.