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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ 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. $\endgroup$– xzkxyzMay 7, 2022 at 19:24
-
1$\begingroup$ 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. $\endgroup$– xzkxyzMay 7, 2022 at 19:27
-
$\begingroup$ I retrospected the defination of MIS, thank you very much! $\endgroup$– finelyMay 8, 2022 at 13:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It's true as stated in the comments that one problem can be reduced to the other, but I'm not sure where you got the information that the two cost functions are the same (in fact they are not, otherwise they would be the same exact problem).
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] $$
You can find these cost functions in standard references such as Boros 2002.
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.
