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.


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.

  • $\begingroup$ Thanks for the help, but isn't the 2-sat problem NP-Complete? How can I find an assignment that satisfies the formula after creating it, in polynomial time? $\endgroup$ Apr 20 '14 at 21:09
  • $\begingroup$ And what clauses should I add for if $(x_u,x_v)=(1,0)$ or $(0,1)$? should it be $(\neg x_v\vee \neg x_u)\wedge (x_v\vee x_u)$? $\endgroup$ Apr 20 '14 at 21:25
  • $\begingroup$ @so.very.tired Yes that's exactly the clause you should add if it's (1,0) or (0,1). And 2-sat has a polynomial time solution (even linear time solution), see. e.g. en.wikipedia.org/wiki/2-satisfiability $\endgroup$ Apr 20 '14 at 21:31
  • $\begingroup$ What if there are more than one max-cut solutions in the original graph? For example, consider the complete graph with 4 nodes. $\endgroup$
    – hengxin
    Jan 22 '15 at 14:01

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.


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.