I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from standard min, max cut problems. I have searched for a suitable algorithm for several days but with no success. Maybe someone can give a suggestion or at least come up with a standard name for such problem?

The problem is as follows:

Input: Undirected graph $V$ with vertex weights $u_i$ and edge weights $w_{ij}$.

Output: Graph partition in two components $S_1$ and $S_2$ to minimize the following:
$$\max((\sum_{i\in S_1}u_i-\sum_{i,j\in S_1}w_{ij}), (\sum_{i\in V-S_1}u_i-\sum_{i,j\in V-S_1}w_{ij})) $$
Basically, if we define $weight$ of a component as the sum of weights of its vertices minus the sum of weights of its edges, then I would like to find a pair of components such that a maximal weight out of the two components is minimal over all possible pairs. The edges between two components are removed.

Here is an example of possible graph partition (there may be several). The numbers mean the weights:
Possible partition of a weighted graph Thanks in advance for suggestions!

  • 2
    $\begingroup$ Your problem is NP-hard. Hint: reduce from Partition to the special case of your problem with $w_{ij}=0$. $\endgroup$
    – Neal Young
    Commented Apr 4, 2016 at 18:40
  • $\begingroup$ @NealYoung do you mean to prove NP-hardness by reducing to the special case? That's true, I agree. But I hoped for some heuristic algorithm or at least something better than brute force... $\endgroup$
    – Kirill
    Commented Apr 4, 2016 at 18:58
  • 3
    $\begingroup$ Yes. As for heuristics, maybe integer linear programming? (You can modify the reduction above to show that deciding whether there is solution of cost zero is NP-hard, so, unless P=NP, there is no poly-time algorithm with multiplicative-approximation guarantee.) $\endgroup$
    – Neal Young
    Commented Apr 4, 2016 at 21:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.