5
$\begingroup$

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge weights. After cutting, each subgraph must be connected (i.e. there must be a path between any two vertices of the subgraph which is only composed of vertices in that subgraph).

However, unlike most existing work on graph partitioning out there, I don't intend to obtain subgraphs that contain the same approximate number of vertices. Instead, I would like these subgraphs to have similar sum of edge weights. In other words, I would like to minimize the sum of edge weights of the subgraph with maximal weight and ideally cut long (weighted) edges.

Is there a name for this problem? I wasn't able to find anything about this on the web. Also, how can I approach this problem?

Improve this question
$\endgroup$
  • $\begingroup$ Are there no constraints on the size of the subgraph? Say a minimum of 2 vertices in the subgraphs or else the problem could have a trivial answer like each vertex forms a graph with zero total weight. $\endgroup$ – swarnim_narayan Aug 2 '13 at 11:25
  • $\begingroup$ @wang if $k$ is fixed, separate each vertex doesn't work. $\endgroup$ – wece Aug 2 '13 at 11:41
  • $\begingroup$ You only care for the existence of such a subgraph, and not for a solution that minimizes the sum of deleted edges or the weight (in terms of edge weights) of each connected component? Also, are the weights in a specific range, or can they be arbitrarily large? $\endgroup$ – Jonas G. Drange Aug 4 '13 at 10:08
  • $\begingroup$ @JonasG.Drange: the goal is to find a cut, where the weight of the subgraph with maximum weight is minimized. The weights are arbitrary real positive numbers. Thanks! $\endgroup$ – davidbsp Aug 4 '13 at 21:12
  • $\begingroup$ how many edges am I allowed to cut? can I also cute edges within a subgraph, if it still remains connected afterwards? $\endgroup$ – Syzygy Sep 22 '16 at 23:43
1
$\begingroup$

If the graph is sparse, may be it's also bounded tree width. Then we can find the optimum cut by using dynamic programming for graphs of bounded treewidth1. To check whether it's a bounded tree-width or not there are some tools and you can use them. On the other hand, one (may be good) heuristic approach is finding maximum spanning tree. This can be done by negating edge weights and running Kruskal algorithm to find MST. Because the graph is sparse then heaviest cuts along this tree are not bad, also good cut for tree can be found by bottom up dynamic programming approach. (I think it's in factor of at most 5 with high probability in most cases).

1: I didn't think about it, but seems to be as usual.

Improve this answer
$\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.