# The relationship between max-cut and max independent set

I know that Max Independent set problems are not equivalent to Mac-Cut problems. The cost function of Max-Cut can be described by the classical Ising model $$H = \frac{1}{2} \sum_{i,j\in E}(1 - Z_i Z_j),$$ and a maximum independent vertex set is an independent vertex set containing the largest possible number of vertices for a given graph, which seems to share the same cost function with Max-Cut. So why these two tasks are not equivalent?

• I have a feeling this won't always produce an independent set. Imagine a large complete bipartite graph. The max-cut/ind-set partition is obviously to take the vertices on one half of the graph. If we make a new graph by adding an edge between two vertices in one partition, the max-cut partition remains the same, but its no longer an independent set. May 7, 2022 at 19:24
• But, since both problems are NP-complete, they are equivalent (up to Turing reductions), so an Ising model ground state solver can still solve max-ind-set problems. May 7, 2022 at 19:27
• I retrospected the defination of MIS, thank you very much! May 8, 2022 at 13:13

I guess your formulation uses $$Z_i$$ variables with value $$\pm 1$$. I find it easier to work with binary variables $$X_i$$ with value $$0$$ or $$1$$. The two are completely equivalent, you can go from one to the other with a simple change of variables $$Z_i = 2 X_i - 1$$.
The cost function of Maximum Independent Set is: $$\sum_{i \in V} X_i - \sum_{i,j \in E} X_i X_j$$
The cost function of MaxCut is: $$\sum_{i,j \in E} \left[ X_i (1-X_j) + (1-X_i) X_j \right]$$
If you expand the cost function of MaxCut you will find a two-body term contribution of: $$-2 \sum_{i,j \in E} X_i X_j$$ but your one-body term will be: $$\sum_{i,j \in E} \left[ X_i + X_j \right] = 2 \sum_{i,j \in E} X_i$$ notice that the sum is on the edges, which means that each variable $$X_i$$ will appear a number of times equal to the number of edges it is involved in. The cost function of MaxCut then reads (up to a numerical factor): $$\sum_{i \in V} N_i X_i - \sum_{i,j \in E} X_i X_j$$ where $$N_i$$ is the number of neighbours of $$X_i$$. So you see the two cost functions are not the same.