# Greedy max k-cut approximation algorithm

I'm trying to formulate a greedy algorithm for the Max k-cut problem:

Let's have an not oriented graph $G(V,E)$, each edge $e \in E$ has its weight $w_e$. The goal of the algorithm is to divide all vertices $v\in V$ to $k$ disjunct sets $V_1,\dots,V_k$ and maximize the weight of the edges that are connecting these sets.

I have come up with the following algorithm:

1. Take any vertex $v$ from $v\in V$ and add it into a queue $Q$.
2. while $Q$ is not empty
1. take the first vertex from the queue. (Let's name it $u$.)
2. $p_i:=0$ for $i\in\{1, 2, \dots, k\}$
3. for each neighbour $n\in \text{Neighbours}(u)$ consider the edge $\{u, n\}$.
1. $p_i := p_i + 1$ if $n\in V_i$
4. Add the vertex $u$ to the set $V_i$ that has the lowest $p_i$.
5. Add all neighbours of $u$ that have not been yet assigned to any set to the queue $Q$.
3. return $V_1, V_2, \dots, V_n$

It is basically a greedy breadth-first search algorithm, that adds each vertex to the best set based on information of the neighbours that have already been added.

Now I am trying to analyze the algorithm, if it is an $\left(1-\frac{1}{k}\right)$-approximation algorithm, but I am having hard time finding where to start.

Could someone please give me some hints on how to analyze this algorithm?

• You use statements such as for each. Could you add indents to your pseudocode? In particular it is not clear which lines belong to the for-statement in the line 3. Also it is not clear whether for-statements in line 3 and 5 are nested. – fade2black Dec 8 '17 at 14:09
• I have added indentation, I hope it is more understandable now. – janjaromirhorak Dec 8 '17 at 14:53
• ...and I removed one line, that might be misleading. – janjaromirhorak Dec 8 '17 at 17:59