2
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ Sorry but programming questions are off-topic, here, and you already seem to know what algorithms you should be using. Your question is probably on-topic at Stack Overflow, but please check their help centre before posting. $\endgroup$ – David Richerby Nov 11 '18 at 1:04
  • $\begingroup$ Your question asking for algorithm is on-topic. However, please note that users here will generally avoid questions with long code in any particular language, let alone it runs with error!. $\endgroup$ – Apass.Jack Nov 11 '18 at 3:20
2
$\begingroup$

Your problem is a slightly more general version of computing the vertex-connectivity of a graph. If all weights are equal, then it is equivalent to the vertex-connectivity problem.

The problem can be solved in polynomial time with network flow, yes; but you'll need to invoke a network flow subroutine several times; just one invocation won't be enough.

The simplest approach is the following. Consider all pairs $s$, $t$ of nodes in the graph. For each such pair, we are going to compute the minimum cost, call it $c_{st}$, of separating that pair, that is, the weight of a minimum vertex-weighted $s$-$t$ cut. Then the set you look for will be the set achieving the minimum cost $c_{st}$ over all pairs $s$, $t$.

For a given pair $s$, $t$, the minimum weight cut can be computed with network flow by first replacing every edge $\{u,v\}$ with a directed pair of edges $(u,v)$, $(v,u)$. Then you need to expand your graph by splitting every vertex $v$ into a pair $(v^-, v^+)$. An arc $(u,v)$ is replaced by an arc $(u^+, v^-)$ and an arc $(v,u)$ is replaced by an arc $(v^+, u^-)$. Moreover you add arcs $(v^-, v^+)$ with capacity equal to the weight of $v$; all other arcs have unbound capacity ($\infty$). This complication is necessary to properly model the vertex removal costs. After creating this new instance, you just call the network flow subroutine with source $s^+$ and sink $t^-$. The amount of flow shipped from the source in the solution will tell you $c_{st}$. (To find the set of vertices disconnecting $s$ from $t$, look for all vertices $v$ such that $v^-$ is reachable from $s^+$ in the residual flow network while $v^+$ is not.)

All in all, you need to call the network flow subroutine $n(n-1)/2 = O(n^2)$ times. In fact, there is also a less intuitive but somewhat faster algorithm that allows you to call the network flow subroutine $m$ times instead of $n^2$, where $m$ is the number of edges. This could be much better if the graph if sparse. See the reference below for more details about this faster version.

You can also substantially reduce the time complexity if you know for sure some vertex $s$ that is not going to be one of the nodes that will be removed from the graph. Then you can just try all other nodes $t$ and follow the same strategy as above, only this time you will need to invoke $n-1$ times the network flow subroutine, because $s$ is fixed.

Reference: A. Schrijver, Combinatorial Optimization, Section 15.2. Springer, 2004.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.