Fixed-parameter tractability of the mixed-sign k-part minimum edge cut problem on sparse graphs
When applying community detection methods such as modularity, one encounters an optimization problem of the general form “I have a collection of objects that I need to divide into bags, and for each pair there is a cost or benefit associated to putting them in the same bag”. In general, this problem is very hard to solve, but for some particular instances, it is known to be easy when dividing into two bags.
May 1, 2025
