5
$\begingroup$

I am interesting in studying the complexity of some graph partition problems, where it is important to take into account the weights on the edges as well as the weight on the vertices. Max-cut only cares about the weights on the edges, while other problems only care about the weights on the vertices. Does anyone know problems in which BOTH weights are important in order to make the optimal partition?

Thank you very much

Here's an example problem:

Input: directed graph with vertex weights $u_i$ and arcs weights $w_{ij}$.

Output: a subset S of V to maximize the sum of the following things:

  1. $\sum_{i, j \in S} w_{ij} + \sum_{i,j \in V - S} w_{ij}$ (arc weights inside each side)

  2. $\sum_{|{i,j} \cap S| = 1} w_{ij}u_j$: the sum over all cut edges of product of arc weight and the weight of the destination vertex.

$\endgroup$
  • 6
    $\begingroup$ Might help to give a specific problem: there are specific transformation that might apply, but it's hard to say without looking at an actual problem. $\endgroup$ – Suresh Venkat Mar 19 '12 at 5:20
  • 4
    $\begingroup$ For many problems, there are easy reductions from graphs with weighted vertices and edges to graphs with just weighted vertices, or to graphs with just weighted edges. For minimum (s,t)-cuts, this is a standard homework exercise. $\endgroup$ – Jeffε Mar 19 '12 at 9:15
  • 2
    $\begingroup$ Is there any motivation for this (somewhat strange) cost function ? just wondering. $\endgroup$ – Suresh Venkat Mar 20 '12 at 5:23
4
$\begingroup$

(not quite an answer, but too long for a comment)

Given your new cost function, I'm wondering if there's a simpler formulatio. Let $W = \sum_{(i,j) \in E} w_{ij}$. Now your goal is to maximize

\[ W - \sum_{|\{i,j\} \cap S| = 1} w_{ij} + \sum_{|\{i,j\} \cap S| = 1} w_{ij}u_j\]

Collecting terms, your goal is then to minimize

\[ \sum_{|\{i,j\} \cap S| = 1} w_{ij} (u_j - 1)\]

Setting $w'_{ij} = w_{ij}(u_j - 1)$, your problem now becomes a min cut problem with the twist that it's not a typical min cut (you're not counting edges going from one side to the other, but both sides)

$\endgroup$
3
$\begingroup$

I think Sparsest cut or edge expansion, is good enough for you, because deals with both edges and nodes. The task is to find a cut, with $S\subset V$, $|S|\leq {|V|\over2}$ in one part such that:

$$\alpha(G) = \min \{ {E(S,S^c)\over |S|}\}$$

is minimized over all possible set of $S$.

You may look at Sparsest cut and bottlenecks in graphs by Matula,Shahrokhi for proof of NP-Hardness (proof is by using max cut).

Also P. Bonsmaa et al, shown that it's NP-Hard even in uniform case (means all edges are of weight $1$).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.