0
$\begingroup$

I'm a newbie in the mathematical field of graph theory (started to dive into it only few days ago) but I'm a very fast learner and have deep mathematical background. I'm trying to find/develop an algorithm for the following problem:

Given a directed weighted graph $G$ with $m$ nodes and $n$ arcs and a constant integer $K\le10$ (each arc has a weight $w_{ij}$), Divide all $m$ nodes into K sub groups such that the following two goals are met:

1) Sum of intra-arcs weights (in each sub-group) will be equalized across all sub groups (to some extent using a predefined error criteria - e.g < 1%).

$ \underset{\{\forall k,l |k \ne l\}}{\text{minimize}} \left|\displaystyle\sum_{i,j\in S_k} w_{ij} - \displaystyle\sum_{i,j\in S_l} w_{ij}\right| \\ k,l \in [1\mathrel{{.}\,{.}}K] \\ S_k \cap S_l \in \{\varnothing: k \ne l \} $

2) Minimize the number of inter-arcs (connecting sub-groups).

$ \underset{\{\forall k,l |k \ne l\} }{\text{minimize}} \left(\displaystyle\sum_{i\in S_k, j\in S_l} a_{ij} \right) \\ \\ a_{ij} = \begin{cases} 1 & \quad \text{if } i \ne j \text{ and arc } i \rightarrow j \text{ exist}\\ 0 & \quad \text{ otherwise}\\ \end{cases} \\ $

Any help would be greatly appreciated!

Gil

$\endgroup$
  • $\begingroup$ I forgot to specify that my graph contains significant amount of cycles. $\endgroup$ – Gil Sep 20 '18 at 21:59
  • $\begingroup$ Can you assume WLOG that the arc weights are symmetric by, e.g., taking $w'_{ij} = w'_{ji} = (w_{ij} + w_{ji})/2$? You say that the $S_i$'s should partition the vertices; is that what you mean by the following notation? $$S_k \cap S_l \in \{\varnothing: k \ne l \}$$ $\endgroup$ – Neal Young Sep 21 '18 at 5:24
  • $\begingroup$ Hi Neal, in my problem, the arc weights are not necessarily equal, namely - $ w'_{ij} \ne w`_{ji} $ . As for your second question, you understood me correctly. $\endgroup$ – Gil Sep 21 '18 at 7:36
  • $\begingroup$ I did some homework yesterday and it seems like the Kernighan-Lin and/or the Fiduccia-Mattheyses (FM) algorithms might do the job. (I'm starting to learn how to implement them). Any comment on that? $\endgroup$ – Gil Sep 21 '18 at 7:42
  • $\begingroup$ My comment about $w'$ is suggesting a reduction. Given any $w$, you can replace $w$ by the (symmetric) $w'$ suggested there without changing the problem, right? $\endgroup$ – Neal Young Sep 21 '18 at 13:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.