Question 14: Let G = (V, E) be a graph. A cut in G is a partition of …

Let $G = (V, E)$ be a graph. A cut in $G$ is a partition of $V$ into two sets. Let $S \subseteq V$ be a subset of vertices. The cost of the cut $(S, V \backslash S)$, denoted by cost$(S)$, equals the number of edges between $S$ and $V \backslash S$, i.e., the size of the set $\{\{x, y\} \in E \mid x \in S, y \in V \backslash S\}$. The edges that have one endpoint in $S$ and the other in $V \backslash S$ are said to cross the cut.

The Maximum Cut Problem takes a graph $G = (V, E)$ as input and the objective is to find a cut with maximum cost.

Based on the above data, answer the given subquestions.

For $q \geqslant 1$, a $q$-approximation algorithm for maximum cut is an algorithm that is guaranteed to produce a cut whose cost is at least $\frac{1}{q}$ of the cost of the optimal cut of the input instance.

Suppose we can devise an algorithm that, given a graph $G$ on $m$ edges, is guaranteed to find a cut whose cost is at least $\frac{m}{2}$. Such an algorithm would be: