Minimum cost node cut
-
05-11-2019 - |
Question
I am interested in solving the following problem:
Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph.
Is there any known algorithm solving this problem?
Here is an attempt at a solution (in python), using network flow:
deg_G = nx.degree(G)
max_weight = max([deg for i,deg in deg_G])+1
st_Weighted_Complement_G = nx.DiGraph()
r = np.arange(len(Complement_G.nodes))
nodes = ['s','t']
edges = []
for i in r:
nIn = (str(i)+'in')
nOut = (str(i)+'out')
nodes.extend([nIn,nOut])
edges.extend([(nIn,nOut,{'capacity':deg_G[i],'weight':deg_G[i]}),('s',nIn,{'capacity':math.inf,'weight':0}),
(nOut,'t',{'capacity':math.inf,'weight':0})])
for edge in Complement_G.edges:
print(edge[0],edge[1])
edges.extend([((str(edge[0]))+'out',(str(edge[1]))+'in',{'capacity':max_weight,'weight':0}),
((str(edge[1]))+'out',(str(edge[0]))+'in',{'capacity':max_weight,'weight':0})])
print(edges)
st_Weighted_Complement_G.add_nodes_from(nodes)
st_Weighted_Complement_G.add_weighted_edges_from(edges)
mincostFlow = nx.max_flow_min_cost(st_Weighted_Complement_G, 's', 't',capacity='capacity',weight='weight')
print(mincostFlow)
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange