Summary -「Maximum Weight Closure of a Graph」

cirnovsky /

§ 1. Introduction

Define a closure of a directed graph G=(V,E)G=(V,E) as an induced set of vertexes of GG, where the out-tended edges in EE start at some vertex in the closure of GG and end at some vertex in the closure, too. More formally, closure is defined as a set of vertexes VVV'\subseteq V, such that uV,s.t.<u,v>E,vV\forall u\in V',s.t.\forall\left<u,v\right>\in E,v\in V'.

For the Maximum Weight Closure of a Graph, we define it as, with starting out endowing vertexes in VV' costs called wuw_u, the maximum value of uVwu\sum\limits_{u\in V'}w_u.

§ 2. Construction of Algorithm

Add a source ss and a sink tt to the original graph, endow the origin edges in EE with capacities that ++\infty, and connect ss with points with positive costs with the points' costs as capacities on them while tt connects to those with negative costs with the minus points' costs as capacities on them, where ++\infty is defined as any number greater or equal to wi\sum |w_i|.

More formally, as explained & illustrated:

VN=V{s,t}EN=E{<s,v>vV,wv0}{<v,t>vV,wv<0}{c(u,v)=+,<u,v>Ec(s,v)=wv,wv0c(v,t)=wv,wv<0V_N=V\cup\{s,t\} \\ E_N=E\cup\left\{\left<s,v\right>\mid v\in V,w_v\geqslant0\right\}\cup\left\{\left<v,t\right>\mid v\in V,w_v<0\right\} \\ \begin{cases} c(u,v)=+\infty,\left<u,v\right>\in E \\ \displaystyle c(s,v)=w_v,w_v\geqslant0 \\ \displaystyle c(v,t)=-w_v,w_v<0 \end{cases}

Which make it easy to understand the answer would be min-cut(GN={VN,EN})\text{min-cut}(G_N=\{V_N,E_N\}).


[1] Referenced to 最小割模型在信息学竞赛中的应用 by 胡伯涛 Amber.