Reducing optimization problem to decision problem

Question

I'm trying to reduce an optimization problem to a decision problem, more specifically, consider the Max-Cut problem in its decision version:
Given $(G=(V,E),k)$ as input, where $G$ is an undirected weighted graph (all weights are positive integers, formally: $w: E\rightarrow \mathbb{N}$ is the weight function) and $k\in\mathbb{N}$, one should decide whether there exist a cut $(V_1,V_2)$, s.t its weight is at least $k$, meaning $k\leq \sum _{u\in V_1, v\in V_2}w(u,v)$.
The optimization version is simply finding the maximum weighted cut.
What I'm trying to achieve is, given an algorithm $A$ that can solve the decision problem, I want to describe an algorithm that can find the maximum cut in $G$.
So, first of all, this is what I had in mind:

• Find the weight of the maximum cut in $G$ (this can be done with a simple for loop that starts with 1 and stops at $m$, where $m=\sum _{e\in E}w(e)$ while in each iteration the algorithm queries $A$), define $k$ to be the weight of the maximum cut.
• Initialize new set $S\leftarrow \phi$
• For $e\in E$ do:
  • Omit edge $e=(u,v)$ from $G$, to create new graph $G_e$.
  • If $A(G_e,k)=0$ (both ends of $e$ are at the same set), $S\leftarrow S\cup \left \{ u,v \right \}$
  • else if $A(G_e,k)=1$ then...(?)
    This is where I'm stuck, I'm not sure how can I tell which end of $e$ should be in $S$...
    In fact, I'm not even sure if this is the right way to do it.

Any help and thoughts will be appreciated.

Answer 1

Given the formulation of your decision problem, first of all notice that you can do binary search to find the max-cut weight $k$, rather than linear search. Secondly, when you test each edge, you get that either the two end points are in the same set, or the two end points are in different sets. Let $S$ be a set on one side of the cut, and let $x_u,x_v$ be boolean indicator variables for whether $u,v$ are in $S$. Then if edge $(u,v)$ crosses the cut, you want $(x_u,x_v) = (1,0)$ or $(0,1)$, and otherwise you want $(x_u,x_v) = (0, 0)$ or $(1,1)$. You can formulate this as a 2-sat problem and solve it in linear time (linear in the number of edges) to determine membership in set $S$. For example, if $(x_u,x_v) = (0, 0)$ or $(1,1)$ then you would add the two clauses $(x_u \vee \neg x_v) \wedge (\neg x_u \vee x_v)$ to your 2-sat formula.

Answer 2

After finding the set of edges which has no effect on the maxcut. remove the edges from the graph by making its cost 0. The remaining graph will be bipartite. we can use 2 color algorithm to get the bipartite sets.

This might be one of simple solution.