Connected Subgraph Generation

Problems with modeling
Post Reply
amin
User
User
Posts: 1
Joined: 4 months ago

Connected Subgraph Generation

Post by amin » 4 months ago

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

cladelpino
User
User
Posts: 96
Joined: 1 year ago

Re: Connected Subgraph Generation

Post by cladelpino » 2 months ago

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

Post Reply