I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar problems to which I can map to. Perhaps someone can give some insight or point me to a similar problem from the graph theory literature.

The problem is as follows, given a fully connected graph $G=(V,E)$ with weights $w_i$ on the edges. Find a partition which removes edges $E_p$ $(E_p \subset E)$ to create exactly $k$ connected components that maximize an objective. A solution or mapping for $k=2$ should be good enough to get me started so I'll just formulate the problem for k=2. The partition seeks to maximize a function over the $2$ subgraphs $\frac{\sum\limits_{w \in W_1} w}{|S_1|}+\frac{\sum\limits_{w \in W_2} w}{|S_2|}$ where $W_1$ and $W_2$ are the set of edge weights for connected components $S_1$ and $S_2$. Without the cardinality normalization term this problem can be mapped to min-cut. There is some similarity here with the ratio cut problem which seeks to maximize $\frac{cut(S_1,S_2)}{|S_1|}+\frac{cut(S_1,S_2)}{|S_2|}$ but I have been unable to find any mapping between the problems. Any suggestions or key search terms would be helpful


Your Answer

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

Browse other questions tagged or ask your own question.