Triangles Improve 0.878 Approximation for Maxcut

George, Fredie; Louis, Anand; Paul, Rameesh

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.27

Triangles Improve $0.878$ Approximation for Maxcut

Fredie George

Indian Institute of Science, Bangalore, India Anand Louis

Indian Institute of Science, Bangalore, India Rameesh Paul

Indian Institute of Science, Bangalore, India

Abstract

Maxcut is a fundamental problem in graph algorithms, extensively studied for its theoretical and practical significance. The goal is to partition the vertex set of a graph $G=(V,E)$ into disjoint subsets $S$ and $V\setminus S$ so as to maximize the number of edges crossing the cut $(S,V\setminus S)$ . The seminal work of Goemans and Williamson [39] introduced a semidefinite programming (SDP) based algorithm achieving a $\alpha_{\mathsf{GW}}\approx 0.87856$ -approximation for general graphs, guaranteed to be optimal under the Unique Games Conjecture [56, 57].

We revisit the Goemans–Williamson SDP and prove that the standard Maxcut SDP achieves a $\left(\alpha_{\mathsf{GW}}+\Omega(1)\right)$ -approximation whenever the input graph contains $\Omega\left(\left\lvert E\right\rvert\right)$ edge-disjoint triangles. Our analysis builds on classical rounding techniques studied in [39, 76] and introduces a refined understanding of the SDP solution structure in regimes where the previous guarantees are tight. Our result identifies a simple combinatorial property that may be satisfied by many natural graph classes.

As applications, we show that unit ball graphs and graphs satisfying a spectral transitivity condition (as studied in [40, 12]) meet our structural criterion, and therefore we get better than $\alpha_{\mathsf{GW}}$ approximation guarantees for them. Our algorithm runs in nearly linear time $\widetilde{\mathcal{O}}\left(\left\lvert E\right\rvert\right)$ , offering a more practical alternative to the PTAS of [48] for unit ball graphs, which has exponential dependence on the approximation parameter.

Keywords and phrases:

Approximation Algorithms, Maxcut, Semidefinite Programming, Edge-disjoint Triangles, Unit Ball Graphs, Spectral Triadic Graphs

Category:

APPROX

Funding:

Anand Louis: Supported by the Walmart Center for Tech Excellence at IISc, and SERB award CRG/2023/002896.

Rameesh Paul: Supported by Prime Minister’s Research Fellowship, India.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis ; Theory of computation

\rightarrow

Graph algorithms analysis

Acknowledgements:

We thank Rahul Saladi for valuable discussions. We thank anonymous reviewers for their insightful comments.

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.27

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

We study the Maxcut problem, a fundamental problem in combinatorial optimization. We are given a graph $G=(V,E)$ , and the goal is to partition the vertex set $V$ into disjoint subsets $S$ and $V\setminus S$ such that the number of edges crossing the cut $(S,V\setminus S)$ is maximized. Maxcut is one of Karp’s original NP-hard problems [53] and has been extensively studied both for its theoretical depth and its wide range of applications, including areas such as VLSI design [23], statistical physics [9], and image segmentation [15].

A simple algorithm that outputs a random cut in the graph achieves a $0.5$ -approximation. For a long time, this remained the best known algorithm for the problem, until the seminal work of Goemans and Williamson [39] introduced a semidefinite programming (SDP) based algorithm that achieves roughly $0.87856$ -approximation factor. The exact value of the approximation ratio is known as the Goemans-Williamson constant $\alpha_{\mathsf{GW}}\approx 0.87856$ . The guarantee is also tight in the worst-case, due to an integrality gap construction [36], and is guaranteed to be optimal assuming the Unique Games Conjecture [56, 57].

While the SDP achieves $\alpha_{\mathsf{GW}}$ -approximation ratio in the worst-case instances, it is natural to ask whether stronger guarantees can be obtained on more structured inputs. In this work, we identify a simple combinatorial property, namely the presence of many edge-disjoint triangles, that suffices to improve the approximation ratio achieved by the Goemans–Williamson SDP. We show that this property holds for several natural classes of graphs, including unit ball graphs and certain real-world networks. Our results thus provide provable guarantees explaining improved SDP performance on structured instances, offering a step towards a broader understanding of approximation algorithms beyond the worst-case.

1.1 Our Results and Techniques

We start by presenting our main result about the Maxcut SDP,

Theorem 1 (Informal Version of Theorem 18).

Given a graph $G=(V,E)$ , having optimal Maxcut value $\mathsf{opt}(G)$ , there exists an algorithm $\mathsf{Alg}(G)$ running in $\widetilde{\mathcal{O}}(|E|)$ time such that,

\operatorname*{\mathbb{E}}[\mathsf{Alg}(G)]\geq\left(\alpha_{\mathsf{GW}}+% \Omega\left(\frac{\Delta(G)}{\left\lvert E\right\rvert}\right)^{2}\right)% \mathsf{opt}(G),

where $\Delta(G)$ denotes the number of edge-disjoint triangles in $G$ .

Our approach involves a refined analysis of the standard Maxcut SDP. The original analysis of Goemans and Williamson [39], and subsequent follow-up works [76, 35], already show an $\Omega(1)$ improvement (over $\alpha_{\mathsf{GW}}$ ) in certain regimes of sdpopt, the SDP optimum value. We leverage these results as black-box components. Our main technical contribution is to show that for the remaining regimes of sdpopt, those where there are no known guarantees, the approximation ratio can still be improved by an additive factor of $\Omega(\Delta(G)/\left\lvert E\right\rvert)^{2}$ . This yields a uniformly improved $(\alpha_{\mathsf{GW}}+\Omega(1))$ -approximation ratio in graphs whenever the number of edge-disjoint triangles $\Delta(G)=\Omega(\left\lvert E\right\rvert)$ .

Although SDP-based algorithms are often considered computationally expensive, recent developments [3, 65, 68] have enabled fast implementations for these on a broad class of constraint satisfaction problems (CSP), including Maxcut .

We then proceed to identify natural classes of graphs where this structural condition holds. Combined with Theorem 1, this suffices to show an improved $\left(\alpha_{\mathsf{GW}}+\Omega(1)\right)$ -approximation guarantees. Specifically, we give a constructive proof showing that unit ball graphs, including unit interval graphs, unit disk graphs, and their higher-dimensional generalizations contain $\Omega(\left\lvert E\right\rvert)$ edge-disjoint triangles.

Proposition 2 (Informal Version of Theorem 31).

For any geometric intersection graph of unit balls in $\mathbb{S}^{k-1}$ with degree $d\geq 6(2)^{3k}$ , it has $\Omega_{k}\left(\left\lvert E\right\rvert\right)$ many edge-disjoint triangles.

Corollary 3.

For any geometric intersection graph of unit balls in $\mathbb{S}^{k-1}$ with average degree at least $6(2)^{3k}$ , there exists an algorithm achieving a $\left(\alpha_{\mathsf{GW}}+\Omega(1)\right)$ -approximation for the Maxcut problem on $G$ .

We note that [48] previously gave a PTAS (Polynomial Time Approximation Schemes) for Maxcut on unit disk graphs via a dynamic programming approach that partitions the graph into dense components, which are then solved using the dense graph algorithm of [4]. They also note that their techniques extend to general unit ball graphs.

$\blacktriangleright$ Remark 4.

We contrast our running time with that of the algorithm by the work [48], which achieves a PTAS for Maxcut on unit ball graphs. When combined with the fast dense graph algorithm of [60] as a subroutine, their overall running time becomes $\mathcal{O}(\left\lvert E\right\rvert+2^{\mathcal{O}(1/\upsilon^{2})})$ . The exponential dependence on $\upsilon$ makes the running time of their algorithm impractically large even for values of $\upsilon$ as large as $\upsilon=0.1$ .

Our work also considers Maxcut SDP on models inspired by real world networks considered by [12] which satisfy a spectral criterion of $\tau(G)=\Omega(1)$ . We elaborate on the spectral condition $\tau(G)$ in Section 4.2; intuitively, it captures a form of triadic closure commonly observed in social networks and community-structured networks.

Lemma 5 (Section 3 in [12]).

For any regular graph $G$ satisfying a spectral condition $\tau(G)=\Omega(1)$ , the number of edge-disjoint triangles in graph is $\Omega(\left\lvert E\right\rvert)$ .

$\blacktriangleright$ Remark 6.

Some degenerate unit ball graphs, such as path graphs contain no triangles. However, if the satisfy a mild constant lower bound on the average degree, they indeed have high edge-disjoint triangle density. We also show that graphs satisfying the spectral criterion in the work [12] have large number of edge-disjoint triangles. For graphs with low average degree ( $\left\lvert E\right\rvert=\mathcal{O}(\left\lvert V\right\rvert)$ ), we can alternatively use the SDP-based algorithm of [44], which achieves a $(\alpha_{\mathsf{GW}}+\Omega(1))$ -approximation, albeit with higher running time due to additional $l_{2}^{2}$ -triangle inequality constraints in their SDP

1.2 Related Work

Maxcut Problem

The problem has been extensively studied across various settings. As noted earlier, in the worst-case graphs, a simple $0.5$ -approximation was known from [32, 66] which was best until [39] gave an $\alpha_{\mathsf{GW}}$ -approximation algorithm. The SDP is also known to be tight due to an integrality gap example of [36]. On the hardness front, Maxcut is APX-hard in general graphs, and has a $16/17$ -hardness of approximation due to [46, 71]. Further, $\alpha_{\mathsf{GW}}$ is also conjectured to be the optimal approximation ratio achievable assuming UGC [56, 57].

The work of [70] showed how to achieve a better than $0.5$ -approximation without using SDP. They show that the eigenvector corresponding to the smallest eigenvalue of the graph’s adjacency matrix could be used to obtain at least $0.531$ -approximation algorithm, the bound was later improved to $0.614$ by [67].

The problem has also been considered in various special graph classes. On the algorithmic front, [43] shows that the problem can be solved for planar graphs. The work [41] shows that the problem is polynomial time solvable for line graphs. The work [15] shows how to solve the problem efficiently on bounded treewidth graphs. The work [19] gives an efficient algorithm for co-bipartite chain graphs. The approximation guarantees also have been studied extensively in works of [25, 52, 70]. The work [4] showed how LP relaxations can yield a PTAS for the problem on dense graphs. The work [60] later showed that a greedy randomized algorithm can give a PTAS for the problem, with a runtime of $\mathcal{O}\left(\left\lvert E\right\rvert+2^{\mathcal{O}(1/\upsilon^{2})}\right)$ .

The work [13] shows that the problem remains NP-hard on cubic graphs. The work [41] showed it is NP-hard for total graphs. The work [15] then showed that it remains NP-hard for chordal graphs, split graphs, co-bipartite graphs, and tripartite graphs. Lower bounds on $\mathsf{opt}(G)$ for the problem were also studied in the works of [32, 31, 22].

Maxcut SDP

SDP algorithms are central to state-of-the-art solutions for a range of problems, such as graph coloring [54], sparsest cut [5], correlation clustering (maximizing agreements version) [69], maximizing cut norm of matrix [2], max bisection [6], maxcut in general graphs [39], among others. While SDP algorithms are traditionally viewed as “slow”, recent developments [3, 68] enable fast implementation of these algorithms for many Constraint Satisfaction Problems (CSPs) such as the Maxcut problem.

The Maxcut SDP itself has received a lot of attention over the years. The SDP formulation itself was originally proposed an earlier work of [29], and [39] gave a randomized rounding algorithm which produced a cut having (in expectation) at least $\alpha_{\mathsf{GW}}$ fraction of the edges in the optimal cut. The work [76] gave a rounding algorithm based on “outward rotations”, which we review in Section 2.2. Later [35] further generalized this with the RPR² rounding procedure; which they claim is at least as good as algorithm by [76] and potentially better than [76] (Theorem 5.2 in [35]), though this improvement was formally demonstrated only for particular values of $\mathsf{opt}(G)$ . This culminated with the work of [64] that characterized the entire approximability curve of the Maxcut SDP on general graphs.

For bounded degree graphs, the work of [34] showed that the Maxcut SDP combined with a local algorithm achieves a $\alpha_{\mathsf{GW}}+\Omega(1/d^{4})$ -approximation algorithm, which was later improved to $\alpha_{\mathsf{GW}}+\Omega\left(1/d^{3}\right)$ in the work [37], and recently improved to $\alpha_{\mathsf{GW}}+\Omega(1/d^{2}\log d)$ -approximation by the work [44], where $d$ is the maximum degree of the graph. For dense graphs and their spectral generalizations, the works of [10, 42] showed that one can obtain a PTAS for this problem in time $n^{\mathcal{O}(1/\varepsilon)}$ by using a higher-order SDP (degree $\mathcal{O}(1/\varepsilon)$ sum of squares hierarchy). Combining these results with ideas from [48], one can also obtain a PTAS for unit ball graphs (albeit with higher running time compared to [60]).

Fast SDP Solvers

The work [3] developed the framework of approximately solving SDPs using the Matrix Multiplicative Weight Update method. The work [68] builds on this to develop a fast SDP solver by designing an efficient separation oracle. When paired with the general rounding algorithm of [65], it yields an algorithm for approximately solving a canonical SDP relaxation for a CSP with $n$ variables and $m$ constraints (up to a $\left(1-\upsilon\right)$ factor for some $\upsilon>0$ ) in running time $\mathcal{O}(m\,\mathsf{poly(log}n){\sf poly}(1/\upsilon))$ .

Geometric Intersection Graphs

Geometric intersection graphs are graphs where vertices represent geometric objects, such as intervals, disks, rectangles, polygons etc., and there is an edge between vertices if the corresponding objects overlap. These graphs have applications in wireless networks [45], resource allocation [7], protein sequencing [50], VLSI design [23], statistical physics [9], and image segmentation [15]. An important class of geometric intersection graphs are interval graphs. It is well-known that many NP-hard problems become easy on interval graphs, such as graph isomorphism [17], maximum clique/independent set problem [47], hamiltonian cycle [55], maximum dominating set [24], graph coloring [75, 21], minimum vertex cover [59].

Maxcut in Geometric Intersection Graphs

One may conjecture that Maxcut problem follows a similar narrative, and this was posed as an open question in [49]. Earlier works due to [16] and then [18] claimed a polynomial time algorithm for the problem, however both proofs were subsequently reported to be incorrect due to the works of [14] and [58] respectively. The problem thus remained open for a very long time, and the mystery was resolved only recently in [1] where they show that the problem is NP-hard on general interval graphs.

An interval count of an interval graph is defined as the number of distinct interval lengths in an interval graph, and thus unit interval graphs have interval count $1$ . The work of [28] showed that the problems is NP-hard even if interval count is $4$ . More recently, [11] improved upon this to show that Maxcut remains NP-hard even when interval count is $2$ . However, whether the problem is NP-hard for unit interval graphs (interval count $1$ ) remains an open question. The work of [30] established that the problem is NP-hard on unit disk graphs.

On the algorithmic front, [48] proposed a PTAS (polynomial time approximation scheme) for the problem on unit ball graphs. They give a graph partitioning algorithm that employs a Dynamic Programming approach to partitions the graph into dense components such that $(1-\upsilon)$ -fraction of edges lie inside these components. For dense components they apply the dense graph Maxcut algorithm of [4] and obtain an $\left(1-\mathcal{O}(\upsilon)\right)$ -approximation with running time $\mathcal{O}\left(\left\lvert E\right\rvert+2^{\mathcal{O}(1/\upsilon^{2})}\right)$ , which is impractically large for even large values of $\upsilon$ (say $\upsilon=0.1$ ).

Real World Graphs

While the performance of Maxcut SDP on random Erdős–Rényi $G(n,p)$ graphs has received considerable attention [27, 62, 38, 61], such models fail to capture many key features of real-world networks, such as community structure, heavy-tailed degree distributions, and high clustering coefficients. There are various models proposed to mimic such real-world features as: the Preferential Attachment Model due to [8], the small-world network model due to [74], and more recently frameworks such as the combinatorial triangle-dense decompositions by [40] and the “spectral triadic decomposition” by [12]. These capture the role of triangles and higher-order motifs in capturing the nuanced community structure of real-world networks. We will discuss real-world graphs in detail in Section 4.2.

2 Overview and Discussion

We start by setting up some notation in Section 2.1. We review the proof of the algorithm due to [39] and the critical values where their analysis is tight. Then we discuss the improvement by [76], followed by our algorithm. In Section 2.4, we present an overview of the proof and our main result. The proof is in two parts, first we show (formally in Section 3) that proving a certain structural property about the SDP can lead to an improved approximation algorithm. Later, in Section 4 we show that the desired property holds for some natural class of graphs.

2.1 Notation

Let $E(U,V)$ denote the set of edges from set $U$ to set $V$ , and $K_{n}$ denote the complete graph on $n$ vertices. We let $T(G)$ denote the maximum number of triangles in a graph, and $\Delta(G)$ denote the maximum number of edge-disjoint triangles in a graph $G$ . We let $\mathcal{N}(0,1)^{n}$ denote a multivariate normal distribution in $\mathbb{R}^{n}$ where each of the $n$ components is an independent standard normal random variable with mean $0$ and variance $1$ .

2.2 Preliminaries

We recall the Maxcut SDP relaxation due to [29], typically presented in vector formulation,

SDP 7 (Maxcut SDP).

$\displaystyle\quad\max\quad$	$\displaystyle\sum_{\left\{i,j\right\}\in E}\frac{1}{2}\left(1-\left\langle% \mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)$
subject to
$\displaystyle\qquad\qquad\left\lVert\mathbf{v}_{i}\right\rVert^{2}$	$\displaystyle=1$	$\displaystyle\forall i\in V$

The SDP was analyzed using a novel randomized rounding procedure by [39] where they show how to obtain an $\alpha_{GW}$ approximation algorithm (denoted $\mathsf{Alg}_{\mathsf{GW}}$ ) for the Maxcut problem. Their rounding algorithm samples a random hyperplane by sampling the normal (a random $n$ dimensional gaussian vector $\mathbf{g}\sim\mathcal{N}(0,1)^{n}$ ) and computes the set $S_{g}=\left\{i:\left\langle\mathbf{v}_{i},\mathbf{{g}}\right\rangle\geq 0\right\}$ . They output the edges cut by the algorithm as $E(S_{g},V\setminus S_{g})$ . We reproduce their analysis below. We let $\mathsf{opt}_{\mathsf{MC}}=\mathsf{opt}(G)$ denote the optimal value for the Maxcut problem in $G$ and ${\sf sdpopt}=\mathsf{opt}\left(\text{\lx@cref{creftype~refnum}{sdp:maxcut_sdp}% }\right)$ .

Definition 8 (GW Critical Constants).

We consider the functions $h_{r}(t)$ and $g_{r}(t)$ below from the analysis in works of [39] and [76],

\displaystyle h_{r}(t)=\frac{\arccos\left(r\left(1-2t\right)\right)}{\pi}\text% { and let }g_{r}(t)=\frac{h_{r}(t)}{t}\text{ where }t\in(0,1]\text{ and }r\in[% 0,1].

We define the unique minimum value of $g_{1}(t)$ as $\alpha_{\mathsf{GW}}$ ( $\approx 0.87856$ ) which is obtained for $t=t_{c}\approx 0.84458$ . Also, we let $\theta_{c}=\pi h_{1}(t_{c})=\arccos\left(1-2t_{c}\right)\approx 133.56345^{\circ}$ .

Theorem 9 (Theorem 3.3 in [39]).

For a graph $G=(V,E)$ the following holds,

\displaystyle\operatorname*{\mathbb{E}}\limits_{\mathbf{g}\sim\mathcal{N}(0,1)% ^{n}}\Bigl[\left\lvert E(S_{g},V\setminus S_{g})\right\rvert\Bigr]\geq\alpha_{% \mathsf{GW}}\,\mathsf{opt}_{\mathsf{MC}}

Proof.

Their proof is a term by term analysis of the edges cut by the rounding algorithm and it’s contribution to the SDP objective value. Let $\theta_{ij}\stackrel{{\scriptstyle\textup{def}}}{{=}}\arccos\left({\left% \langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle}\right)$ and we note,

	$\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}$	$\displaystyle\Bigl[\left\lvert E(S_{g},V\setminus S_{g})\right\rvert\Bigr]=% \sum_{\left\{i,j\right\}\in E}\operatorname*{\mathbb{E}}_{\mathbf{g}\sim% \mathcal{N}(0,1)^{n}}\Bigl[\mathbf{1}_{\left\{i,j\right\}\in E(S_{g},V% \setminus S_{g})}\Bigr]$
		$\displaystyle=\sum_{\left\{i,j\right\}\in E}\operatorname*{\mathbb{P}}_{% \mathbf{g}\sim\mathcal{N}(0,1)^{n}}\left[\left\{i,j\right\}\in E(S_{g},V% \setminus S_{g})\right]$
		$\displaystyle=\sum_{\left\{i,j\right\}\in E}\frac{\theta_{ij}}{\pi}\qquad% \qquad\quad\qquad\qquad\,\,\,\,\left(\text{Look at the plane spanned by $% \mathbf{v}_{i}$ and $\mathbf{v}_{j}$}\right)$
		$\displaystyle=\sum_{\left\{i,j\right\}\in E}\left(\frac{2\theta_{ij}}{\pi\left% (1-\cos(\theta_{ij})\right)}\right)\left(\frac{1}{2}\left(1-\left\langle% \mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right)$
		$\displaystyle=\sum_{\left\{i,j\right\}\in E}\left(\frac{\arccos(1-2t_{ij})}{% \pi t_{ij}}\right)\left(\frac{1}{2}\left(1-\left\langle\mathbf{v}_{i},\mathbf{% v}_{j}\right\rangle\right)\right)\,\,\,\,\left(\text{Let }t_{ij}=(1-\cos\left(% \theta_{ij}\right))/2\right)$
		$\displaystyle\geq\sum_{\left\{i,j\right\}\in E}g_{1}(t_{ij})\left(\frac{1}{2}% \left(1-\left\langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right)% \geq\alpha_{\mathsf{GW}}\sum_{\left\{i,j\right\}\in E}\left(\frac{1}{2}\left(1% -\left\langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right)$
		$\displaystyle=\alpha_{\mathsf{GW}}\,{\sf sdpopt}\geq\alpha_{\mathsf{GW}}\,% \mathsf{opt}_{\mathsf{MC}}\$

$\hfill\blacktriangleleft$

Since the above is an edge by edge analysis, it is tight when the function $g_{1}(t)$ has the same value i.e., $g_{1}(t_{e})=g_{1}(t_{c})$ for all edges $e\in E$ , which occurs when $t_{ij}=t_{c},\forall\left\{i,j\right\}\in E$ and $\theta_{ij}=\theta_{c},\forall\left\{i,j\right\}\in E$ . We note that when this happens, ${\sf sdpopt}=t_{c}\left\lvert E\right\rvert$ .

When the ${\sf sdpopt}$ value is strictly larger than $t_{c}\left\lvert E\right\rvert$ , there are edges for which $t_{e}>t_{c}$ . In this case, for such edges we have that $g_{1}(t_{e})>\alpha_{\mathsf{GW}}$ . Then the work [39] gives an improved approximation guarantee presented below,

Theorem 10 (Theorem 3.1.1 in [39]).

For a graph $G=(V,E)$ and some $\varepsilon_{u}>0$ such that ${\sf sdpopt}\geq\left(t_{c}+\varepsilon_{u}\right)\left\lvert E\right\rvert$ we have that, $\operatorname*{\mathbb{E}}\limits_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}\Bigl[% \left\lvert E(S_{g},V\setminus S_{g})\right\rvert\Bigr]\geq g_{1}(t_{c}+% \varepsilon_{u})\,\mathsf{opt}_{\mathsf{MC}}$ .

$\blacktriangleright$ Remark 11 (Lemma 3.5 in [39]).

For a choice of $\varepsilon_{u}>0$ , we have that $g_{1}(t_{c}+\varepsilon_{u})>g_{1}(t_{c})$ since $t_{c}$ is the unique minimizer of $g_{1}(t)$ .

However, a similar argument can’t be made for the light maxcut setting, i.e., where ${\sf sdpopt}=(t_{c}-\varepsilon_{l})\left\lvert E\right\rvert$ for some $\varepsilon_{l}>0$ . This is since, it may be possible that for a $(1-\varepsilon_{l})$ fraction of the edges $t_{e}=t_{c}$ while it is $0$ for the other $\varepsilon_{l}\left\lvert E\right\rvert$ edges. We note that if the ${\sf sdpopt}$ value is very close to $1/2$ , then indeed a random cut gives improved approximation guarantees. However for ${\sf sdpopt}\geq\left\lvert E\right\rvert/2t_{c}\stackrel{{\scriptstyle\textup% {def}}}{{=}}\alpha_{\textsf{random}}\left\lvert E\right\rvert\approx 0.56911% \left\lvert E\right\rvert$ , the approximation factor of a random cut is also strictly smaller than $\alpha_{\mathsf{GW}}$ . Therefore, for a large range of values for ${\sf sdpopt}$ in the interval $[\alpha_{\textsf{random}}\left\lvert E\right\rvert,t_{c}\left\lvert E\right\rvert)$ , [39] can only guarantee a $\alpha_{\mathsf{GW}}$ -approximation.

This is where the work [76] introduced a novel rounding technique and analysis that gives an algorithm (denoted $\mathsf{Alg}_{\mathsf{rot}}$ ) which improves the approximation guarantees in the light maxcut setting. Their rounding algorithm is based on “outward rotations”, an idea proposed by [63]. We present their algorithm next.

Zwick’s Outward Rotation Algorithm [76]

Input. The algorithm takes a graph $G=(V,E)$ and a parameter $\tau$ as input.
Algorithm. We present their algorithm from [76] denoted $\mathsf{Alg}_{\mathsf{rot}}(G,\tau)$ below,

$\blacksquare$

Solve the Maxcut SDP to obtain a collection of vectors $\left\{\mathbf{v}_{1},\mathbf{v}_{2},\dots,\mathbf{v}_{n}\right\}$ .
$\blacksquare$

They embed the SDP vectors in $\mathbb{R}^{2n}$ (by padding them with $n$ zeroes).
$\blacksquare$

An angle $\phi$ is obtained by solving the below system of equations in variables $r, t$ ,

$\displaystyle\frac{\arccos(r(1-2t))-\arccos(r)}{t}$ $\displaystyle=\frac{2r}{\sqrt{1-r^{2}(1-2t)^{2}}}$ (1)

$\displaystyle\frac{1-\frac{t\left\lvert E\right\rvert}{{\sf sdpopt}}}{\sqrt{1-% r^{2}}}$ $\displaystyle=\frac{1-2t}{\sqrt{1-r^{2}(1-2t)^{2}}}$ (2)

and letting $\phi=\arccos\left(\sqrt{r}\right)$ . If ${\sf sdpopt}\geq\tau\left\lvert E\right\rvert$ , they set $\phi=0^{\circ}$ .
$\blacksquare$

Consider an orthogonal subspace of vectors $\left\{\mathbf{u}_{1},\mathbf{u}_{2},\dots,\mathbf{u}_{n}\right\}$ and for each $i\in[n]$ they rotate the vector $\mathbf{v}_{i}$ by an angle $\phi$ towards the vector $\mathbf{u}_{i}$ in the plane spanned by $\mathbf{v}_{i}$ and $\mathbf{u}_{i}$ to obtain vectors $\left\{\mathbf{w}_{i}\right\}_{i\in[n]}$ where $\left\langle\mathbf{w}_{i},\mathbf{w}_{j}\right\rangle=\cos^{2}(\phi)\left% \langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle$ .
$\blacksquare$

Finally, they run the rounding algorithm of [39] on the $\left\{\mathbf{w}_{i}\right\}_{i\in[n]}$ vectors.

The work [76] then show the following guarantees about their algorithm.

Theorem 12 (Theorem 3.3 in [76]).

For a graph $G=(V,E)$ where ${\sf sdpval}\leq\left(t_{c}-\varepsilon_{l}\right)\left\lvert E\right\rvert$ for $\varepsilon_{l}>0$ ,

\displaystyle\operatorname*{\mathbb{E}}\Bigl[\mathsf{Alg}_{\mathsf{rot}}(G,t_{% c})\Bigr]\geq\left(\left(\frac{1}{t_{c}-\varepsilon_{l}}-\frac{1}{t^{*}}\right% )h_{r^{*}}(0)+g_{r^{*}}(t^{*})\right)\mathsf{opt}_{\mathsf{MC}}

where $r^{*}$ and $t^{*}$ are the unique solutions to Equation 1 and Equation 2, obtained by setting ${\sf sdpopt}=\left(t_{c}-\varepsilon_{l}\right)\left\lvert E\right\rvert$ .

Refer to caption — Figure 1: Improvement by Outward Rotation $\left(\text{Figure 2, Figure 4 in }\cite[cite]{[\@@bibref{}{Zwi99}{}{}]}\right)$ .

$\blacktriangleright$ Remark 13 (Lemma 3.2 in [76]).

For a choice of $\tau=t_{c}$ and $\varepsilon_{l}>0$ , we have that

\displaystyle\left(\frac{1}{t_{c}-\varepsilon_{l}}-\frac{1}{t^{*}}\right)h_{r^% {*}}(0)+g_{r^{*}}(t^{*})>\alpha_{\mathsf{GW}}.

2.3 Our SDP Based Algorithm

From Theorem 10 and Theorem 12, we observe that if ${\sf sdpopt}$ value is bounded sufficiently away from $t_{c}$ , it is possible to round the Maxcut SDP and obtain a strictly better than $\alpha_{\mathsf{GW}}$ -approximation algorithm. However, we note from Theorem 12 (see also $\alpha_{\mathsf{rot}}$ in Figure 1) that when ${\sf sdpopt}=t_{c}\left\lvert E\right\rvert$ , the algorithm of [76] reduces to algorithm of [39], and as before it offers no improvement beyond $\alpha_{\mathsf{GW}}$ -approximation. This highlights the need for new ideas to handle the case when ${\sf sdpopt}\approx t_{c}$ . Towards this we make a definition first,

Definition 14 (Edge-Disjoint Triangle Density).

For a graph $G=(V,E)$ , we define its edge-disjoint triangle density denoted $\mu(G)$ as,

\displaystyle\mu(G)=\frac{3\Delta(G)}{\left\lvert E\right\rvert}.

$\blacktriangleright$ Remark 15.

Clearly, $0\leq\mu(G)\leq 1$ . The quantity $\mu(G)$ is similar to the global clustering coefficient of the graph considered in [73, 40]. However, in $\mu(G)$ we consider edge-disjoint triangles as opposed to total number of triangles.

We now present our algorithm, which we later show achieves an improved approximation ratio regardless of the value of ${\sf sdpopt}$ .

Algorithm.

Our SDP algorithm (denoted $\mathsf{Alg}(G)$ ) is the following,

$\blacksquare$

Fix $\varepsilon$ to be,

$\displaystyle\varepsilon\stackrel{{\scriptstyle\textup{def}}}{{=}}\frac{(t_{c}% -3/4)\mu(G)}{9}$ $\displaystyle\left(\text{note that clearly $\varepsilon\leq(t_{c}-3/4)/9<t_{c}% $}\right)$ (3)
$\blacksquare$

Run $\mathsf{Alg}_{\mathsf{rot}}\left(G,t_{c}-\varepsilon\right)$

Our algorithm essentially runs the Zwick’s Outward Rotation Algorithm $\mathsf{Alg}_{\mathsf{rot}}$ as a subroutine, with the key difference being that we use a smaller threshold value of $\tau=t_{c}-\varepsilon$ , as compared to $\tau=t_{c}$ in [76]. Thus, for regimes of ${\sf sdpopt}\leq\left(t_{c}-\varepsilon\right)\left\lvert E\right\rvert$ , our algorithm reduces to $\mathsf{Alg}_{\mathsf{rot}}$ , and retains the improvement over $\alpha_{\mathsf{GW}}$ from Theorem 12. Similarly for ${\sf sdpopt}\geq\left(t_{c}+\varepsilon\right)\left\lvert E\right\rvert$ , our algorithm reduces to the standard [39] analysis and we have an improvement due to Theorem 10. We formalize this discussion below.

Definition 16 (Minimum Improvement).

We define the minimum improvement (over $\alpha_{\mathsf{GW}}$ ) as the minimum of the improvement obtained from Theorem 10 by setting $\varepsilon_{l}=\varepsilon$ and from Theorem 12 by setting $\varepsilon_{u}=\varepsilon$ (for choice of $\varepsilon$ in Equation 3) as,

\displaystyle\delta=\min\left\{g_{1}\left(t_{c}+\varepsilon\right)-\alpha_{% \mathsf{GW}},\left(\left(\frac{1}{t_{c}-\varepsilon}-\frac{1}{t^{*}}\right)h_{% r^{*}}(0)+g_{r^{*}}(t^{*})\right)-\alpha_{\mathsf{GW}}\right\}.

Note that $\delta>0$ (from Remark 11 and Remark 13) and it follows from the discussion above,

Corollary 17.

For a graph $G=(V,E)$ with ${\sf sdpopt}\notin[t_{c}-\varepsilon,t_{c}+\varepsilon]\left\lvert E\right\rvert$ , our algorithm gives,

\displaystyle\operatorname*{\mathbb{E}}[\mathsf{Alg}(G)]\geq\left(\alpha_{% \mathsf{GW}}+\delta\right){\sf sdpopt}\geq\left(\alpha_{\mathsf{GW}}+\delta% \right)\mathsf{opt}_{\mathsf{MC}}.

2.4 Our SDP Analysis

Building on the discussion above, it suffices to show that our algorithm obtains $\left(\alpha_{\mathsf{GW}}+\Omega(1)\right)$ -approximation guarantees when ${\sf sdpopt}\approx t_{c}\left\lvert E\right\rvert$ . Our analysis centers on the contribution of individual edges to the SDP solution, denoted by $t_{e}$ . We define $t_{\mathsf{avg}}={\sf sdpopt}/\left\lvert E\right\rvert$ , and we will focus on the values of $t_{\mathsf{avg}}$ in the band $[t_{c}-\varepsilon,t_{c}+\varepsilon]$ . We note that in these regimes our algorithm sets $\phi=0^{\circ}$ and reduces to the algorithm of [39].

Refined SDP Analysis

Previously, we mentioned that if $t_{\mathsf{avg}}=t_{c}-\varepsilon$ , it’s possible that a $\left(1-\varepsilon\right)$ -fraction of edges have $t_{e}=t_{c}$ while the remaining edges have $t_{e}=0$ yielding no improvement over $\alpha_{\mathsf{GW}}$ . Here, we consider a more refined analysis of this argument by defining a set of good edges as $F=\left\{e\in E:t_{e}\geq t_{c}+\varepsilon\right\}$ . We leverage the edge by edge analysis of [39] to show that,

$\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}% \Bigl[\left\lvert E(S_{g},V\setminus S_{g})\right\rvert\Bigr]$	$\displaystyle=\sum_{e\in F}g_{1}(t_{e})t_{e}+\sum_{e\in E\setminus F}g_{1}(t_{% e})t_{e}$	$\displaystyle\left(\text{See \lx@cref{creftype~refnum}{thm:maxcut_gw}}\right)$
	$\displaystyle\geq\sum_{e\in F}g_{1}(t_{c}+\varepsilon)t_{e}+\alpha_{\mathsf{GW% }}\sum_{e\in E\setminus F}t_{e}$	$\displaystyle\left(\text{Definition of $F$ and $g$}\right)$
	$\displaystyle\geq\left(\alpha_{\mathsf{GW}}+\delta\right)\sum_{e\in F}t_{e}+% \alpha_{\mathsf{GW}}\sum_{e\in E\setminus F}t_{e}$	$\displaystyle\left(\text{By \lx@cref{creftype~refnum}{thm:gw_bound}}\right)$
	$\displaystyle=\alpha_{\mathsf{GW}}\sum_{e\in E}t_{e}+\delta\sum_{e\in F}t_{e}$
	$\displaystyle\geq\alpha_{\mathsf{GW}}\,t_{\mathsf{avg}}\left\lvert E\right% \rvert+\delta\left\lvert F\right\rvert\left(t_{c}+\varepsilon\right)$	$\displaystyle\left(\text{By definition of }F\right)$
	$\displaystyle\geq\alpha_{\mathsf{GW}}\,\mathsf{opt}_{\mathsf{MC}}+\delta\left% \lvert F\right\rvert(t_{c}+\varepsilon)$	$\displaystyle\left(\text{By definition of }t_{\mathsf{avg}}\right).$

Improved Approximation Guarantees

The main takeaway from the above analysis is that for $t_{\mathsf{avg}}\in[t_{c}-\varepsilon,t_{c}+\varepsilon]$ , the condition $\left\lvert F\right\rvert=\Omega(1)\left\lvert E\right\rvert$ ensures an $\left(\alpha_{\mathsf{GW}}+\Omega(1)\right)$ -approximation. We will next identify a sufficient criterion for graphs where this condition holds.

Triangles and Good Edges

We consider another set of good edges $D=\left\{e\in E:t_{e}\ll t_{c}\right\}$ (say smaller than $t_{c}-100\varepsilon$ ). Now, given a triangle $T=\left\{i,j,k\right\}$ in the graph, we examine the geometry of SDP vectors for $T$ and note (see Figure 2) that there always exists an edge $\left\{i,j\right\}$ having

\displaystyle\theta_{ij}\leq\left(\frac{\theta_{ij}+\theta_{jk}+\theta_{ik}}{3% }\right)\leq\left(\frac{\theta^{\prime}_{ij}+\theta^{\prime}_{jk}+\theta^{% \prime}_{ik}}{3}\right)\leq\frac{2\pi}{3}\left(\text{also see proof of % \lx@cref{creftype~refnum}{claim:small_angle_claim}}\right).

For such an edge $e=\left\{i,j\right\}$ having $\theta_{ij}\leq 2\pi/3$ we have its contribution to the SDP value as,

\displaystyle t_{e}=\frac{1}{2}\left(1-\left\langle\mathbf{v}_{i},\mathbf{v}_{% j}\right\rangle\right)=\frac{1}{2}\left(1-\cos(\theta_{ij})\right)\leq\frac{1}% {2}\left(1-\cos(2\pi/3)\right)=0.75.

Now $t_{c}-100\varepsilon>0.75$ (for $\varepsilon\leq 1/1000$ ) and hence the edge $e\in D$ . Thus if the graph has “large” number of edge-disjoint triangles, such that $\Delta(G)=\Omega(1)\left\lvert E\right\rvert$ (equivalently $\mu(G)=\Omega(1)$ ), then each triangle will contribute a unique edge to the set $D$ and we can infer that $\left\lvert D\right\rvert=\Omega(1)\left\lvert E\right\rvert$ .

Averaging argument saves the day

Recall we earlier show that an improvement over $\alpha_{\mathsf{GW}}$ is possible when a certain set of good edges $F$ are large $\left\lvert F\right\rvert=\Omega(1)\left\lvert E\right\rvert$ . Then we showed that if the graph has $\Omega(1)\left\lvert E\right\rvert$ many edge-disjoint triangles, a different set of good edges $D$ such that $\left\lvert D\right\rvert=\Omega(1)\left\lvert E\right\rvert$ . One may wonder where are we headed and the connection between these set of good edges?

Here we use the fact that we only care about $t_{\mathsf{avg}}$ in the band $[t_{c}-\varepsilon,t_{c}+\varepsilon]$ . This allows us to use a simple averaging argument (see Lemma 25 for details) to argue that $\left\lvert D\right\rvert=\Omega(1)\left\lvert E\right\rvert$ implies that $\left\lvert F\right\rvert=\Omega(1)\left\lvert E\right\rvert$ . Thus, we identify a structural criterion, namely a large number ( $\Omega(1)\left\lvert E\right\rvert$ many) of edge-disjoint triangles in a graph that is sufficient for obtaining a $\left(\alpha_{\mathsf{GW}}+\Omega(1)\right)$ -approximation.

Fast SDP Solvers

As we pointed out earlier, for CSPs such as the Maxcut problem, it is possible to use the result of [68] which builds upon framework of [3, 65] to obtain a feasible SDP solution with ${\sf sdpval}\geq{\sf sdpopt}-\upsilon\left\lvert E\right\rvert$ for some $\upsilon>0$ in time $O(\left\lvert E\right\rvert\log^{2}\left\lvert V\right\rvert{\sf poly}(1/% \upsilon))$ . We show later that it is possible to choose $\upsilon$ appropriately and prove Theorem 1.

2.5 Applications of Improved SDP Analysis

In this section, we apply our main result (Theorem 1) which shows that the Maxcut SDP achieves a strictly better-than- $\alpha_{\mathsf{GW}}$ approximation ratio whenever the graph $G$ contains a constant fraction of edge-disjoint triangles, i.e., $\mu(G)=\Delta(G)/|E|=\Omega(1)$ . We show this property for two broad classes of graphs: (1) unit ball graphs (for simplicity we use unit disk graphs in the overview), and (2) real-world networks with strong community structure.

Unit Disk Graphs

A unit disk graph is defined by mapping vertices to points in $\mathbb{R}^{2}$ , where an edge is present between two vertices if their corresponding unit-radius disks intersect. Our goal is to show unit disks graph with sufficiently large average degree contains $\Omega(|E|)$ edge-disjoint triangles.

We begin by fixing a vertex $v$ and analyzing its neighborhood $N(v)$ in the geometric embedding. The vectors from $v$ to its neighbors are projected onto the unit circle, and this space is partitioned into six small angular sectors (using spherical caps on $\mathbb{S}^{1}$ ). By the pigeonhole principle, one such sector contains $\Omega(\deg(v)/6)$ neighbors, all within an angular range of $\pi/6$ . This is small enough to ensure that any pair of vertices here have an edge due to the geometry.

Thus, the set of neighbors, along with $v$ , induces a dense subgraph which contains a clique of size $\Omega\left(\deg(v)\right)$ . Using an algorithm that greedily packs triangles in cliques, we extract $\Omega(\deg(v)^{2})$ edge-disjoint triangles from this neighborhood. Repeating this process over all high-degree vertices, we construct a global set of $\Omega(|E|)$ edge-disjoint triangles. Therefore, any unit disk graph with average degree at least $18$ satisfies $\mu(G)=\Omega(1)$ , and Theorem 1 implies a $(\alpha_{\mathsf{GW}}+\Omega(1))$ -approximation in $\widetilde{\mathcal{O}}(|E|)$ time.

Real-World Network Graphs

Real-world networks often display features like high clustering, community structure, and triangle density, which are not captured by classical Erdős–Rényi models. To formalize this, we use the “spectral triadic decomposition” framework of [12], which introduces a measure of triangle density called spectral transitivity:

\tau(G)=\left({\sum_{i=1}^{n}\lambda_{i}^{3}}\right)/\left({\sum_{i=1}^{n}% \lambda_{i}^{2}}\right),

where $\lambda_{i}$ are the eigenvalues of the normalized adjacency matrix.

For $d$ -regular graphs, they show that $\tau(G)=\frac{3T(G)}{|E|d}$ , where $T(G)$ is the total number of triangles in the graph. Using a simple greedy packing argument and upper bounding the triangle load on any edge, we show that such graphs must contain at least $\Omega(\tau(G)|E|)$ edge-disjoint triangles.

Thus, for such graphs where $\tau(G)=\Omega(1)$ , we again conclude $\mu(G)=\Omega(1)$ , and hence the Maxcut SDP achieves a $(\alpha_{\mathsf{GW}}+\Omega(1))$ -approximation guarantee.

3 Maxcut SDP Analysis

The main result in this section is presenting a sufficient condition under which the Maxcut SDP achieves better than $\alpha_{\mathsf{GW}}$ approximation. We begin by recalling that in Equation 3 we fix our value for $\varepsilon=\left((t_{c}-3/4)\mu(G)\right)/9$ , where $\mu(G)$ denotes the edge-disjoint triangle density of a graph. For this choice of $\varepsilon$ , we also refer to the definition of $\delta$ from Definition 16.

Theorem 18.

Given a graph $G=(V,E)$ , there exists an algorithm $\mathsf{Alg}\text{\small+}(G)$ such that,

\displaystyle\operatorname*{\mathbb{E}}[\mathsf{Alg}\text{\small+}(G)]\geq% \left(\alpha_{\mathsf{GW}}+{\frac{\delta}{2}\left(t_{c}+\frac{(t_{c}-3/4)\mu(G% )}{9}\right)\left(\frac{\frac{(t_{c}-3/4)\mu(G)}{9}}{1-t_{c}-\frac{(t_{c}-3/4)% \mu(G)}{9}}\right)}\right)\mathsf{opt}_{\mathsf{MC}}.

where the running time of $\mathsf{Alg}\text{\small+}(G)$ is $O\left(\left\lvert E\right\rvert\log^{2}\left\lvert V\right\rvert{\sf poly}% \left(1/\left(\delta\mu^{2}(G)\right)\right)\right)$ .

3.1 Improved Approximation Ratio Analysis

Towards proving Theorem 18, we start with a few useful definitions,

Definition 19 (Good and Bad Edges).

For a given feasible solution to the Maxcut SDP and $\varepsilon^{\prime},\zeta^{\prime}>0$ , we say that an edge $e=\left\{i,j\right\}$ is an $(\varepsilon^{\prime},\zeta^{\prime})$ -bad edge if $t_{e}\in[t_{c}-\zeta^{\prime}\varepsilon^{\prime},t_{c}+\varepsilon^{\prime}]$ . We say an edge $e$ is an $(\varepsilon^{\prime},\zeta^{\prime})$ -good edge if it is not $(\varepsilon^{\prime},\zeta^{\prime})$ -bad. We let $E_{g}(\varepsilon^{\prime},\zeta^{\prime})$ denote the set of $(\varepsilon^{\prime},\zeta^{\prime})$ -good edges and $E_{b}(\varepsilon^{\prime},\zeta^{\prime})$ denote the set of $(\varepsilon^{\prime},\zeta^{\prime})$ -bad edges. Further we let, $E_{g}^{(l)}(\varepsilon^{\prime},\zeta^{\prime})=\left\{e\in E:t_{e}\leq t_{c}% -\zeta^{\prime}\varepsilon^{\prime}\right\}$ and $E_{g}^{(u)}(\varepsilon^{\prime},\zeta^{\prime})=E_{g}(\varepsilon^{\prime},% \zeta^{\prime})\setminus E_{g}^{(l)}(\varepsilon^{\prime},\zeta^{\prime})$ .

Definition 20 (Density Constants).

We let $\zeta=\left((t_{c}-3/4)/\varepsilon\right)-1/2$ (any arbitrary small constant $c>0$ instead of $1/2$ would also suffice). For choice of $\varepsilon^{\prime}=\varepsilon,\zeta^{\prime}=\zeta$ we let $\kappa=\left\lvert E_{g}^{(l)}\left(\varepsilon,\zeta\right)\right\rvert/\left% \lvert E\right\rvert$ , and we let $\gamma=\left\lvert E_{g}^{(u)}\left(\varepsilon,\zeta\right)\right\rvert/\left% \lvert E\right\rvert$ . We note that $0\leq\kappa,\gamma\leq 1$ .

Recall that for ${\sf sdpopt}\geq\left(t_{c}-\varepsilon\right)\left\lvert E\right\rvert$ , our algorithm $\mathsf{Alg}(G)$ sets $\phi=0^{\circ}$ and consequently reduces to the [39] algorithm. As noted earlier, if ${\sf sdpopt}=t_{c}\left\lvert E\right\rvert$ , the analysis of [39] gives exactly $\alpha_{\mathsf{GW}}$ -approximation ratio (no improvement). We now present a more refined analysis of [39] that leverages the notion of good edges we defined above to show that,

Lemma 21.

For a graph $G=(V,E)$ and a feasible SDP solution to the Maxcut SDP such that ${\sf sdpval}(G)\geq(t_{c}-\varepsilon)\left\lvert E\right\rvert$ for some $\varepsilon>0$ , there exists an algorithm $\mathsf{Alg}\text{\small+}(G)$ such that,

\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}[% \mathsf{Alg}\text{\small+}(G)]\geq\alpha_{\mathsf{GW}}\,{\sf sdpval}(G)+\delta% \sum_{e\in E_{g}^{(u)}(\varepsilon,\zeta)}\left(\frac{1}{2}\left(1-\left% \langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right).

Proof.

The proof follows along lines of proof of Theorem 9. For ${\sf sdpval}(G)\geq(t_{c}-\varepsilon)\left\lvert E\right\rvert$ for some $\varepsilon>0$ the algorithm sets $\phi=0^{\circ}$ and hence one obtains that,

	$\displaystyle\operatorname{\mathbb{E}}_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}[% \mathsf{Alg}\text{\small+}(G)]=\operatorname{\mathbb{E}}_{\mathbf{g}\sim% \mathcal{N}(0,1)^{n}}[\left\lvert E(S_{g},V\setminus S_{g})\right\rvert]=% \operatorname*{\mathbb{E}}_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}\left[{\sum_{e% \in E}\mathbf{1}_{e\in E(S_{g},V\setminus S_{g})}}\right]$
	$\displaystyle=\sum_{e\in E}\operatorname{\mathbb{E}}_{\mathbf{g}\sim\mathcal{% N}(0,1)^{n}}[{{\mathbf{1}_{e\in E(S_{g},V\setminus S_{g})}}}]=\sum_{e\in E}% \operatorname{\mathbb{P}}_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}\left[e\in E(S_% {g},V\setminus S_{g})\right]$
	$\displaystyle=\sum_{e\in E_{g}^{(u)}(\varepsilon,\zeta)}\operatorname{\mathbb% {P}}_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}\left[e\in E(S_{g},V\setminus S_{g})% \right]+\sum_{e\in E\setminus E_{g}^{(u)}(\varepsilon,\zeta)}\operatorname{% \mathbb{P}}_{\mathbf{g}\sim\mathcal{N}(0,1)^{n}}\left[e\in E(S_{g},V\setminus S% _{g})\right]$
	$\displaystyle\geq\left(\alpha_{\mathsf{GW}}+\delta\right)\sum_{e\in E_{g}^{(u)% }(\varepsilon,\zeta)}\left(\frac{1}{2}\left(1-\left\langle\mathbf{v}_{i},% \mathbf{v}_{j}\right\rangle\right)\right)+\left(\alpha_{\mathsf{GW}}\right)% \sum_{e\in E\setminus E_{g}^{(u)}(\varepsilon,\zeta)}\left(\frac{1}{2}\left(1-% \left\langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right)$
	$\displaystyle=\alpha_{\mathsf{GW}}\sum_{e\in E}\left(\frac{1}{2}\left(1-\left% \langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right)+\delta\sum_{e% \in E_{g}^{(u)}(\varepsilon,\zeta)}\left(\frac{1}{2}\left(1-\left\langle% \mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right)$
	$\displaystyle=\alpha_{\mathsf{GW}}\,{\sf sdpval}(G)+\delta\sum_{e\in E_{g}^{(u% )}(\varepsilon,\zeta)}\left(\frac{1}{2}\left(1-\left\langle\mathbf{v}_{i},% \mathbf{v}_{j}\right\rangle\right)\right).$

where the inequality follows from Definition 16 and proof of Theorem 10. $\hfill\blacktriangleleft$

Above, we show that we obtain an improvement over $\alpha_{\mathsf{GW}}$ when the “SDP mass” on the good edges, $E_{g}^{(u)}(\varepsilon,\zeta)$ is large. Next, we argue that rather than requiring a large “SDP mass”, it suffices to show that the fraction of good edges, $\left\lvert E_{g}^{(u)}(\varepsilon,\zeta)\right\rvert/\left\lvert E\right\rvert$ is large.

Lemma 22.

Given a graph $G=(V,E)$ , and a feasible solution to the Maxcut SDP one obtains that,

\displaystyle\sum_{e\in E_{g}^{(u)}(\varepsilon,\zeta)}\left(\frac{1}{2}\left(% 1-\left\langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right)\geq% \gamma\left(t_{c}+\varepsilon\right){\sf sdpval}(G)\text{ where $\gamma=\left% \lvert E_{g}^{(u)}\left(\varepsilon,\zeta\right)\right\rvert/\left\lvert E% \right\rvert$}.

Proof.

Considering the contribution in the SDP objective from $E_{g}^{(u)}(\varepsilon,\zeta)$ it follows that,

$\displaystyle\sum_{e\in E_{g}^{(u)}(\varepsilon,\zeta)}\left(\frac{1}{2}\left(% 1-\left\langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)\right)$	$\displaystyle=\sum_{\left\{i,j\right\}\in E_{g}^{(u)}(\varepsilon,\zeta)}t_{ij}$
	$\displaystyle\geq\left\lvert E_{g}^{(u)}(\varepsilon,\zeta)\right\rvert\min_{% \left\{i,j\right\}\in E_{g}^{(u)}(\varepsilon,\zeta)}\left\{t_{ij}\right\}$
	$\displaystyle\geq\left\lvert E_{g}^{(u)}(\varepsilon,\zeta)\right\rvert\left(t% _{c}+\varepsilon\right)$	$\displaystyle\hskip-8.0pt\left(\text{Definition of }E_{g}^{(u)}(\varepsilon,% \zeta)\right)$
	$\displaystyle\geq\left(t_{c}+\varepsilon\right)\gamma\left\lvert E\right\rvert$	$\displaystyle\hskip-8.0pt\left(\text{By \lx@cref{creftype~refnum}{def:our_cons% tants}}\right)$
	$\displaystyle\geq\left(t_{c}+\varepsilon\right)\gamma\,{\sf sdpval}(G)$	$\displaystyle\hskip-8.0pt\left({\sf sdpval}(G)\leq\left\lvert E\right\rvert% \right).$

$\hfill\blacktriangleleft$

Now we present a crucial result, where we show that the other type of good edges $E_{g}^{(l)}(\varepsilon,\zeta)$ can be lower bounded by $\mu(G)/3$ , the edge-disjoint triangle density of our graph $G$ . We examine the SDP vectors corresponding to the vertices of triangles, and use their geometry to infer a useful bound on the SDP contribution of the edges within each triangle.

Lemma 23.

Given a graph $G=(V,E)$ , and a feasible solution to the Maxcut SDP one obtains that $\kappa\geq\mu(G)/3$ where $\kappa=\left\lvert E_{g}^{(l)}\left(\varepsilon,\zeta\right)\right\rvert/\left% \lvert E\right\rvert$ .

Proof.

Let $T=\left\{i,j,k\right\}$ be a triangle in the graph $G$ and let $\mathbf{v}_{i},\mathbf{v}_{j},\mathbf{v}_{k}$ be the corresponding vectors for a solution to the Maxcut SDP. Now, consider the plane spanned by $\mathbf{v}_{i},\mathbf{v}_{j}$ and $\mathbf{v}_{k}$ and let $\theta_{ij},\theta_{jk},\theta_{ik}$ be the corresponding angles between the respective vectors. Then we have that,

Claim 24.

$\min\left\{\theta_{ij},\theta_{ik},\theta_{jk}\right\}\leq 2\pi/3$ .

Proof.

The analysis proceeds by examining $\left\lVert\mathbf{v}_{i}+{\mathbf{v}_{j}+{\mathbf{v}_{k}}}\right\rVert^{2}$ and noting that,

	$\displaystyle 0$	$\displaystyle\leq\left\lVert\mathbf{v}_{i}+{\mathbf{v}_{j}+{\mathbf{v}_{k}}}% \right\rVert^{2}$
		$\displaystyle=\left\lVert\mathbf{v}_{i}\right\rVert^{2}+\left\lVert\mathbf{v}_% {j}\right\rVert^{2}+\left\lVert\mathbf{v}_{k}\right\rVert^{2}+2\left(\left% \langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle+\left\langle\mathbf{v}_{j},% \mathbf{v}_{k}\right\rangle+\left\langle\mathbf{v}_{i},\mathbf{v}_{k}\right% \rangle\right)$
		$\displaystyle=3+2\left(\cos(\theta_{ij})+\cos(\theta_{jk})+\cos(\theta_{ik})% \right)\quad\qquad\qquad\left(\text{By constraints of {\hyperref@@ii[sdp:% maxcut_sdp]{{Maxcut }SDP}}}\right).$

From the above it follows that ${\cos(\theta_{ij})+\cos(\theta_{jk})+\cos(\theta_{ik})}\geq-3/2$ . Since the maximum of three real numbers at least their average, one obtains that,

\displaystyle\max\left\{\cos(\theta_{ij}),\cos(\theta_{ik}),\cos(\theta_{jk})% \right\}\geq-1/2\text{ and hence }\min\left\{\theta_{ij},\theta_{ik},\theta_{% jk}\right\}\leq 2\pi/3

$\hfill\vartriangleleft$ Now, at least one of the edges in the triangles (without loss of generality, say the edge $\left\{i,j\right\}$ ) is such that $\theta_{ij}\leq 2\pi/3=120^{\circ}$ and hence for this edge it follows that,

\displaystyle t_{ij}\stackrel{{\scriptstyle\textup{def}}}{{=}}\frac{1}{2}\left% (1-\left\langle\mathbf{v}_{i},\mathbf{v}_{j}\right\rangle\right)=\frac{1}{2}% \left(1-\cos\theta_{ij}\right)\leq\frac{1}{2}\left(1-\cos(2\pi/3)\right)=\frac% {3}{4}.

Now for the given choice of $\zeta=(t_{c}-3/4)/\varepsilon-1/2$ it is easy to see that for choice of $\varepsilon$ in Equation 3,

\displaystyle\zeta=\frac{t_{c}-3/4}{\varepsilon}-\frac{1}{2}=\frac{9}{\mu(G)}-% \frac{1}{2}\geq 9-\frac{1}{2}>0

where above uses $\mu(G)\leq 1$ and further one obtains that,

\displaystyle t_{c}-\varepsilon\zeta=t_{c}-\varepsilon\left(\frac{t_{c}-3/4}{% \varepsilon}-\frac{1}{2}\right)=t_{c}-\left(t_{c}-3/4\right)+\frac{\varepsilon% }{2}>\frac{3}{4}

Therefore one concludes that $\left\{i,j\right\}\in E_{g}^{(l)}\left(\varepsilon,\zeta\right)$ and hence,

\displaystyle\kappa=\frac{\left\lvert E_{g}^{(l)}\left(\varepsilon,\zeta\right% )\right\rvert}{\left\lvert E\right\rvert}\geq\frac{\Delta(G)}{\left\lvert E% \right\rvert}=\frac{\mu(G)}{3}.

$\hfill\blacktriangleleft$

We now revisit the object of our interest, the type of good edges $E_{g}^{(u)}(\varepsilon,\zeta)$ . Next, we show through an averaging argument that for ${\sf sdpopt}\geq\left(t_{c}-\varepsilon\right)\left\lvert E\right\rvert$ , a large number of good edges of other type $E_{g}^{(l)}(\varepsilon,\zeta)$ imply a large number of edges of type $E_{g}^{(u)}(\varepsilon,\zeta)$ .

Lemma 25.

Given a graph $G=(V,E)$ , a feasible solution to the Maxcut SDP such that ${\sf sdpval}(G)\geq\left(t_{c}-\varepsilon\right)\left\lvert E\right\rvert$ one obtains that,

\displaystyle\gamma\geq{\frac{\varepsilon}{\left(1-t_{c}-\varepsilon\right)}},% \text{ where recall that }\gamma=\left\lvert E_{g}^{(u)}\left(\varepsilon,% \zeta\right)\right\rvert/\left\lvert E\right\rvert.

Proof.

Let $T$ be a uniform random variable that takes values $\left(t_{e}\right)_{e\in E}$ , then it is given that,

	$\displaystyle\operatorname*{\mathbb{E}}[T]$	$\displaystyle=\frac{1}{\left\lvert E\right\rvert}\sum_{e\in E}t_{e}\geq\frac{1% }{\left\lvert E\right\rvert}(t_{c}-\varepsilon)\left\lvert E\right\rvert\geq t% _{c}-\varepsilon\text{ and }$
	$\displaystyle\operatorname*{\mathbb{P}}\left[T\leq t_{c}-\zeta\varepsilon\right]$	$\displaystyle=\frac{\left\lvert E_{g}^{(l)}(\varepsilon,\zeta)\right\rvert}{% \left\lvert E\right\rvert}=\frac{\kappa\left\lvert E\right\rvert}{\left\lvert E% \right\rvert}=\kappa$

Note that $T\in[0,1]$ and it follows that $\operatorname*{\mathbb{P}}\left[T\geq(t_{c}+\varepsilon)\right]=\gamma$ and hence one obtains that,

	$\displaystyle\operatorname*{\mathbb{E}}[T]$	$\displaystyle=\frac{1}{\left\lvert E\right\rvert}\left(\sum_{\begin{subarray}{% c}e\in E\\[1.50694pt] t_{e}\leq t_{c}-\zeta\varepsilon\end{subarray}}{t_{e}}+\sum_{\begin{subarray}{% c}e\in E\\[1.50694pt] t_{c}-\zeta\varepsilon\leq t_{e}\leq t_{c}+\varepsilon\end{subarray}}{t_{e}}+% \sum_{\begin{subarray}{c}e\in E\\[1.50694pt] t_{e}\geq t_{c}+\varepsilon\end{subarray}}t_{e}\right)$
		$\displaystyle\leq\left(t_{c}-\zeta\varepsilon\right)\operatorname{\mathbb{P}}% \left[T\leq t_{c}-\zeta\varepsilon\right]+(t_{c}+\varepsilon)\operatorname{% \mathbb{P}}\left[t_{c}-\zeta\varepsilon\leq T\leq t_{c}+\varepsilon\right]+1.% \operatorname*{\mathbb{P}}\left[T\geq t_{c}+\varepsilon\right]$
		$\displaystyle\leq\left(t_{c}-\zeta\varepsilon\right)\kappa+\left(t_{c}+% \varepsilon\right)\left(1-\kappa-\gamma\right)+\gamma$

Now using $\operatorname*{\mathbb{E}}[T]\geq t_{c}-\varepsilon$ and by expanding the above expression if follows that,

\displaystyle t_{c}-\varepsilon\leq t_{c}\kappa-\zeta\varepsilon\kappa+t_{c}+% \varepsilon-t_{c}\kappa-t_{c}\gamma-\varepsilon\kappa-\varepsilon\gamma+\gamma

and rearranging terms in the above expression one obtains that,

\displaystyle\left(1-t_{c}-\varepsilon\right)\gamma\geq\zeta\varepsilon\kappa+% \varepsilon\kappa-2\varepsilon=\left(\left(\zeta+1\right)\kappa-2\right)\varepsilon

and we one can then solve for $\gamma$ by noting that for choice of $\zeta$ from Definition 20,

\displaystyle\zeta+1=\left(\frac{t_{c}-3/4}{\varepsilon}-\frac{1}{2}\right)+1% \geq\frac{t_{c}-3/4}{\varepsilon}\geq\left(t_{c}-3/4\right)\frac{9}{(t_{c}-3/4% )\mu(G)}=\frac{9}{\mu(G)}

where the second inequality follows by choice of $\varepsilon$ in Equation 3. Now solving for $\gamma$ ,

\displaystyle\gamma\geq\frac{\left(\left(\zeta+1\right)\kappa-2\right)% \varepsilon}{1-t_{c}-\varepsilon}

\displaystyle\geq\frac{\left((9/\mu(G))\kappa-2\right)\varepsilon}{1-t_{c}-% \varepsilon}\geq\frac{(3-2)\varepsilon}{1-t_{c}-\varepsilon}\geq\frac{% \varepsilon}{1-t_{c}-\varepsilon}

where the last inequality follows from Lemma 23 since $\kappa\geq\mu(G)/3$ . $\hfill\blacktriangleleft$

3.2 Running Time Analysis

We recall our discussion of fast SDP solvers for Maxcut SDP. The work of [68] (building on the works of [3, 65]) showed that for CSPs such as Maxcut , we can obtain an approximate solution to their canonical SDP relaxation in near-linear time. We state the main result in [68] in the context of solving the Maxcut SDP.

Theorem 26 (Theorem 1.1 in [68]).

Given a graph $G=(V,E)$ and a constant $\upsilon>0$ , there exists an algorithm that computes in time $O(\left\lvert E\right\rvert\log^{2}\left\lvert V\right\rvert{\sf poly}(1/% \upsilon))$ , a subgraph $G^{\prime}=(V,E^{\prime})$ and a feasible solution to Maxcut SDP with value ${\sf sdpval}(G^{\prime})$ such that,

$\blacksquare$

${\sf sdpval}(G^{\prime})\geq{\sf sdpopt}(G)-\upsilon\left\lvert E\right\rvert$
$\blacksquare$

$\left\lvert E\setminus E^{\prime}\right\rvert\leq\upsilon\left\lvert E\right\rvert$ .

The fast SDP solver of [68] finds an approximately optimal solution using the Matrix Multiplicative Weights Update framework developed in [3] that does not construct a full $n\times n$ Gram matrix but a low-rank approximation where instead it produces the solution vectors $\left\{\mathbf{v}_{1},\mathbf{v}_{2},\dots,\mathbf{v}_{n}\right\}\in\mathbb{R}% ^{k}$ for $k=\mathcal{O}\left({\sf poly}\left(\log n\right)\right)$ . Next the angle computation for the outward rotation angle $\phi$ can be done in $\mathcal{O}\left(n\right)$ time. The vectors after rotation like in space $\mathbb{R}^{n+k}$ , but we do not need to explicitly compute these vectors. Instead we proceed to show that the [39] rounding can be more directly applied. We recall first that in [76] the rotated vectors $\mathbf{w}_{i}$ can be written as,

\displaystyle\mathbf{w}_{i}=\left(\cos\phi\right)\mathbf{v}_{i}+\left(\sin\phi% \right)\mathbf{u}_{i}

where $\mathbf{u}_{i}$ is simply the $i^{th}$ standard basis vector of $\mathbb{R}^{n}$ . Finally we see that the last step is a plain [39] rounding which requires computing an inner product with a random Gaussian vector $\mathbf{g}\sim\mathcal{N}\left(0,1\right)^{n+k}$ . Now we can decompose $\mathbf{g}$ as $\mathbf{g}=\mathbf{g}_{v}+\mathbf{g}_{u}$ where $\mathbf{g}_{v}\in\mathbb{R}^{k}$ and $\mathbf{g}_{u}\in\mathbb{R}^{n}$ and $\mathbf{g}_{v}\perp\mathbf{g}_{u}$ . Then we note that the inner product computation is simply,

$\displaystyle\left\langle\mathbf{w}_{i},\mathbf{g}\right\rangle$	$\displaystyle=\left\langle\left(\cos\phi\right)\mathbf{v}_{i}+\left(\sin\phi% \right)\mathbf{u}_{i},\mathbf{g}_{v}+\mathbf{g}_{u}\right\rangle$
	$\displaystyle=\left(\cos\phi\right)\left\langle\mathbf{v}_{i},\mathbf{g}_{v}% \right\rangle+\left(\sin\phi\right)\left\langle\mathbf{u}_{i},\mathbf{g}_{u}\right\rangle$
	$\displaystyle=\left(\cos\phi\right)\left\langle\mathbf{v}_{i},\mathbf{g}_{v}% \right\rangle+\left(\sin\phi\right)g_{u}\left(i\right)$	(4)

Since $\mathbf{v}_{i}$ and $\mathbf{g}_{v}$ are vectors in $\mathbb{R}^{k}$ , we can compute $\left\langle\mathbf{w}_{i},\mathbf{g}\right\rangle$ in $\mathcal{O}\left(k\right)$ time. Thus the overall running time is dominated by the time required by the fast SDP solver. We restate the algorithm for clarity.

Input. The algorithm takes a graph $G=(V,E)$ as input.
Algorithm. We present the final algorithm denoted $\mathsf{Alg}\text{\small+}(G)$ below,

$\blacksquare$

Solve the Maxcut SDP using fast SDP solver of [68] to obtain a subgraph $G^{\prime}=(V,E^{\prime})$ and a collection of vectors $\left\{\mathbf{v}_{1},\mathbf{v}_{2},\dots,\mathbf{v}_{n}\right\}$ that are feasible for it.
$\blacksquare$

An angle $\phi$ is obtained by solving the below system of equations in variables $r, t$ ,

$\displaystyle\frac{\arccos(r(1-2t))-\arccos(r)}{t}$ $\displaystyle=\frac{2r}{\sqrt{1-r^{2}(1-2t)^{2}}},$

$\displaystyle\frac{1-\frac{t\left\lvert E\right\rvert}{{\sf sdpval}(G^{\prime}% )}}{\sqrt{1-r^{2}}}$ $\displaystyle=\frac{1-2t}{\sqrt{1-r^{2}(1-2t)^{2}}}$

and letting $\phi=\arccos\left(\sqrt{r}\right)$ . If ${\sf sdpval}(G^{\prime})\geq\left(t_{c}-\varepsilon\right)\left\lvert E\right\rvert$ , set $\phi=0^{\circ}$ .
$\blacksquare$

Run the rounding algorithm of [39] on the $\left\{\mathbf{w}_{i}\right\}_{i\in[n]}$ vectors using computation as in Equation 4.

Now we have all the ingredients to prove our main result in this section where we show formal guarantees on the performance of $\mathsf{Alg}\text{\small+}(G)$ .

Proof of Theorem 18.

For the choice of $\varepsilon$ in Equation 3 observe when ${\sf sdpval}(G^{\prime})\geq\left(t_{c}-\varepsilon\right)\left\lvert E\right\rvert$ it follows that,

\displaystyle{\sf sdpopt}(G)\geq{\sf sdpval}(G^{\prime})\geq\left(t_{c}-% \varepsilon\right)\left\lvert E\right\rvert.

If ${\sf sdpval}(G^{\prime})\leq\left(t_{c}-\varepsilon\right)\left\lvert E\right\rvert$ , then from Theorem 26 with choice of $\upsilon=2\epsilon$ one obtains that,

\displaystyle{\sf sdpopt}(G)\leq{\sf sdpval}(G^{\prime})+\upsilon\left\lvert E% \right\rvert\leq\left(t_{c}-\varepsilon\right)\left\lvert E\right\rvert+% \upsilon\left\lvert E\right\rvert=\left(t_{c}+\varepsilon\right)\left\lvert E\right\rvert

Therefore, it follows that ${\sf sdpopt}(G)\notin[(t_{c}-\varepsilon)\left\lvert E\right\rvert,(t_{c}+% \varepsilon)\left\lvert E\right\rvert]$ and using Corollary 17 one obtains the following,

\displaystyle\operatorname*{\mathbb{E}}[\mathsf{Alg}\text{\small+}(G)]\geq% \left(\alpha_{\mathsf{GW}}+\delta\right){\sf sdpval}(G)\geq\left(\alpha_{% \mathsf{GW}}+\delta\right)\mathsf{opt}_{\mathsf{MC}}.

Next, consider the regimes where ${\sf sdpval}(G^{\prime})\in\left[\left(t_{c}-\varepsilon\right)\left\lvert E% \right\rvert,\left(t_{c}+\varepsilon\right)\left\lvert E\right\rvert\right]$ . For choice of $\zeta=\left((t_{c}-3/4)/\varepsilon\right)-1/2$ and using Lemma 25 one obtains that,

\displaystyle\gamma\geq\frac{\varepsilon}{\left(1-t_{c}-\varepsilon\right)}

Using this in Lemma 22 and the bound obtained there further in Lemma 21 one obtains that,

	$\displaystyle\operatorname*{\mathbb{E}}[\mathsf{Alg}\text{\small+}(G)]$	$\displaystyle\geq\alpha_{\mathsf{GW}}\,{\sf sdpval}(G^{\prime})+\delta\gamma% \left(t_{c}+\varepsilon\right){\sf sdpval}(G^{\prime})$
		$\displaystyle\geq\alpha_{\mathsf{GW}}\,{\sf sdpval}(G^{\prime})+\delta\left(% \frac{\varepsilon}{\left(1-t_{c}-\varepsilon\right)}\right)\left(t_{c}+% \varepsilon\right){\sf sdpval}(G^{\prime})$
		$\displaystyle=\left(\alpha_{\mathsf{GW}}+{\delta\left(t_{c}+\varepsilon\right)% \left(\frac{\varepsilon}{1-t_{c}-\varepsilon}\right)}\right){\sf sdpval}(G^{% \prime})$

Putting everything together we have that regardless of the value of ${\sf sdpval}(G^{\prime})$ ,

\displaystyle\operatorname*{\mathbb{E}}[\mathsf{Alg}\text{\small+}(G)]\geq% \left(\alpha_{\mathsf{GW}}+\min\left\{\delta,\delta\left(t_{c}+\varepsilon% \right)\left(\frac{\varepsilon}{1-t_{c}-\varepsilon}\right)\right\}\right){\sf sdpval% }(G^{\prime}).

Note that for choice of $\varepsilon$ in Equation 3 and using $\mu(G)\leq 1$ it follows that for $t_{c}\approx 0.84458$ ,

\displaystyle\hskip-5.0ptt_{c}+\varepsilon

\displaystyle\leq t_{c}+\frac{t_{c}-3/4}{9}={\frac{10t_{c}}{9}}-\frac{1}{12}<1% ,\frac{\varepsilon}{1-t_{c}-\varepsilon}\leq\frac{\frac{t_{c}}{9}-\frac{1}{12}% }{1-t_{c}-\left(\frac{t_{c}}{9}-\frac{1}{12}\right)}=\frac{4t_{c}-3}{39-40t_{c% }}<1

and hence one obtains that,

\displaystyle\min\left\{\delta,\delta\left(t_{c}+\varepsilon\right)\left(\frac% {\varepsilon}{1-t_{c}-\varepsilon}\right)\right\}=\delta\left(t_{c}+% \varepsilon\right)\left(\frac{\varepsilon}{1-t_{c}-\varepsilon}\right)

Setting the value of $\varepsilon$ from Equation 3 it follows that,

\displaystyle\operatorname*{\mathbb{E}}[\mathsf{Alg}\text{\small+}(G)]\geq% \left(\alpha_{\mathsf{GW}}+{\delta\left(t_{c}+\frac{(t_{c}-3/4)\mu(G)}{9}% \right)\left(\frac{\frac{(t_{c}-3/4)\mu(G)}{9}}{1-t_{c}-\frac{(t_{c}-3/4)\mu(G% )}{9}}\right)}\right){\sf sdpval}(G^{\prime}).

Now to simplify the notation in rest of the analysis consider a definition,

Definition 27 (Final Improvement).

Denote the final improvement (over $\alpha_{\mathsf{GW}}$ ) as $\tau$ by letting,

\displaystyle\tau\stackrel{{\scriptstyle\textup{def}}}{{=}}\frac{\delta}{2}% \left(t_{c}+\frac{(t_{c}-3/4)\mu(G)}{9}\right)\left(\frac{\frac{(t_{c}-3/4)\mu% (G)}{9}}{1-t_{c}-\frac{(t_{c}-3/4)\mu(G)}{9}}\right).

Thus one notes that $\operatorname*{\mathbb{E}}[\mathsf{Alg}\text{\small+}(G)]\geq\left(\alpha_{% \mathsf{GW}}+2\tau\right){\sf sdpval}(G^{\prime})$ . Now using Theorem 26 for choice of $\upsilon=\tau/\left(4\alpha_{\mathsf{GW}}+8\tau\right)$ it follows that,

$\displaystyle\operatorname*{\mathbb{E}}[\mathsf{Alg}\text{\small+}(G)]$	$\displaystyle\geq\left(\alpha_{\mathsf{GW}}+2\tau\right){\sf sdpval}(G^{\prime})$
	$\displaystyle\geq\left(\alpha_{\mathsf{GW}}+2\tau\right)\left({\sf sdpopt}(G)-% 2\upsilon\left\lvert E\right\rvert\right)$	$\displaystyle\left(\text{Using \lx@cref{creftype~refnum}{thm:fast_sdp_solver}}\right)$
	$\displaystyle\geq\left(\alpha_{\mathsf{GW}}+2\tau\right)\left(1-4\upsilon% \right){\sf sdpopt}(G)$	$\displaystyle\left(\text{Using }{\sf sdpopt}(G)\geq\mathsf{opt}(G)\geq\left% \lvert E\right\rvert/2\right)$
	$\displaystyle=\left(\alpha_{\mathsf{GW}}+\tau\right){\sf sdpopt}(G)$	$\displaystyle\left(\text{Using choice of $\upsilon$}\right)$
	$\displaystyle\geq\left(\alpha_{\mathsf{GW}}+\tau\right)\mathsf{opt}(G)$	$\displaystyle\left(\text{Since }{\sf sdpopt}(G)\geq\mathsf{opt}(G)\right).$

The running time is $O(\left\lvert E\right\rvert\log^{2}\left\lvert V\right\rvert{\sf poly}(1/\tau))$ and it is easy to note from Definition 27 that $\tau=\Omega(\delta\mu^{2}(G))$ and hence the running time is $O\left(\left\lvert E\right\rvert\log^{2}\left\lvert V\right\rvert{\sf poly}% \left(1/\left(\delta\mu^{2}(G)\right)\right)\right)$ . $\hfill\blacktriangleleft$

4 Applications of Improved Maxcut SDP Analysis

In this section, we apply Theorem 18 to derive improved approximation guarantees for Maxcut problem on some natural class of graphs. We show that $\left(\alpha_{\mathsf{GW}}+\Omega(1)\right)$ -approximation is achievable by showing that $\mu(G)=\Omega(1)$ indeed holds for these classes of graphs.

4.1 Geometric Intersection Graphs of Unit Balls

Given a set of geometric objects, a geometric intersection graph is constructed by representing each object as a vertex and placing an edge between two vertices if and only if the corresponding objects intersect.

Definition 28 (Unit Ball Graph in $\mathbb{R}^{k}$ ).

An undirected graph $G=(V,E)$ is said to be a unit ball graph if there exists an embedding $\varphi:V\rightarrow\mathbb{R}^{k}$ such that for every vertex $u\in V$ , we associate a unit radius ball centered at $\varphi(u)$ , and for all $u,v\in V$ we have,

\displaystyle\left\{u,v\right\}\in E\Longleftrightarrow\left\lVert\varphi(u)-% \varphi(v)\right\rVert_{2}\leq 2\quad\text{ i.e., an edge exists iff the % vertex balls intersect}.

$\blacktriangleright$ Remark 29.

Since recognizing whether a graph (given in standard representation such as adjacency list or matrix), is a unit ball graph is NP-hard (even for $k=2$ , see [20]), one assumes that the mapping $\varphi$ is given explicitly as part of the input.

Our goal in this section is to show that any unit ball graph with sufficiently high average degree satisfies $\mu(G)=\Omega(1)$ by exhibiting that it has $\Delta(G)=\Omega\left(\left\lvert E\right\rvert\right)$ many edge-disjoint triangles.

Definition 30 (Covering Number).

The covering number ${C(l,\theta)}$ is the minimum number of spherical caps of angular radius $\theta$ required to cover the entire sphere $\mathbb{S}^{l-1}$ . We let $N_{l}=C(l,\pi/6)$ , be the covering number with spherical caps of angular radius¹¹1A spherical cap of angular radius $\theta$ is set of points on surface of sphere with angular distance from center at most $\theta$ . $\pi/6$ . Equivalently, in each such cap, the angle between any two points is at most $\pi/3$ .

Theorem 31.

Let $G=(V,E)$ be a unit ball graph in $\mathbb{R}^{k}$ with average degree $d_{\mathsf{avg}}\geq 6N_{k}$ . Then $G$ contains $\left\lvert E\right\rvert/216N_{k}^{2}$ edge-disjoint triangles.

Construction 32 (Spherical Cap Partitioning).

Fix a vertex $v\in V$ of degree $r=\deg(v)$ , and let the set $S(v)=v\cup N(v)$ . Without loss of generality, translate the embedding so that $\varphi(v)=O$ (the origin). For each neighbor $u\in N(v)$ define:

\displaystyle p_{u}=\varphi(u)\text{ and }\hat{p}_{u}=\frac{p_{u}}{\left\lVert p% _{u}\right\rVert}\in\mathbb{S}^{k-1}\text{ that represent unit direction from % $v$ to $u$}.

Let $\left\{\mathcal{C}_{1},\mathcal{C}_{2},\dots,\mathcal{C}_{N_{k}}\right\}$ be a covering of $\mathbb{S}^{k-1}$ by spherical caps of angular radius $\pi/6$ where $N_{k}=C(k,\pi/6)$ . We then group the neighbors of $v$ according to which cap the direction falls into as,

\displaystyle R_{i}(v)=\left\{u\in N(v):\hat{p}_{u}\in C_{i}\right\},\quad i% \in\left\{1,2,\dots,N_{k}\right\}

Fact 33.

For $l\in\mathbb{N}$ we define $N_{l}\stackrel{{\scriptstyle\textup{def}}}{{=}}C(l,\pi/6)$ . Then for all dimensions $l$ , the covering number $N_{l}$ satisfies $N_{l}\leq 2^{3l}$ .

Proof.

We consider a proof by the connection to packing number. We define the packing number as,

Definition 34 (Packing Number).

The packing number, denoted $P(l,\theta)$ is the maximum number of points that can be placed on the unit sphere $\mathbb{S}^{l-1}$ such that the angular distance between any pair of points is at least $\theta$ .

$\blacktriangleright$ Remark 35.

The kissing number $\kappa_{l}$ in $\mathbb{R}^{l}$ is defined as the maximum number of non-overlapping unit balls that can simultaneously touch a central unit ball. Equivalently $\kappa_{l}=P(l,\pi/3)$ since the angle between any two such directions must be at least $\pi/3$ .

Fact 36 (Covering-Packing Duality, Lemma 5.5 in [72]).

For all dimensions $l$ , the packing number and covering number satisfy the following relation,

\displaystyle P(l,\theta)\leq C(l,\theta)\leq P(l,\theta/2).

Now using the general bounds in the works [51, 26] and using the Fact 36 one notes that,

\displaystyle N_{l}=C(l,\pi/6)\leq P(l,\pi/12)\leq\left(7.67\right)^{l-2}\leq 2% ^{3l}

where the last inequality is easy to check, and this finishes the proof. $\hfill\blacktriangleleft$

Claim 37.

Let the vertices $x,y,z\in R_{i}(v)$ for some $i\in\left\{1,2,\dots,N_{k}\right\}$ . Then it follows that $\left\{x,y,z\right\}$ forms a triangle.

Proof.

By construction, all three vertices $x, y, z$ lie in the same spherical cap $\mathcal{C}_{i}$ of angular radius $\pi/6$ . Therefore the angular distance between any two direction vectors is at most $\pi/3$ . In particular,

	$\displaystyle\left\lVert p_{x}-p_{y}\right\rVert^{2}$	$\displaystyle=\left\lVert p_{x}\right\rVert_{2}^{2}+\left\lVert p_{y}\right% \rVert_{2}^{2}-2p_{x}^{T}p_{y}=\left\lVert p_{x}\right\rVert_{2}^{2}+\left% \lVert p_{y}\right\rVert_{2}^{2}-2\left\lVert p_{x}\right\rVert_{2}\left\lVert p% _{y}\right\rVert_{2}\left\langle\hat{p}_{x},\hat{p}_{y}\right\rangle$
		$\displaystyle\leq\left\lVert p_{x}\right\rVert_{2}^{2}+\left\lVert p_{y}\right% \rVert_{2}^{2}-\left\lVert p_{x}\right\rVert_{2}\left\lVert p_{y}\right\rVert_% {2}\leq\left\lVert p_{x}\right\rVert_{2}^{2}+\left\lVert p_{y}\right\rVert_{2}% ^{2}-\min\left\{\left\lVert p_{x}\right\rVert_{2}^{2},\left\lVert p_{y}\right% \rVert_{2}^{2}\right\}$
		$\displaystyle=\max\left\{\left\lVert p_{x}\right\rVert_{2}^{2},\left\lVert p_{% y}\right\rVert_{2}^{2}\right\}=4$

and hence $\left\lVert p_{x}-p_{y}\right\rVert\leq 2$ and $\left\{x,y\right\}\in E$ . The same argument applies to pairs $\left\{y,z\right\}$ and $\left\{x,z\right\}$ , and hence all three edges $\left\{x,y\right\},\left\{y,z\right\}\left\{x,z\right\}$ are present. Therefore, $\left\{x,y,z\right\}$ forms a triangle. $\hfill\vartriangleleft$

If $n=6x+1$ or $n=6x+3$ , one gets a decomposition of complete graph $K_{n}$ into edge-disjoint triangles, the number of edge-disjoint triangles is exactly $\binom{n}{2}/3$ , a perfect packing of edge-disjoint triangles. We consider the following result that tells the maximum number of edge-disjoint triangles that can be packed into $K_{n}$ when $n$ is not of the form $6x+1$ or $6x+3$ ,

Fact 38 (Theorem 2, [33]).

Given a complete graph $K_{n}$ where $\left\lvert V\right\rvert=n=6x+i,0\leq i\leq 5$ ,

\displaystyle\Delta(K_{n})=\begin{cases}\frac{\binom{n}{2}-\frac{n}{2}}{3}&% \text{ if }i=0,2\\[8.61108pt] \frac{\binom{n}{2}}{3}&\text{ if }i=1,3\\[8.61108pt] \frac{\binom{n}{2}-\frac{n}{2}-1}{3}&\text{ if }i=4\\[8.61108pt] \frac{\binom{n}{2}-4}{3}&\text{ if }i=5,\end{cases},\,\,\text{thus a uniform % lower bound, }\Delta(K_{n})\geq\frac{\binom{n}{2}-\frac{n}{2}-1}{3}.

Lemma 39.

Let $G=(V,E)$ be a unit ball graph in $\mathbb{R}^{k}$ . Fix a vertex $v\in V$ of degree $d\geq 3N_{k}$ and let $S(v)=\left\{v\right\}\cup N(v)$ . Then the induced subgraph $G[S(v)]$ has at least $d^{2}/54N_{k}^{2}$ edge-disjoint triangles.

Proof.

Recall Construction 32 for vertex $v$ where we partition $\mathbb{S}^{k-1}$ into $N_{k}$ spherical caps of angular radius $\pi/6$ . By a simple averaging argument, some cap (say $\mathcal{C}_{i}$ ) contains at least $\lfloor d/N_{k}\rfloor$ neighbors of $v$ . Including $v$ this gives us a set of $n^{\prime}=\lfloor d/N_{k}\rfloor+1$ vertices all lying in the same region $R_{i}(v)$ . By Claim 37, the subgraph induced by this set forms a clique of size $n^{\prime}=\lfloor d/N_{k}\rfloor+1$ . Using Fact 38 the number of edge disjoint triangles in a clique of size $n^{\prime}$ is at least,

\displaystyle\frac{\binom{n^{\prime}}{2}-\left(n^{\prime}/2+1\right)}{3}=\frac% {n^{\prime 2}-2n^{\prime}-2}{6}

Now let $C$ be a constant such that $d\geq CN_{k}$ . Since $n^{\prime}=\lfloor d/N_{k}\rfloor+1\geq d/N_{k}$ it follows that,

\displaystyle\frac{n^{\prime 2}-2n^{\prime}-2}{6}\geq\left(\frac{1-2/C-2/C^{2}% }{6}\right)\frac{d^{2}}{N_{k}^{2}}

The coefficient above is non-negative when $1-2/C-2/C^{2}\geq 0$ which holds for $C\geq 1+\sqrt{3}\approx 2.732$ . For simplicity taking $C=3$ gives a valid lower bound whenever $d\geq 3N_{k}$ and one obtains that the number of edge-disjoint triangles in $G[S(v)]$ is at least,

\displaystyle\left(\frac{1-2/3-2/9}{6}\right)\frac{d^{2}}{N_{k}^{2}}=\frac{d^{% 2}}{54N_{k}^{2}}.

$\hfill\blacktriangleleft$

Proof of Theorem 31.

We will give a constructive proof for this by extracting edge-disjoint triangles greedily as below,

Algorithm.

Initialize $G_{0}=G$ , $m_{0}=m=\left\lvert E\right\rvert$ , and initially empty set of edge disjoint triangles $\mathcal{T}\leftarrow\emptyset$ . For rounds $i=1,2,\dots$ , do the following:

1.

If $\max\limits_{v\in V(G_{i-1})}\deg\limits_{G_{i-1}}(v)\leq 3N_{k}$ , then terminate.
2.

Otherwise choose a vertex $v_{i}$ in $G_{i-1}$ with maximum degree where $d_{i}\geq 3N_{k}$ .
3.

Apply Lemma 39 to extract edge disjoint triangles $\mathcal{T}_{i}$ from $G_{i-1}[S(v_{i})]$ and add to $\mathcal{T}$ .
4.

Delete all vertices in $S(v_{i})$ and their incident edges to form a graph $G_{i}$ . Let $m_{i}=\left\lvert E(G_{i})\right\rvert$ .

It is easy to see that when procedure terminates correctly. Each triangle in $\mathcal{T}$ is edge-disjoint by construction. Since all vertices and their incident edges in $S(v_{i})$ are removed in each round, no triangle in any subsequent round can share an edge with any triangle previously added. Thus, $\mathcal{T}$ is a collection of edge-disjoint triangles.

In each round we remove $m_{i-1}-m_{i}$ edges, which is at most $\left(d_{i}+1\right)d_{i}\leq 2d_{i}^{2}$ (since each vertex in $S(v_{i})$ has degree at most $d_{i}$ in $G_{i-1}$ ). By Lemma 39, we add at least $d_{i}^{2}/(54N_{k}^{2})$ triangles. Therefore, the number of triangles added satisfies:

\displaystyle\left\lvert\mathcal{T}_{i}\right\rvert\geq\frac{d_{i}^{2}}{54N_{k% }^{2}}\geq\frac{m_{i-1}-m_{i}}{108N_{k}^{2}}

(5)

Let the procedure end after $r$ rounds where one notes that $r\geq 1$ since to start with the graph has average degree at least $6N_{k}$ and hence,

\displaystyle m_{0}=\left\lvert E\right\rvert\geq\frac{6N_{k}\left\lvert V% \right\rvert}{2}=3N_{k}\left\lvert V\right\rvert

(6)

Each round removes at least one vertex and hence $\left\lvert V(G_{r})\right\rvert\leq\left\lvert V\right\rvert-r$ and in $G_{r}$ we have all degrees are smaller than $3N_{k}$ and hence,

\displaystyle m_{r}\leq\frac{1}{2}\left(3N_{k}-1\right)\left\lvert V(G_{r})% \right\rvert<\frac{3N_{k}}{2}\left(\left\lvert V\right\rvert-r\right)<\frac{3N% _{k}\left\lvert V\right\rvert}{2}

(7)

and using Equation 6 one concludes that $m_{r}\leq m_{0}/2$ .

Finally, summing over all the rounds and using Equation 5 the number of edge-disjoint triangles,

\displaystyle\left\lvert\mathcal{T}\right\rvert=\sum_{i=1}^{r}\left\lvert% \mathcal{T}_{i}\right\rvert\geq\sum_{i=1}^{r}\left(\frac{m_{i-1}-m_{i}}{108N_{% k}^{2}}\right)=\frac{m_{0}-m_{r}}{108N_{k}^{2}}\geq\frac{m_{0}}{216N_{k}^{2}}=% \frac{\left\lvert E\right\rvert}{216N_{k}^{2}}.

$\hfill\blacktriangleleft$

4.2 Real-World Network Graphs

While the performance of Maxcut SDP on random Erdős–Rényi $G(n,p)$ graphs has received considerable attention, with several works [27, 62, 38, 61] showing that $\alpha_{\mathsf{GW}}$ -approximation ratio can be significantly improved. However, Erdős–Rényi graphs are often too simplified of model that fail to capture many key features of real-world networks. This includes the presence of community structure, heavy-tailed degree distributions, small diameter, and high clustering coefficients. There are various models proposed that address these shortcomings, the most popular ones being the Preferential Attachment Model due to [8] and the small-world network model due to [74] More recently frameworks such as the combinatorial triangle-dense decompositions by [40] and the “spectral triadic decomposition” by [12], emphasize the role of triangles and higher-order motifs in capturing the nuanced community structure of real-world networks.

While one might expect that tailored algorithms could yield much better than $\alpha_{\mathsf{GW}}$ -approximation in such models by exploiting the structure in such graphs. However, we show here that one can use the result from our SDP analysis in a black box fashion to show an $\left(\alpha_{\mathsf{GW}}+\Omega(1)\right)$ -approximation on such real-world network graphs.

4.2.1 Spectral Triadic Decomposition Framework

The spectral triadic decomposition proposed by [12] provides an analytical model for studying the community structure of real-world networks. They define a spectral measure called “spectral transitivity” denoted $\tau(G)$ , which quantifies the pervalence of triangles in real-world graphs. They show that a large value for this measure allows for a graph decomposition into multiple dense “clique like” structures capturing a stylized form of community structure observed in real-world networks.

Definition 40 (Spectral Transitivity, Definition 1.1 in [12]).

For an undirected graph $G$ with a normalized adjacency matrix $\mathcal{A}$ , the spectral transitivity denoted $\tau(G)$ is defined as,

\displaystyle\tau(G)=\frac{\sum\limits_{i=1}^{n}\lambda_{i}^{3}}{\sum\limits_{% i=1}^{n}\lambda_{i}^{2}}.

where $\lambda_{1},\lambda_{2},\dots,\lambda_{n}$ are eigenvalues of $\mathcal{A}$ .

$\blacktriangleright$ Remark 41.

This measure is a reweighted version of transitivity notion from [40]. For simplicity we restrict to $d$ -regular graphs where $\mathcal{A}=A/d$ . For an edge $\left\{u,v\right\}$ the weight is defined as $1/d_{u}d_{v}=1/d^{2}$ and for a triangle $\left\{u,v,w\right\}$ it is defined to be $1/d_{u}d_{v}d_{w}=1/d^{3}$

Lemma 42 (Lemma 3.5 in [12]).

For a $d$ -regular graph $G=(V,E)$ having $T(G)$ many triangles, the spectral transitivity is,

\displaystyle\tau(G)=\frac{3\sum\limits_{t\in T}w(t)}{\sum\limits_{e\in E}w(e)% }=\frac{3T(G)/d^{3}}{\left\lvert E\right\rvert/d^{2}}=\frac{3T(G)}{\left\lvert E% \right\rvert d}.

Lemma 43.

Let $G$ be a $d$ -regular graphs with $d\geq 3$ , and $\tau(G)\geq c$ for a constant $c>0$ , then $\tau(G)\geq c/3$ .

Proof.

Consider the quantity $t_{e}=\left\lvert t\in T(G):e\in T\right\rvert$ which calculates the number of triangles containing edge $e$ , and let $t^{*}=\max_{e\in E}t_{e}$ . In a $d$ -regular graph it is easy to see that $t_{e}\leq d-1$ and hence $t^{*}\leq d-1$ . Now, we greedily pick a triangle and remove its three edges from the graph. The total number of triangles in the graph can go down by at most $3t^{*}$ . Thus we have that total number of edge-disjoint triangles is at least,

\displaystyle\Delta(G)\geq\frac{T(G)}{1+3t^{*}}\geq\frac{T(G)}{1+3(d-1)}\geq% \frac{T(G)}{3d-2}

and using $d\geq 3$ and using Lemma 42 we have that,

\displaystyle\Delta(G)\geq\frac{\tau(G)\left\lvert E\right\rvert d}{3(3d-2)}% \geq\frac{c\left\lvert E\right\rvert}{9}\text{ and hence }\tau(G)=\frac{3% \Delta(G)}{\left\lvert E\right\rvert}\geq\frac{c}{3}.

$\hfill\blacktriangleleft$

References

[1] Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee, and Bodhayan Roy. Complexity of maximum cut on interval graphs. In 37th International Symposium on Computational Geometry (SoCG), volume 189, pages 7:1–7:11, 2021. doi:10.4230/LIPICS.SOCG.2021.7.
[2] Noga Alon and Assaf Naor. Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput., 35(4):787–803, 2006. doi:10.1137/S0097539704441629.
[3] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. J. ACM, 63(2):Art. 12, 35, 2016. doi:10.1145/2837020.
[4] Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. System Sci., 58(1):193–210, 1999. doi:10.1006/jcss.1998.1605.
[5] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):Art. 5, 37, 2009. doi:10.1145/1502793.1502794.
[6] Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better balance by being biased: a 0.8776-approximation for Max Bisection. ACM Trans. Algorithms, 13(1):Art. 2, 27, 2016. doi:10.1145/2907052.
[7] R. Bar-Yehuda, M. M. Halldórsson, J. Naor, H. Shachnai, and I. Shapira. Scheduling split intervals. SIAM J. Comput., 36(1):1–15, 2006. doi:10.1137/S0097539703437843.
[8] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, 1999. doi:10.1126/science.286.5439.509.
[9] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res., 36(3):493–513, June 1988. doi:10.1287/OPRE.36.3.493.
[10] Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pages 472–481. IEEE Computer Soc., Los Alamitos, CA, 2011. doi:10.1109/FOCS.2011.95.
[11] Alexey Barsukov and Bodhayan Roy. Maximum cut on interval graphs of interval count two is np-complete, 2024. arXiv:2203.06630.
[12] Sabyasachi Basu, Suman Kalyan Bera, and C. Seshadhri. Spectral triadic decompositions of real-world networks. SIAM J. Math. Data Sci., 6(3):703–730, 2024. doi:10.1137/23M1586926.
[13] Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In icalp, pages 200–209, 1999. doi:10.1007/3-540-48523-6_17.
[14] Hans L. Bodlaender, Celina M. H. de Figueiredo, Marisa Gutierrez, Ton Kloks, and Rolf Niedermeier. Simple max-cut for split-indifference graphs and graphs with few p4’s. In Experimental and Efficient Algorithms, pages 87–99, 2004. doi:10.1007/978-3-540-24838-5_7.
[15] Hans L. Bodlaender and Klaus Jansen. On the complexity of the maximum cut problem. Nordic Journal of Computing, 7(1):14–31, 2000.
[16] Hans L. Bodlaender, Ton Kloks, and Rolf Niedermeier. Simple max-cut for unit interval graphs and graphs with few p4s. Electronic Notes in Discrete Mathematics, 3:19–26, 1999. doi:10.1016/S1571-0653(05)80014-9.
[17] Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using $P Q$ -tree algorithms. J. Comput. System Sci., 13(3):335–379, 1976. doi:10.1016/S0022-0000(76)80045-1.
[18] Arman Boyacı, Tinaz Ekim, and Mordechai Shalom. A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Information Processing Letters, 121:29–33, 2017. doi:10.1016/j.ipl.2017.01.007.
[19] Arman Boyacı, Tınaz Ekim, and Mordechai Shalom. The maximum cardinality cut problem in co-bipartite chain graphs. Journal of Combinatorial Optimization, 35(1):250–265, 2018. doi:10.1007/s10878-015-9963-x.
[20] Heinz Breu and David G. Kirkpatrick. Unit disk graph recognition is NP-hard. Comput. Geom., 9(1-2):3–24, 1998. doi:10.1016/S0925-7721(97)00014-X.
[21] Martin C. Carlisle and Errol L. Lloyd. On the $k$ -coloring of intervals. Discrete Appl. Math., 59(3):225–235, 1995. doi:10.1016/0166-218X(93)E0174-W.
[22] Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca Trevisan. Lower bounds for max-cut in $H$ -free graphs via semidefinite programming. SIAM J. Discrete Math., 35(3):1557–1568, 2021. doi:10.1137/20M1333985.
[23] K.C. Chang and D.H.-C. Du. Efficient algorithms for layer assignment problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(1):67–78, 1987. doi:10.1109/TCAD.1987.1270247.
[24] Maw-Shang Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput., 27(6):1671–1694, December 1998. doi:10.1137/S0097539792238431.
[25] Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending grothendieck’s inequality. In focs, pages 54–60, 2004. doi:10.1109/FOCS.2004.39.
[26] John H. Conway and Neil J. A. Sloane. Sphere Packings, Lattices and Groups, volume 290 of Grundlehren der mathematischen Wissenschaften. Springer, 3rd edition, 1999.
[27] Hervé Daudé, Conrado Martínez, Vonjy Rasendrahasina, and Vlady Ravelomanana. The MAX-CUT of sparse random graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 265–271. ACM, New York, 2012. doi:10.1137/1.9781611973099.24.
[28] Celina MH de Figueiredo, Alexsander A de Melo, Fabiano S Oliveira, and Ana Silva. Maximum cut on interval graphs of interval count four is np-complete. arXiv preprint, 2020. arXiv:2012.09804.
[29] Charles Delorme and Svatopluk Poljak. Combinatorial properties and the complexity of a max-cut approximation. European J. Combin., 14(4):313–333, 1993. doi:10.1006/eujc.1993.1035.
[30] Josep Díaz and Marcin Kamiński. Max-cut and max-bisection are NP-hard on unit disk graphs. Theoretical Computer Science, 377(1):271–276, 2007. doi:10.1016/j.tcs.2007.02.013.
[31] C. S. Edwards. An improved lower bound for the number of edges in a largest bipartite subgraph. In Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pages 167–181. Academia, Prague, 1975.
[32] Pál Erdős. On even subgraphs of graphs. Mat. Lapok, 18:283–288, 1967.
[33] Tomás Feder and Carlos S. Subi. Packing edge-disjoint triangles in given graphs. Electron. Colloquium Comput. Complex., TR12-013, 2012. URL: https://eccc.weizmann.ac.il/report/2012/013.
[34] Uriel Feige, Marek Karpinski, and Michael Langberg. Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms, 43(2):201–219, 2002. doi:10.1016/S0196-6774(02)00005-6.
[35] Uriel Feige and Michael Langberg. The $\rm RPR^{2}$ rounding technique for semidefinite programs. J. Algorithms, 60(1):1–23, 2006. doi:10.1016/j.jalgor.2004.11.003.
[36] Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. Random Structures Algorithms, 20(3):403–440, 2002. Probabilistic methods in combinatorial optimization. doi:10.1002/rsa.10036.
[37] Mikael Florén. Approximation of max-cut on graphs of bounded degree, 2016.
[38] David Gamarnik and Quan Li. On the max-cut of sparse random graphs. Random Structures Algorithms, 52(2):219–262, 2018. doi:10.1002/rsa.20738.
[39] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach., 42(6):1115–1145, 1995. doi:10.1145/227683.227684.
[40] Rishi Gupta, Tim Roughgarden, and C. Seshadhri. Decompositions of triangle-dense graphs. SIAM J. Comput., 45(2):197–215, 2016. doi:10.1137/140955331.
[41] Venkatesan Guruswami. Maximum cut on line and total graphs. Discrete Applied Mathematics, 92(2):217–221, 1999. doi:10.1016/S0166-218X(99)00056-6.
[42] Venkatesan Guruswami and Ali Kemal Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graphs partitioning and quadratic integer programming with PSD objectives (extended abstract). In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science – FOCS 2011, pages 482–491. IEEE Computer Soc., Los Alamitos, CA, 2011. doi:10.1109/FOCS.2011.36.
[43] F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4(3):221–225, 1975. doi:10.1137/0204019.
[44] Jun-Ting Hsieh and Pravesh K. Kothari. Approximating max-cut on bounded degree graphs: tighter analysis of the FKL algorithm. In 50th International Colloquium on Automata, Languages, and Programming, volume 261 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 77, 7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.77.
[45] M.L. Huson and A. Sen. Broadcast scheduling algorithms for radio networks. In Proceedings of MILCOM ’95, volume 2, pages 647–651 vol.2, 1995. doi:10.1109/MILCOM.1995.483546.
[46] Johan Håstad. Some optimal inapproximability results. In STOC ’97 (El Paso, TX), pages 1–10. ACM, New York, 1999.
[47] Hiroshi Imai and Takao Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms, 4(4):310–323, 1983. doi:10.1016/0196-6774(83)90012-3.
[48] Klaus Jansen, Marek Karpinski, Andrzej Lingas, and Eike Seidel. Polynomial time approximation schemes for max-bisection on planar and geometric graphs. SIAM J. Comput., 35(1):110–119, 2005. doi:10.1137/S009753970139567X.
[49] David S Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 6(3):434–451, 1985. doi:10.1016/0196-6774(85)90012-4.
[50] John R. Jungck, Gregg Dick, and Amy Gleason Dick. Computer-assisted sequencing, interval graphs, and molecular evolution. Biosystems, 15(3):259–273, 1982. doi:10.1016/0303-2647(82)90010-7.
[51] G. A. Kabatiansky and V. I. Levenshtein. On bounds for packings on a sphere and in space. Problems of Information Transmission, 14(1):1–17, 1978. Originally in Russian: Probl. Peredachi Inf. 14(1):3–25.
[52] Satyen Kale and C. Seshadhri. Combinatorial approximation algorithms for maxcut using random walks. In Proceedings of 2nd Symposium on Innovations in Computer Science (ICS), pages 367–388, 2011. URL: http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/20.html.
[53] Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), The IBM Research Symposia Series, pages 85–103. Plenum, New York-London, 1972. doi:10.1007/978-1-4684-2001-2_9.
[54] Ken-ichi Kawarabayashi, Mikkel Thorup, and Hirotaka Yoneda. Better coloring of 3-colorable graphs. In STOC’24—Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 331–339. ACM, New York, 2024. doi:10.1145/3618260.3649768.
[55] J. Mark Keil. Finding Hamiltonian circuits in interval graphs. Inform. Process. Lett., 20(4):201–206, 1985. doi:10.1016/0020-0190(85)90050-X.
[56] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 767–775. ACM, New York, 2002. doi:10.1145/509907.510017.
[57] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. doi:10.1137/S0097539705447372.
[58] Jan Kratochvíl, Tomáš Masařík, and Jana Novotná. U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170, pages 57:1–57:14, 2020. doi:10.4230/LIPIcs.MFCS.2020.57.
[59] Madhav V. Marathe, R. Ravi, and C. Pandu Rangan. Generalized vertex covering in interval graphs. Discrete Appl. Math., 39(1):87–93, 1992. doi:10.1016/0166-218X(92)90116-R.
[60] Claire Mathieu and Warren Schudy. Yet another algorithm for dense max cut: go greedy. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 176–182. ACM, New York, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347102.
[61] Renee Mirka and David P. Williamson. An experimental evaluation of semidefinite programming and spectral algorithms for max cut. ACM J. Exp. Algorithmics, 28, August 2023. doi:10.1145/3609426.
[62] Andrea Montanari and Subhabrata Sen. Semidefinite programs on sparse random graphs and their application to community detection. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 814–827, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2897518.2897548.
[63] Yurii Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods & Software, 9:141–160, 1998. URL: https://api.semanticscholar.org/CorpusID:121309892.
[64] Ryan O’Donnell and Yi Wu. An optimal SDP algorithm for max-cut, and equally optimal long code tests. In STOC’08, pages 335–344. ACM, New York, 2008. doi:10.1145/1374376.1374425.
[65] Prasad Raghavendra and David Steurer. How to round any CSP. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, pages 586–594. IEEE Computer Soc., Los Alamitos, CA, 2009. doi:10.1109/FOCS.2009.74.
[66] Sartaj Sahni and Teofilo Gonzalez. $P$ -complete approximation problems. J. Assoc. Comput. Mach., 23(3):555–565, 1976. doi:10.1145/321958.321975.
[67] José A. Soto. Improved analysis of a max-cut algorithm based on spectral partitioning. SIAM J. Discrete Math., 29(1):259–268, 2015. doi:10.1137/14099098X.
[68] David Steurer. Fast SDP algorithms for constraint satisfaction problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 684–697. SIAM, Philadelphia, PA, 2010. doi:10.1137/1.9781611973075.56.
[69] Chaitanya Swamy. Correlation clustering: maximizing agreements via semidefinite programming. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 526–527. ACM, New York, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982866.
[70] Luca Trevisan. Max cut and the smallest eigenvalue. siamj, 41(6):1769–1786, 2012. doi:10.1137/090773714.
[71] Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM J. Comput., 29(6):2074–2097, 2000. doi:10.1137/S0097539797328847.
[72] Martin J. Wainwright. High-dimensional statistics, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2019. A non-asymptotic viewpoint. doi:10.1017/9781108627771.
[73] Stanley Wasserman and Katherine Faust. Social Network Analysis: Methods and Applications. Structural Analysis in the Social Sciences. Cambridge University Press, 1994. doi:10.1017/CBO9780511815478.
[74] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442, 1998. doi:10.1038/30918.
[75] Mihalis Yannakakis and Fănică Gavril. The maximum $k$ -colorable subgraph problem for chordal graphs. Inform. Process. Lett., 24(2):133–137, 1987. doi:10.1016/0020-0190(87)90107-4.
[76] Uri Zwick. Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 679–687. ACM, New York, 1999. doi:10.1145/301250.301431.

[bib.bib1] [1] Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee, and Bodhayan Roy. Complexity of maximum cut on interval graphs. In 37th International Symposium on Computational Geometry (SoCG), volume 189, pages 7:1–7:11, 2021. doi:10.4230/LIPICS.SOCG.2021.7.

[bib.bib2] [2] Noga Alon and Assaf Naor. Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput., 35(4):787–803, 2006. doi:10.1137/S0097539704441629.

[bib.bib3] [3] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. J. ACM, 63(2):Art. 12, 35, 2016. doi:10.1145/2837020.

[bib.bib4] [4] Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. System Sci., 58(1):193–210, 1999. doi:10.1006/jcss.1998.1605.

[bib.bib5] [5] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):Art. 5, 37, 2009. doi:10.1145/1502793.1502794.

[bib.bib6] [6] Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better balance by being biased: a 0.8776-approximation for Max Bisection. ACM Trans. Algorithms, 13(1):Art. 2, 27, 2016. doi:10.1145/2907052.

[bib.bib7] [7] R. Bar-Yehuda, M. M. Halldórsson, J. Naor, H. Shachnai, and I. Shapira. Scheduling split intervals. SIAM J. Comput., 36(1):1–15, 2006. doi:10.1137/S0097539703437843.

[bib.bib8] [8] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, 1999. doi:10.1126/science.286.5439.509.

[bib.bib9] [9] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res., 36(3):493–513, June 1988. doi:10.1287/OPRE.36.3.493.

[bib.bib10] [10] Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pages 472–481. IEEE Computer Soc., Los Alamitos, CA, 2011. doi:10.1109/FOCS.2011.95.

[bib.bib11] [11] Alexey Barsukov and Bodhayan Roy. Maximum cut on interval graphs of interval count two is np-complete, 2024. arXiv:2203.06630.

[bib.bib12] [12] Sabyasachi Basu, Suman Kalyan Bera, and C. Seshadhri. Spectral triadic decompositions of real-world networks. SIAM J. Math. Data Sci., 6(3):703–730, 2024. doi:10.1137/23M1586926.

[bib.bib13] [13] Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In icalp, pages 200–209, 1999. doi:10.1007/3-540-48523-6_17.

[bib.bib14] [14] Hans L. Bodlaender, Celina M. H. de Figueiredo, Marisa Gutierrez, Ton Kloks, and Rolf Niedermeier. Simple max-cut for split-indifference graphs and graphs with few p4’s. In Experimental and Efficient Algorithms, pages 87–99, 2004. doi:10.1007/978-3-540-24838-5_7.

[bib.bib15] [15] Hans L. Bodlaender and Klaus Jansen. On the complexity of the maximum cut problem. Nordic Journal of Computing, 7(1):14–31, 2000.

[bib.bib16] [16] Hans L. Bodlaender, Ton Kloks, and Rolf Niedermeier. Simple max-cut for unit interval graphs and graphs with few p4s. Electronic Notes in Discrete Mathematics, 3:19–26, 1999. doi:10.1016/S1571-0653(05)80014-9.

[bib.bib17] [17] Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using $P Q$ -tree algorithms. J. Comput. System Sci., 13(3):335–379, 1976. doi:10.1016/S0022-0000(76)80045-1.

[bib.bib18] [18] Arman Boyacı, Tinaz Ekim, and Mordechai Shalom. A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Information Processing Letters, 121:29–33, 2017. doi:10.1016/j.ipl.2017.01.007.

[bib.bib19] [19] Arman Boyacı, Tınaz Ekim, and Mordechai Shalom. The maximum cardinality cut problem in co-bipartite chain graphs. Journal of Combinatorial Optimization, 35(1):250–265, 2018. doi:10.1007/s10878-015-9963-x.

[bib.bib20] [20] Heinz Breu and David G. Kirkpatrick. Unit disk graph recognition is NP-hard. Comput. Geom., 9(1-2):3–24, 1998. doi:10.1016/S0925-7721(97)00014-X.

[bib.bib21] [21] Martin C. Carlisle and Errol L. Lloyd. On the $k$ -coloring of intervals. Discrete Appl. Math., 59(3):225–235, 1995. doi:10.1016/0166-218X(93)E0174-W.

[bib.bib22] [22] Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca Trevisan. Lower bounds for max-cut in $H$ -free graphs via semidefinite programming. SIAM J. Discrete Math., 35(3):1557–1568, 2021. doi:10.1137/20M1333985.

[bib.bib23] [23] K.C. Chang and D.H.-C. Du. Efficient algorithms for layer assignment problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(1):67–78, 1987. doi:10.1109/TCAD.1987.1270247.

[bib.bib24] [24] Maw-Shang Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput., 27(6):1671–1694, December 1998. doi:10.1137/S0097539792238431.

[bib.bib25] [25] Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending grothendieck’s inequality. In focs, pages 54–60, 2004. doi:10.1109/FOCS.2004.39.

[bib.bib26] [26] John H. Conway and Neil J. A. Sloane. Sphere Packings, Lattices and Groups, volume 290 of Grundlehren der mathematischen Wissenschaften. Springer, 3rd edition, 1999.

[bib.bib27] [27] Hervé Daudé, Conrado Martínez, Vonjy Rasendrahasina, and Vlady Ravelomanana. The MAX-CUT of sparse random graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 265–271. ACM, New York, 2012. doi:10.1137/1.9781611973099.24.

[bib.bib28] [28] Celina MH de Figueiredo, Alexsander A de Melo, Fabiano S Oliveira, and Ana Silva. Maximum cut on interval graphs of interval count four is np-complete. arXiv preprint, 2020. arXiv:2012.09804.

[bib.bib29] [29] Charles Delorme and Svatopluk Poljak. Combinatorial properties and the complexity of a max-cut approximation. European J. Combin., 14(4):313–333, 1993. doi:10.1006/eujc.1993.1035.

[bib.bib30] [30] Josep Díaz and Marcin Kamiński. Max-cut and max-bisection are NP-hard on unit disk graphs. Theoretical Computer Science, 377(1):271–276, 2007. doi:10.1016/j.tcs.2007.02.013.

[bib.bib31] [31] C. S. Edwards. An improved lower bound for the number of edges in a largest bipartite subgraph. In Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pages 167–181. Academia, Prague, 1975.

[bib.bib32] [32] Pál Erdős. On even subgraphs of graphs. Mat. Lapok, 18:283–288, 1967.

[bib.bib33] [33] Tomás Feder and Carlos S. Subi. Packing edge-disjoint triangles in given graphs. Electron. Colloquium Comput. Complex., TR12-013, 2012. URL: https://eccc.weizmann.ac.il/report/2012/013.

[bib.bib34] [34] Uriel Feige, Marek Karpinski, and Michael Langberg. Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms, 43(2):201–219, 2002. doi:10.1016/S0196-6774(02)00005-6.

[bib.bib35] [35] Uriel Feige and Michael Langberg. The $\rm RPR^{2}$ rounding technique for semidefinite programs. J. Algorithms, 60(1):1–23, 2006. doi:10.1016/j.jalgor.2004.11.003.

[bib.bib36] [36] Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. Random Structures Algorithms, 20(3):403–440, 2002. Probabilistic methods in combinatorial optimization. doi:10.1002/rsa.10036.

[bib.bib37] [37] Mikael Florén. Approximation of max-cut on graphs of bounded degree, 2016.

[bib.bib38] [38] David Gamarnik and Quan Li. On the max-cut of sparse random graphs. Random Structures Algorithms, 52(2):219–262, 2018. doi:10.1002/rsa.20738.

[bib.bib39] [39] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach., 42(6):1115–1145, 1995. doi:10.1145/227683.227684.

[bib.bib40] [40] Rishi Gupta, Tim Roughgarden, and C. Seshadhri. Decompositions of triangle-dense graphs. SIAM J. Comput., 45(2):197–215, 2016. doi:10.1137/140955331.

[bib.bib41] [41] Venkatesan Guruswami. Maximum cut on line and total graphs. Discrete Applied Mathematics, 92(2):217–221, 1999. doi:10.1016/S0166-218X(99)00056-6.

[bib.bib42] [42] Venkatesan Guruswami and Ali Kemal Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graphs partitioning and quadratic integer programming with PSD objectives (extended abstract). In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science – FOCS 2011, pages 482–491. IEEE Computer Soc., Los Alamitos, CA, 2011. doi:10.1109/FOCS.2011.36.

[bib.bib43] [43] F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4(3):221–225, 1975. doi:10.1137/0204019.

[bib.bib44] [44] Jun-Ting Hsieh and Pravesh K. Kothari. Approximating max-cut on bounded degree graphs: tighter analysis of the FKL algorithm. In 50th International Colloquium on Automata, Languages, and Programming, volume 261 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 77, 7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.77.

[bib.bib45] [45] M.L. Huson and A. Sen. Broadcast scheduling algorithms for radio networks. In Proceedings of MILCOM ’95, volume 2, pages 647–651 vol.2, 1995. doi:10.1109/MILCOM.1995.483546.

[bib.bib46] [46] Johan Håstad. Some optimal inapproximability results. In STOC ’97 (El Paso, TX), pages 1–10. ACM, New York, 1999.

[bib.bib47] [47] Hiroshi Imai and Takao Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms, 4(4):310–323, 1983. doi:10.1016/0196-6774(83)90012-3.

[bib.bib48] [48] Klaus Jansen, Marek Karpinski, Andrzej Lingas, and Eike Seidel. Polynomial time approximation schemes for max-bisection on planar and geometric graphs. SIAM J. Comput., 35(1):110–119, 2005. doi:10.1137/S009753970139567X.

[bib.bib49] [49] David S Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 6(3):434–451, 1985. doi:10.1016/0196-6774(85)90012-4.

[bib.bib50] [50] John R. Jungck, Gregg Dick, and Amy Gleason Dick. Computer-assisted sequencing, interval graphs, and molecular evolution. Biosystems, 15(3):259–273, 1982. doi:10.1016/0303-2647(82)90010-7.

[bib.bib51] [51] G. A. Kabatiansky and V. I. Levenshtein. On bounds for packings on a sphere and in space. Problems of Information Transmission, 14(1):1–17, 1978. Originally in Russian: Probl. Peredachi Inf. 14(1):3–25.

[bib.bib52] [52] Satyen Kale and C. Seshadhri. Combinatorial approximation algorithms for maxcut using random walks. In Proceedings of 2nd Symposium on Innovations in Computer Science (ICS), pages 367–388, 2011. URL: http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/20.html.

[bib.bib53] [53] Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), The IBM Research Symposia Series, pages 85–103. Plenum, New York-London, 1972. doi:10.1007/978-1-4684-2001-2_9.

[bib.bib54] [54] Ken-ichi Kawarabayashi, Mikkel Thorup, and Hirotaka Yoneda. Better coloring of 3-colorable graphs. In STOC’24—Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 331–339. ACM, New York, 2024. doi:10.1145/3618260.3649768.

[bib.bib55] [55] J. Mark Keil. Finding Hamiltonian circuits in interval graphs. Inform. Process. Lett., 20(4):201–206, 1985. doi:10.1016/0020-0190(85)90050-X.

[bib.bib56] [56] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 767–775. ACM, New York, 2002. doi:10.1145/509907.510017.

[bib.bib57] [57] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. doi:10.1137/S0097539705447372.

[bib.bib58] [58] Jan Kratochvíl, Tomáš Masařík, and Jana Novotná. U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170, pages 57:1–57:14, 2020. doi:10.4230/LIPIcs.MFCS.2020.57.

[bib.bib59] [59] Madhav V. Marathe, R. Ravi, and C. Pandu Rangan. Generalized vertex covering in interval graphs. Discrete Appl. Math., 39(1):87–93, 1992. doi:10.1016/0166-218X(92)90116-R.

[bib.bib60] [60] Claire Mathieu and Warren Schudy. Yet another algorithm for dense max cut: go greedy. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 176–182. ACM, New York, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347102.

[bib.bib61] [61] Renee Mirka and David P. Williamson. An experimental evaluation of semidefinite programming and spectral algorithms for max cut. ACM J. Exp. Algorithmics, 28, August 2023. doi:10.1145/3609426.

[bib.bib62] [62] Andrea Montanari and Subhabrata Sen. Semidefinite programs on sparse random graphs and their application to community detection. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 814–827, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2897518.2897548.

[bib.bib63] [63] Yurii Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods & Software, 9:141–160, 1998. URL: https://api.semanticscholar.org/CorpusID:121309892.

[bib.bib64] [64] Ryan O’Donnell and Yi Wu. An optimal SDP algorithm for max-cut, and equally optimal long code tests. In STOC’08, pages 335–344. ACM, New York, 2008. doi:10.1145/1374376.1374425.

[bib.bib65] [65] Prasad Raghavendra and David Steurer. How to round any CSP. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, pages 586–594. IEEE Computer Soc., Los Alamitos, CA, 2009. doi:10.1109/FOCS.2009.74.

[bib.bib66] [66] Sartaj Sahni and Teofilo Gonzalez. $P$ -complete approximation problems. J. Assoc. Comput. Mach., 23(3):555–565, 1976. doi:10.1145/321958.321975.

[bib.bib67] [67] José A. Soto. Improved analysis of a max-cut algorithm based on spectral partitioning. SIAM J. Discrete Math., 29(1):259–268, 2015. doi:10.1137/14099098X.

[bib.bib68] [68] David Steurer. Fast SDP algorithms for constraint satisfaction problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 684–697. SIAM, Philadelphia, PA, 2010. doi:10.1137/1.9781611973075.56.

[bib.bib69] [69] Chaitanya Swamy. Correlation clustering: maximizing agreements via semidefinite programming. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 526–527. ACM, New York, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982866.

[bib.bib70] [70] Luca Trevisan. Max cut and the smallest eigenvalue. siamj, 41(6):1769–1786, 2012. doi:10.1137/090773714.

[bib.bib71] [71] Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM J. Comput., 29(6):2074–2097, 2000. doi:10.1137/S0097539797328847.

[bib.bib72] [72] Martin J. Wainwright. High-dimensional statistics, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2019. A non-asymptotic viewpoint. doi:10.1017/9781108627771.

[bib.bib73] [73] Stanley Wasserman and Katherine Faust. Social Network Analysis: Methods and Applications. Structural Analysis in the Social Sciences. Cambridge University Press, 1994. doi:10.1017/CBO9780511815478.

[bib.bib74] [74] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442, 1998. doi:10.1038/30918.

[bib.bib75] [75] Mihalis Yannakakis and Fănică Gavril. The maximum $k$ -colorable subgraph problem for chordal graphs. Inform. Process. Lett., 24(2):133–137, 1987. doi:10.1016/0020-0190(87)90107-4.

[bib.bib76] [76] Uri Zwick. Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 679–687. ACM, New York, 1999. doi:10.1145/301250.301431.

	$\displaystyle\frac{\arccos(r(1-2t))-\arccos(r)}{t}$	$\displaystyle=\frac{2r}{\sqrt{1-r^{2}(1-2t)^{2}}}$		(1)
	$\displaystyle\frac{1-\frac{t\left\lvert E\right\rvert}{{\sf sdpopt}}}{\sqrt{1-% r^{2}}}$	$\displaystyle=\frac{1-2t}{\sqrt{1-r^{2}(1-2t)^{2}}}$		(2)

Triangles Improve 0.878 Approximation for Maxcut

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Results and Techniques

Theorem 1 (Informal Version of Theorem 18).

Proposition 2 (Informal Version of Theorem 31).

Corollary 3.

▶ Remark 4.

Lemma 5 (Section 3 in [12]).

▶ Remark 6.

1.2 Related Work

Maxcut Problem

Maxcut SDP

Fast SDP Solvers

Geometric Intersection Graphs

Maxcut in Geometric Intersection Graphs

Real World Graphs

2 Overview and Discussion

2.1 Notation

2.2 Preliminaries

SDP 7 (Maxcut SDP).

Definition 8 (GW Critical Constants).

Theorem 9 (Theorem 3.3 in [39]).

Proof.

Theorem 10 (Theorem 3.1.1 in [39]).

▶ Remark 11 (Lemma 3.5 in [39]).

Zwick’s Outward Rotation Algorithm [76]

Theorem 12 (Theorem 3.3 in [76]).

▶ Remark 13 (Lemma 3.2 in [76]).

2.3 Our SDP Based Algorithm

Definition 14 (Edge-Disjoint Triangle Density).

▶ Remark 15.

Algorithm.

Definition 16 (Minimum Improvement).

Corollary 17.

2.4 Our SDP Analysis

Refined SDP Analysis

Improved Approximation Guarantees

Triangles and Good Edges

Averaging argument saves the day

Fast SDP Solvers

2.5 Applications of Improved SDP Analysis

Unit Disk Graphs

Real-World Network Graphs

3 Maxcut SDP Analysis

Theorem 18.

3.1 Improved Approximation Ratio Analysis

Definition 19 (Good and Bad Edges).

Definition 20 (Density Constants).

Lemma 21.

Proof.

Lemma 22.

Proof.

Lemma 23.

Proof.

Claim 24.

Proof.

Lemma 25.

Proof.

3.2 Running Time Analysis

Theorem 26 (Theorem 1.1 in [68]).

Proof of Theorem 18.

Definition 27 (Final Improvement).

4 Applications of Improved Maxcut SDP Analysis

4.1 Geometric Intersection Graphs of Unit Balls

Definition 28 (Unit Ball Graph in ℝk).

▶ Remark 29.

Definition 30 (Covering Number).

Theorem 31.

Construction 32 (Spherical Cap Partitioning).

Triangles Improve $0.878$ Approximation for Maxcut

$\blacktriangleright$ Remark 4.

$\blacktriangleright$ Remark 6.

$\blacktriangleright$ Remark 11 (Lemma 3.5 in [39]).

$\blacktriangleright$ Remark 13 (Lemma 3.2 in [76]).

$\blacktriangleright$ Remark 15.

Definition 28 (Unit Ball Graph in $\mathbb{R}^{k}$ ).

$\blacktriangleright$ Remark 29.

$\blacktriangleright$ Remark 35.

$\blacktriangleright$ Remark 41.