# Partitioning directed graph

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

• I forgot to specify that my graph contains significant amount of cycles. – Gil Sep 20 '18 at 21:59
• 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 \}$$ – Neal Young Sep 21 '18 at 5:24
• 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. – Gil Sep 21 '18 at 7:36
• 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? – Gil Sep 21 '18 at 7:42
• 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? – Neal Young Sep 21 '18 at 13:09