betaFeedback

WorksMathematics

Max-Cut on Token Graphs

Abstract

Let GG be a graph on nn vertices, with a positive weight assigned to each edge. A cut of GG is a partition of its vertices into two sets XX and YY; the weight of (X,Y)(X,Y) is the sum of the weight of the edges of GG with one endpoint in XX and the other endpoint in YY. The Max-Cut problem asks for the maximum weight, m(G)m(G), of a cut of GG. The kk-token graph of GG, is the graph, Fk(G)F_k(G), whose vertices are the kk-subsets of vertices of GG, two of them being adjacent when their symmetric difference is an edge of GG. 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 m(Fk(G))m(F_k(G)) in terms of m(G)m(G). We prove that m(Fk(G))≥(n−2k−1)m(G)m(F_k(G))\geq\binom{n-2}{k-1}m(G), and that this bound is tight up to a multiplicative factor of 1+O(k/n)1+O(k/n); in the case when k=c⋅nk=c \cdot n for some constant 0<c<10 < c < 1, we provide an example where this bound is off by a multiplicative constant factor. We also show bounds for m(Fk(G))m(F_k(G)) for various classes of graphs GG. Finally, we consider the algorithmic complexity of finding m(Fk(G))m(F_k(G)), showing it to be NP-complete for a constant kk, and giving evidence that, when the weights take finitely many values, it is not NP-hard for k≥nδk\geq n^δ for any constant δ>0δ>0.

Paper details

vlnc:W_2qqy42qq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Large language models

View statement
Looking for related papers…