Hi all, 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 :) 
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 exponentiallysized 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 Austin Buchanan 1
Thank you Austin, in fact I am looking for other ways (and in case I find anything I'll post links :) ). Now we are trying both approaches (which are closely related) in MIP formulations and yes, we have symmetry issues. They are due to the root and to the structure (chosen a set of nodes, there is more than one, possibly many, spaning trees). We are exploiting the remedy you suggest plus orbitopal constraints, which seem to work pretty well until the problem does not grow too much. Other ideas? What about Constraint Programming?
(21 Jan '13, 06:06)
kr1zz
I would be very careful about combining symmetrybreaking approaches. Sometimes strategy A is appropriate and strategy B is appropriate, but A+B rules out optimal solutions. In another strategy, do not try to break symmetry, but instead use a commercial solver with significant symmetry detection. You may try setting the symmetry parameter as high as possible in CPLEX or in Gurobi. As for constraint programmingI would not be the person to ask.
(27 Jan '13, 12:35)
Austin Buchanan
1
Do you know the number of elements in the partition in advance? Do you know that some nodes belong to a given partition element? What is the objective function?
(28 Jan '13, 07:27)
jfpuget
@jfpuget the original problem featured cardinality constraints (i.e., up to C nodes per partition) and the number of partitions was given (so I had to allow the case were a node could be left unassigned to any partition), details can be found here and here. Now I would like to generalize the problem/try some variants.
(31 Jan '13, 04:33)
kr1zz
showing 5 of 6
show 1 more comments

Hi! Sorry for the selfreference 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. Regards, answered 15 Jan '13, 09:22 Rodolfo Carv... fbahr ♦ Thank you Rodolfo, I found your paper very interesting, both the application and the algorithm. We also happened to consider a treebased formulation,that's why I am looking for something different. However, I might exploit your strengthenings. Did you work on the problem because of a real need or was it just an academic investigation?
(21 Jan '13, 05:53)
kr1zz
Another question: did you try any heuristic approach? Maybe to bootstrap the b&c?
(21 Jan '13, 06:07)
kr1zz
And a third one: have you experimented with more than one patch?
(21 Jan '13, 06:27)
kr1zz
1
I'm glad that you like the paper, @kr1zz! Regarding your questions:
(21 Jan '13, 20:43)
Rodolfo Carv...
1
@kr1zz 2. We did try a very simple heuristic but it seems it didn't did well compared with CPLEX. Our focus was to show the strenght of the formulation and the ease to obtain good upper bounds. There is a lot of room for trying more ideas on the heuristic side. Whe did not try to bootstrap the b&c.
(21 Jan '13, 20:50)
Rodolfo Carv...
1
I would love to know about any progress on your problem. Good luck!
(21 Jan '13, 20:54)
Rodolfo Carv...
showing 5 of 6
show 1 more comments
