I am working on a graph partitioning problem with the hard constraint that each partition must induce a connected subgraph. While I found a lot of work on graph partitioning, I did not find much about the connectivity issue: can anyone suggest me relevant literature?
In particular, I am looking for exact approaches and formulations.
Thanks a lot :-)
Sorry for the self-reference here, but you might want to read:
"Imposing Connectivity Constraints in Forest Planning Models" by R. C., M. Constantino, M. Goycoolea, J. P. Vielma and A. Weintraub, 2011.
you will find an exact approach there and references to other authors tackling the issue of connectivity.
Realize that a (sub)graph is connected if and only if it has a spanning tree. So, you can enforce that each partition induces a tree (say, by choosing edges).
Another common method for enforcing connectivity is through a flow formulation. For each partition, pick a 'source' node and require that each vertex in the graph receives at least one unit of flow from a source node. There can be considerable symmetry in this formulation when you have multiple partitions. One remedy is to require that a source node may only 'fuel' nodes with a larger index (after numbering the nodes 1,...,n). Equivalently, each partition has a unique 'representative' that roots the tree; it has the lowest index in its partition.
You can also use an exponentially-sized formulation based on cutsets. In each partition, there will be sets of vertices that will disconnect the partition. For each of these cutsets, require that at least one of its vertices is selected.
I suspect that there are many other ways to enforce connectivity. For more information, I would search for connectivity constraints in general -- not necessarily limited to graph partitioning.
answered 15 Jan '13, 09:43