2
$\begingroup$

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

$\endgroup$

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.