An explicit vector algorithm for high-girth MaxCut

Jessica K. Thompson; Ojas Parekh; Kunal Marwaha

Source-linked AI summary

An explicit vector algorithm for high-girth MaxCut

Jessica K. Thompson, Ojas Parekh, Kunal Marwaha

arXiv:2108.12477v1Aug 27, 2021quant-phcs.DS

TL;DR

The paper addresses MaxCut approximation on d-regular graphs with girth at least 2k, where efficient guarantees remain limited. It constructs explicit vectors for the standard SDP and applies hyperplane rounding, simplifying Gaussian-wave methods. For d ≥ 3 and k ≥ 4, its guarantees exceed those of all classical and quantum algorithms known to the authors.

Problem
MaxCut lacks optimal, efficient approximation algorithms on most graph families, including regular graphs where optimal worst-case approximation guarantees remain unavailable.
Source: §1 · p. 2
Method
The algorithm explicitly constructs a feasible SDP vector solution with equal edge inner products and applies Goemans-Williamson hyperplane rounding.
Source: §1.1 · p. 4
Results
For d ≥ 3 and k ≥ 4, the approximation guarantees are better than those of all classical and quantum algorithms known to the authors.
Source: §1 · p. 3, §5 · p. 8
Takeaways & Limitations
The procedure provides a simple, explicit high-girth MaxCut guarantee while simplifying the Gaussian-wave-process approach.
Source: §1 · p. 3, §5 · p. 8
The analysis requires k to be upper bounded by the girth, although using k equal to graph diameter numerically improves the cut fraction and requires new analysis.
Source: §5 · p. 8

Abstract

from arXiv · show

We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on $d$-regular graphs of girth $\geq 2k$. For every $d \geq 3$ and $k \geq 4$, our approximation guarantees are better than those of all other classical and quantum algorithms known to the authors. Our algorithm constructs an explicit vector solution to the standard semidefinite relaxation of MaxCut and applies hyperplane rounding. It may be viewed as a simplification of the previously best known technique, which approximates Gaussian wave processes on the infinite $d$-regular tree.

1 Introduction

The paper targets efficient MaxCut guarantees on regular, high-girth graphs, where existing worst-case approximation and cut-fraction guarantees remain limited. It constructs explicit SDP vectors for hyperplane rounding, simplifying Gaussian-wave approaches while improving known classical and quantum guarantees.

1 Introduction

MaxCut is an NP-hard optimization problem, and performance can be measured by cut fraction or approximation ratio.The distinction matters because an approximation ratio can yield only a 1/2 cut-fraction guarantee on graphs with sufficiently small optimal cut fraction.Source: §1 · p. 2
Invariant Gaussian-process algorithms can approach cut fraction 1/2 + 2/(π√d), but their analyses involve infinite-tree eigenvectors and may lack computational-efficiency claims.The paper instead uses explicitly known eigenvectors of a finite path and reports better performance than de Boor (2019).Source: §1 · p. 3
For d ≥ 3 and k ≥ 4, the algorithm’s approximation guarantees exceed those of all algorithms known to the authors.The guarantee applies to d-regular graphs with girth at least 2k.Source: §1 · p. 3

1. Introduction

The optimization over k parameters reduces to finding a minimum eigenvector of a weighted path on k vertices, yielding a simpler implementation and analysis.The paper also gives a closed-form approximate solution that outperforms previous algorithms.Source: §1 · p. 3

1.1 A motivating example

The method constructs an explicit feasible SDP vector solution whose vectors have equal inner products on edges, then applies Goemans-Williamson hyperplane rounding.This avoids solving the SDP directly and is motivated by locally tree-like graph structure.Source: §1.1 · p. 4
The resulting explicit vector assignment outperforms depth-1 QAOA for every d and exceeds several classical and quantum guarantees as girth increases.The comparisons include Lyons (2017), depth-1 and depth-2 QAOA, the threshold algorithm, and its depth-2 extension in Marwaha (2021).Source: §1.1 · p. 4

2 Vector assignments to the semidefinite program

The algorithm explicitly constructs unit vectors for a d-regular graph of girth at least 2k, minimizes their common edge inner product through a finite eigenvalue problem, and applies Goemans-Williamson rounding. Its resulting cut guarantee is the best known for d ≥3 and k ≥4.

The vector assignment makes vi · vj identical on every edge and optimizes this common value under unit-length constraints.Source: §2 · p. 5
The minimum possible edge inner product is obtained as the minimum eigenvalue of a k × k matrix, with optimal coefficients taken from its corresponding eigenvector.Source: §2 · p. 5
Theorem 1 gives an explicit cut-size guarantee for every finite d-regular graph with girth at least 2k.Source: §2 · p. 5
The construction uses the minimum eigenvector of a hollow tridiagonal Toeplitz matrix, whose eigenvectors and eigenvalues are known in closed form.Source: §2 · pp. 5–6
Because arccos is decreasing, the optimized inner product yields a lower bound on the rounded cut fraction.Source: §2 · p. 6
For d ≥3 and k ≥4, the resulting cut fraction is the best known for d-regular graphs of girth at least 2k.Source: §2 · p. 6

3 Relationship to the Gaussian wave process

The explicit vector construction can be interpreted as a finite linear factor of an i.i.d. Gaussian process, connecting it to Gaussian-wave methods on the infinite d-regular tree. This formulation retains explicit finite-path eigenvectors while clarifying the relationship to prior existential constructions.

Hyperplane rounding can be represented by sampling x ∼ N(0n, Σ) with Σ = V^T V and taking coordinate signs, equivalently x = Vz for i.i.d. Gaussian z.Source: §3 · p. 6
The algorithm is a linear factor of an i.i.d. process used to approximate the Gaussian wave process in earlier work.Source: §3 · p. 6
Setting αℓ = 0 for all ℓ ≥ k recovers the first equation in the related Gaussian-wave formulation.Source: §3 · p. 6
The finite-path eigenvector construction avoids the technically complicated infinite-tree eigenvector analysis used by prior Gaussian-wave methods.Source: §3 · pp. 6–7
The finite construction uses only finitely many nonzero αℓ, whereas the earlier results require sufficiently high girth and do not explicitly treat girth as a parameter.Source: §3 · p. 7
Unlike the one-parameter approach of de Boor, this method obtains optimal values for the coefficients and is guaranteed to perform at least as well as linear-factor approaches using the same coefficient range.Source: §3 · p. 7

4 Comparison of performance guarantees

The explicit vector solution has stronger performance guarantees than Lyons (2017) and outperforms depth-1 and depth-2 QAOA and threshold algorithms across the stated degree and girth ranges.

Comparison with Lyons (2017)

The expected cut size from the explicit vector solution exceeds the guarantee of Theorem 4.2 in Lyons (2017).Table 1 compares relative expectations for the proposed solution and the previous Gaussian wave lower bound; all values are truncated.Source: §4 · p. 7, Table 1 · p. 8
For finite d-regular graphs of girth at least 2k, the explicit vector solution has a higher performance guarantee than Lyons (2017) for every k ≥3 and d ≥3.The proof handles the remaining cases (k = 3, 3 ≤d ≤9) and (k = 4, d = 3) by numerical calculation.Source: §4 · p. 7

Comparison with QAOA and threshold algorithms

For all k ≥3 and d ≥3, the explicit vector solution outperforms QAOA and the threshold algorithm at depths 1 and 2.Because the proposed performance increases with k while the competing algorithms increase with depth, the comparison uses k = 3 against depth-2 algorithms.Source: §4 · p. 8
2/π > 0.45 is the proposed algorithm’s large-d normalized value, exceeding QAOA (c∞≈0.41) and threshold (c∞≈0.42).The normalized value decreases with d for d ≥3; for example, c8 ≈0.454, while remaining higher than both algorithms at all d ≥3.Source: §4 · p. 8

Comparison with modified threshold algorithm

A modified threshold algorithm found by computer search outperforms the proposed solution at k = 3 for d ∈{3, 4, 5}, but not at k = 4.This comparison concerns a modified threshold algorithm identified over a large class of algorithms.Source: §4 · p. 8

5 Conclusions

The paper presents an explicit high-girth MaxCut procedure whose hyperplane-rounded SDP solution outperforms previously known classical and quantum guarantees. It also identifies practical extensions and open limitations, including unproved improvements and the possibility of better algorithms.

For girth g ≥ 8, the algorithm guarantees a higher cut fraction than all other classical and quantum algorithms considered.The procedure gives a simple, explicit solution to the MaxCut semidefinite program and uses hyperplane rounding.Source: §5 · p. 8
Setting k equal to the graph diameter improves the cut fraction numerically, but proving this requires a new analysis because the current analysis requires k to be bounded by the girth.The practical modification is therefore not covered by the present proof.Source: §5 · p. 8
The explicit vector technique can be applied to other optimization problems, including the independent set algorithm of Cs´oka et al. (2015), though it does not currently improve performance.A tighter bound could potentially lead to an improvement.Source: §5 · p. 8
Using the algorithm’s output as a warm start for a local threshold procedure could further improve the cut.Because the solution has a simple form, analytic bounds may be possible even though previous results are numerical.Source: §5 · pp. 8–9
No current algorithm provably achieves the optimal cut fraction on locally tree-like graphs, so better classical or quantum algorithms may exist.The existence of an optimal algorithm remains an open question, with approximate message-passing suggested as one possible direction.Source: §5 · p. 9