2
$\begingroup$

Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for the decision problem as a subroutine

MAX CUT

INSTANCE: A graph G = (V,E), a function c giving each edge e ∈ E an integer capacity c(e) and an integer B. QUESTION: (D) Does the graph have a cut of size at least B? (O) Find a cut with the maximum size.

Algorithm

Find the maxcut value k by binary search from 1 to m using decision subroutine
     where m is global maximum value
for all edge e ∈ E
  select a edge e=(u,v) ∈ E, construct G' after removing egde e from G
  if SUBROUTINE(G',k)=1 =>removal of edge has no effect on MAXCUT
    add u and v to same set S or S'(use 2 SAT to determine which group)
  else
    add u and v to different sets S or S'

This algorithm works only if there is only one MAXCUT solution in the graph(i have considered only unweighted graph). In case of a complete graph this algorithm fails as there is more than one MAXCUT solution present.

consider 4 nodes complete graph with edges (1,2),(1,3),(1,4),(2,3),(2,4),(3,4). The algorithm fails because when we remove any one edge still there is a MAXCUT of size 4.

Please suggest any other algorithm which works or any additional condition which can solve this problem.

Thanks in advance

$\endgroup$