Page 1 of 1

Connected Subgraph Generation

Posted: Sat Jan 06, 2018 6:36 pm
by amin
Hello,
I have a graph G=(V,E) in GAMS, and I am trying to generate all connected subgraphs of G, possibly by using dynamic sets.
Any idea on solving this issue is greatly appreciated.
Thanks,
Amin

Re: Connected Subgraph Generation

Posted: Wed Mar 21, 2018 11:31 pm
by cladelpino
This problem of course admits a MIP formulation, but you cannot easily (of the top of my head) limit it to generate only one subgraph per run. Of course this may not be a problem for you (since you are trying to enumerate them all). Something along the lines of...

set node nodes;
set edge(node,node) /.../;
alias(node,i);
binary variable x indicates if the node is chosen for the subgraph;

equation isconnected;
isconnected(node).. sum(i$(edge(node,i) or edge(i,node)),x(i)) =g= x(node);

equation sizeDef;
sizeDef.. sum(node,x(node))=e=size;

model subg /all/;
solve subg using MIP maximizing size;

then repeat adding cuts...

Best
Claudio