학술

\textsc{Max-Cut} on Token Graphs

arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.

Abstract

Let $G$ be a graph on $n$ vertices, with a positive weight assigned to each edge.

A cut of $G$ is a partition of its vertices into two sets $X$ and $Y$; the weight of $(X,Y)$ is the sum of the weight of the edges of $G$ with one endpoint in $X$ and the other endpoint in $Y$.

The Max-Cut problem asks for the maximum weight, $m(G)$, of a cut of $G$.

The $k$-token graph of $G$, is the graph, $F_k(G)$, whose vertices are the $k$-subsets of vertices of $G$, two of them being adjacent when their symmetric difference is an edge of $G$.

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(F_k(G))$ in terms of $m(G)$.

We prove that $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)$; in the case when $k=c \cdot n$ for some constant $0 < c < 1$, we provide an example where this bound is off by a multiplicative constant factor.

We also show bounds for $m(F_k(G))$ for various classes of graphs $G$.

Finally, we consider the algorithmic complexity of finding $m(F_k(G))$, showing it to be NP-complete for a constant $k$, and giving evidence that, when the weights take finitely many values, it is not NP-hard for $k\geq n^{\delta}$ for any constant $\delta>0$.

관련 뉴스