WorksMathematics
Max-Cut on Token Graphs
Abstract
Let be a graph on vertices, with a positive weight assigned to each edge. A cut of is a partition of its vertices into two sets and ; the weight of is the sum of the weight of the edges of with one endpoint in and the other endpoint in . The Max-Cut problem asks for the maximum weight, , of a cut of . The -token graph of , is the graph, , whose vertices are the -subsets of vertices of , two of them being adjacent when their symmetric difference is an edge of . The phase-reconstruction problem for Heisenberg antiferromagnets in physics can be rephrased as a Max-Cut problem on token graphs. Motivated by this, we study the Max-Cut problem on token graphs, mainly when all edges are assigned the same weight. Our main focus is to bound in terms of . We prove that , and that this bound is tight up to a multiplicative factor of ; in the case when for some constant , we provide an example where this bound is off by a multiplicative constant factor. We also show bounds for for various classes of graphs . Finally, we consider the algorithmic complexity of finding , showing it to be NP-complete for a constant , and giving evidence that, when the weights take finitely many values, it is not NP-hard for for any constant .