3
$\begingroup$

I have the following greedy algorithm for max cut problem:

  1. Initialization: $A \leftarrow \{v_1\}$ , $B \leftarrow \{v_2\}$
  2. For $v \in V − \{v_1, v_2\}$ do:

    if $d(v,A) \geq d(v,B)$ then $B \leftarrow B \cup \{v\}$,

    else $A \leftarrow A \cup \{v\}$.

  3. Output $A$ and $B$.

Here, $v_1$ and $v_2$ are arbitrary vertices in $G$ and $d(v,A)$ denotes the number of edges between vertex $v$ and set $A \subset V$.

To show that this is a factor 1/2 approximation algorithm, I used the upper bound that $opt \leq |E|$ and internal_degree(v) and external_degree(v).

But there is a problem, I can not say that when the algorithm terminates, we have external_degree(v) $\geq$ internal_degree(v) for all v (there is a counterexample) , of course since each vertex is check once so time complexity is O(n).

Is there any other way to show this factor?

$\endgroup$
4
$\begingroup$

Let us say that an edge $(v,w)$ belongs to $v$ if when $v$ is processed, $w \in A \cup B$, and that $(v_1,v_2)$ belongs to $v_2$. Denote by $N_v$ the number of edges belonging to $v$, and by $C_v$ the number of those edges that are cut by the algorithm. Step 2 ensures that $C_v \geq N_v/2$ (this clearly holds for $v = v_2$ as well). Therefore $\sum_v C_v \geq \sum_v N_v/2$. Finally, notice that $\sum_v N_v$ is the number of edges in the graph, and $\sum_v C_v$ is the size of the cut produced by the algorithm.

Here is a sketch of another proof. At any point in time, define the score of an edge $(u,v)$ as follows:

  • If $u,v \in A$ or $u,v \in B$, the score is 0.
  • If $u \in A$ and $v \in B$ or vice versa, the score is 1.
  • Otherwise the score is 1/2.

You can check that the initial score is at least half the number of edges, the score never decreases, and the final score is number of edges cut by the algorithm.

$\endgroup$
  • $\begingroup$ I really like your second approach, I had not thought about defining a "custom" function for this purpose. In case others are wondering: there are indeed cases where the score of an individual edge may decrease, but the sum of all scores never decreases. $\endgroup$ – Anthony Labarre Oct 24 '18 at 13:40

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.