Fact-checked by Grok 2 weeks ago

Maximum cut

In graph theory and combinatorial optimization, the maximum cut problem (Max-Cut) seeks to partition the vertices of an undirected graph G = (V, E), possibly with edge weights w_{ij} \geq 0, into two disjoint subsets S \subseteq V and V \setminus S such that the total weight of edges crossing the cut—i.e., edges with one endpoint in S and the other in V \setminus S—is maximized.^[1] This problem is NP-hard, as established in Richard Karp's seminal 1972 list of 21 NP-complete problems via a reduction from the partition problem.^[2] Unlike the minimum cut problem, which is solvable in polynomial time using maximum flow algorithms, Max-Cut lacks an efficient exact solution for general graphs, prompting extensive research into approximation algorithms.^[3] The computational complexity of Max-Cut extends to its approximability: it is NP-hard to approximate within a factor better than $16/17 \approx 0.941,^[4] and the problem is MAX SNP-hard,^[1] implying that no polynomial-time approximation scheme exists unless P = NP. A landmark advancement is the randomized approximation algorithm by Michel Goemans and David Williamson (1995), which uses semidefinite programming relaxation followed by random hyperplane rounding to achieve an expected approximation ratio of at least $0.87856, improving upon the previous best guarantee of $0.5.^[1] This ratio remains the state-of-the-art for general graphs, though exact solutions are feasible for special cases like planar graphs or graphs with bounded treewidth via dynamic programming.^[5] Max-Cut has significant applications beyond theory, including VLSI circuit layout design—where partitioning components minimizes intra-block connections while maximizing inter-block ones—and statistical physics, such as modeling spin glass systems via the Ising model on graphs.^[1] It also arises in clustering tasks, network design for communication systems, and constraint satisfaction problems like MAX 2-SAT, where approximations inform practical heuristics in machine learning and operations research.^[6]

Definition and Basics

Formal Definition

The maximum cut problem, a fundamental optimization problem in graph theory, involves finding a partition of the vertex set V of an undirected graph G = (V, E) into two disjoint subsets S \subseteq V and V \setminus S such that the number of edges crossing between them is maximized. The size of the cut is given by

\cut(S, V \setminus S) = \bigl| \bigl\{ \{u, v\} \in E \;\big|\; u \in S,\ v \in V \setminus S \bigr\} \bigr|,

and the objective in the unweighted case is to maximize this quantity over all possible subsets S. Let n = |V| denote the number of vertices and m = |E| the number of edges; the maximum cut value of G is denoted \alpha(G).^[1] The decision version of the maximum cut problem asks, given an integer k, whether there exists a partition (S, V \setminus S) with \cut(S, V \setminus S) \geq k. For example, in the complete graph K_n on n vertices, \alpha(K_n) = \lfloor n^2 / 4 \rfloor, achieved by partitioning the vertices into two sets of sizes as equal as possible. In contrast, the empty graph with no edges has \alpha(G) = 0.^[1]^[7] This problem is related to the minimum cut, which seeks to minimize the number of crossing edges and is solvable in polynomial time via maximum flow algorithms.^[1] The weighted maximum cut problem extends the unweighted formulation by assigning non-negative weights w_e to each edge e \in E, with the objective to maximize \sum_{e \in \delta(S)} w_e over all subsets S \subseteq V.^[1] This variant arises naturally in applications where edge importance varies, such as network design. For instance, in a complete graph K_n with uniform edge weight w, the maximum weighted cut achieves value \lfloor n^2 w / 4 \rfloor, obtained by partitioning the vertices as evenly as possible. The balanced maximum cut variant imposes the additional constraint that the partition sets S and V \setminus S are of roughly equal size, specifically |S| \approx |V \setminus S| \approx n/2, to ensure equitable division. This modification alters the problem's structure, leading to distinct approximation guarantees; for example, while the standard max-cut admits a 0.878-approximation via semidefinite programming, the balanced version resists similar ratios and remains MAX-SNP-hard even on dense graphs. A further generalization is the k-max-cut problem, which partitions V into k > 2 subsets S_1, \dots, S_k to maximize the total weight of edges with endpoints in different subsets.^[8] This extends max-cut to multiway partitioning, relevant for clustering into more than two groups, and inherits NP-hardness from the k=2 case. Max-cut also relates to correlation clustering, where the two-cluster case reduces to max-cut on a signed graph by treating positive edges as penalties for separation and negative edges as rewards.^[9] The maximum cut problem was first studied by Edwards in 1973, motivated by applications in statistical mechanics.

Mathematical Properties

Bounds

The maximum cut value, denoted \alpha(G) for a graph G with n vertices and m edges, admits a trivial upper bound of \alpha(G) \leq m, as the cut cannot exceed the total number of edges in the graph.^[1] A fundamental lower bound, due to Edwards, applies to connected graphs and states that \alpha(G) \geq m/2 + (n-1)/4.^[10] This result, originally established in 1975, provides a constructive guarantee on the excess over the random cut baseline. A proof sketch relies on a probabilistic partitioning: randomly assign vertices to two sets while adjusting for connectivity, yielding an expected cut size that meets the bound; derandomization via conditional expectations confirms its achievability. This bound is tight for certain extremal graphs, such as complete bipartite graphs with unbalanced parts. It is asymptotically tight, as there exist graphs where the maximum cut size is m/2 + \Theta(\sqrt{m}). The expectation of a random cut, obtained by assigning each vertex independently to one of two sets with equal probability, is E[\alpha] = m/2.^[1] This serves as a baseline for evaluating approximation algorithms, as it matches half the total edges and is achievable in expectation without optimization. Spectral methods yield another upper bound using eigenvalues. For a d-regular graph, where d is the degree, \alpha(G) \leq m \left( \frac{1}{2} + \frac{|\lambda_{\min}|}{2d} \right), with \lambda_{\min} the smallest eigenvalue of the adjacency matrix.^[11] This bound tightens when \lambda_{\min} is close to zero (indicating limited bipartiteness) and reaches m when \lambda_{\min} = -d (as in bipartite graphs). Equivalent formulations arise from the Laplacian matrix in weighted settings, linking to semidefinite relaxations for tighter estimates. These bounds extend naturally to weighted graphs, where edge weights w_e \geq 0 replace unweighted edges, and the total weight W = \sum w_e substitutes for m. The trivial upper bound becomes \alpha(G) \leq W, the random expectation is W/2, and a generalization of Edwards' lower bound is \alpha(G) \geq W/2 + \sqrt{W/8} + O(1).^[10] Spectral bounds similarly replace m with W and incorporate weighted adjacency or Laplacian matrices.^[12]

Computational Complexity

The decision version of the maximum cut problem, which determines whether there exists a partition of the vertices into two sets such that at least k edges cross the partition, is NP-complete. This result follows from a polynomial-time reduction from 3-SAT, as established in the seminal work on simplified NP-complete graph problems, where gadgets are constructed for variables and clauses to ensure that satisfying assignments correspond to large cuts.^[13] The reduction preserves the structure such that a large cut in the resulting graph implies a satisfying assignment for the 3-SAT instance, and vice versa, with the transformation computable in polynomial time. The optimization version of maximum cut, seeking the largest possible cut, is therefore NP-hard. Moreover, it is inapproximable to within a factor of \frac{16}{17} + \epsilon for any \epsilon > 0 unless P = NP, as proven using the Probabilistically Checkable Proof (PCP) theorem and gap-producing reductions from 3-SAT.^[14] This tight inapproximability threshold highlights the inherent difficulty of obtaining guarantees close to the optimal solution in polynomial time. Despite this general hardness, maximum cut is solvable in polynomial time for certain graph classes. In bipartite graphs, every edge crosses the bipartition, yielding a maximum cut of size equal to the number of edges, which can be verified trivially. On trees, dynamic programming can compute the maximum cut in linear time by recursing over subtrees and tracking the contribution of edges based on partition choices at each node. For planar graphs, the problem reduces to finding a maximum-weight matching in an auxiliary graph constructed via the dual, where the matching corresponds to selecting non-adjacent faces to determine the cut edges; this can be solved in polynomial time using known matching algorithms.^[15] In parameterized complexity, maximum cut is fixed-parameter tractable when parameterized by the treewidth of the graph, via standard dynamic programming on a tree decomposition that enumerates partition states across bags. It is also FPT parameterized by the solution size k (the target cut size), admitting a linear kernel of O(k) vertices through reduction rules that prune low-degree vertices and contract high-connectivity components. However, the problem is W^[16]-hard when parameterized by the clique-width of the input graph, indicating intractability for graphs with bounded but non-tree-like structure.^[17]

Algorithms

Exact Algorithms

Exact algorithms for the maximum cut problem exist for several special classes of graphs where the structural properties allow for efficient computation, often leveraging dynamic programming or reductions to other solvable problems. For planar graphs, the problem can be solved in polynomial time by reducing it to a maximum weighted matching problem in a related graph. Specifically, Hadlock showed that the maximum cut in a planar graph corresponds to a minimum odd-vertex pairing in the dual graph, which can be formulated as a T-join problem and solved using matching algorithms in O(n^3) time.^[15] This approach exploits the planarity to construct an auxiliary graph where the matching directly yields the cut partition. Extensions to graphs of bounded genus or excluding fixed minors allow exact solutions in subexponential time using graph minor algorithms. In bipartite graphs, the maximum cut is trivial, as the bipartition of the vertices naturally separates all edges, achieving a cut size equal to the number of edges m. Recognizing whether a graph is bipartite and computing this cut can be done in O(n + m) time using breadth-first search, followed by an O(1) computation of the cut value.^[1] For trees and outerplanar graphs, linear-time dynamic programming algorithms compute the maximum cut by processing the graph from the leaves inward. In a tree, root the graph at an arbitrary vertex and, for each subtree, compute the maximum cut size under two cases: the root vertex is in one side of the partition or the other. The contribution of each edge is added based on whether its endpoints are separated, yielding an overall O(n) time solution. Outerplanar graphs, being a subclass with treewidth at most 2, admit a similar dynamic programming approach along a canonical ordering or dual tree structure, also running in linear time.^[18] Series-parallel graphs, which include trees and outerplanar graphs as subclasses, allow for an O(n) time exact algorithm via recursive decomposition. The graph is broken down into series and parallel compositions, and the maximum cut is computed bottom-up by considering the possible partitions at each composition point and maximizing the crossing edges across substructures. This method relies on the bounded treewidth and the recursive nature of the decomposition tree.^[18] For general graphs, where the problem is NP-hard, exact algorithms rely on exponential-time techniques such as branch-and-bound or meet-in-the-middle approaches. A meet-in-the-middle strategy partitions the vertices into two roughly equal sets of size n/2, enumerates all 2^{n/2} subsets for one set to compute partial cut contributions from edges within and to the other set, and matches them efficiently using sorting or hashing to find the global maximum, achieving O(2^{n/2} n^2) time overall. More advanced branching algorithms can improve the base slightly, but the exponential dependence on n remains fundamental.

Approximation Algorithms

A simple randomized approximation algorithm for the maximum cut problem partitions the vertices into two sets uniformly at random, yielding an expected cut size of m/2, where m is the total edge weight, since each edge crosses the cut with probability $1/2. This achieves a $1/2-approximation in expectation. A deterministic greedy variant sequentially assigns each vertex to the partition that maximizes the incremental cut size, also guaranteeing a $1/2-approximation ratio.^[1]^[19] Local search methods improve upon these baselines by starting from an initial partition and performing vertex swaps or flips that increase the cut size until a local optimum is reached. Trevisan (1997), building on eigenvalue bounds by Poljak and others, demonstrated a 0.531-approximation guarantee for an algorithm using the smallest eigenvalue of the graph Laplacian in conjunction with greedy partitioning. The most influential classical approximation algorithm employs a semidefinite programming (SDP) relaxation, introduced by Goemans and Williamson (1995). The SDP maximizes

\frac{1}{4} \sum_{i \neq j} w_{ij} (1 - \langle v_i, v_j \rangle )

over unit vectors v_i \in \mathbb{R}^n for each vertex i, which relaxes the quadratic integer program for max-cut. The optimal solution is rounded by selecting a random hyperplane and assigning vertices based on the sign of their vector's projection onto a random unit vector, ensuring that the expected cut value satisfies the approximation guarantee. This randomized procedure achieves an approximation ratio of approximately $0.87856, derived from the integral of the arccosine function over the unit circle, which bounds the probability that an edge is cut relative to the SDP value. The algorithm can be derandomized using conditional expectations while preserving the ratio.^[1] Inapproximability results establish that it is NP-hard to approximate Max-Cut within a factor better than $16/17 \approx 0.941. Håstad (2001) provided optimal inapproximability thresholds up to additive factors for max-cut via PCP reductions from 3-SAT. Subsequent refinements by Khot, Kindler, Mossel, and O'Donnell (2004) showed that, assuming the Unique Games Conjecture, no algorithm can exceed the Goemans-Williamson ratio of ≈0.878 by any constant factor.^[14]^[20] Recent classical advances leverage graph structure for slight improvements beyond the Goemans-Williamson bound. For instance, when the input graph contains \Omega(|E|) triangles, the standard max-cut SDP rounded via the hyperplane method achieves an approximation ratio of \alpha_{GW} + \Omega(1), as shown by analyzing correlations induced by triangles in the vector representation (George and Louis, 2025).^[21]

Parameterized and Quantum Algorithms

The parameterized complexity of the maximum cut problem has been extensively studied, particularly with respect to structural parameters like treewidth and solution excess parameters. When parameterized by treewidth tw, maximum cut admits a fixed-parameter tractable (FPT) algorithm via dynamic programming on a tree decomposition. The approach maintains states representing the partition of each bag into the two sides of the cut, leading to a running time of O(2^{tw} \cdot tw \cdot n), where n is the number of vertices, by enumerating subsets of the bag and computing contributions from edges within and between bags.^[17] This exploits the tree decomposition to localize computations, ensuring exponential dependence only on tw. Kernelization techniques further enhance preprocessing for parameters related to the solution quality. For the parameter k defined as the excess of the maximum cut size over the trivial lower bound of m/2 (where m is the number of edges), reduction rules reduce the instance to a kernel of quadratic size, specifically O(k^2) vertices. These rules, developed in the 2010s, include vertex folding for induced paths and handling high-degree vertices by merging or removing them while adjusting the parameter to preserve equivalence; for instance, folding a degree-2 vertex connects its neighbors with an edge of summed weights, reducing intra-component edges without altering the optimal cut value. Such kernels enable efficient solving on the reduced instance via branching or DP.^[22] More recent refinements achieve linear kernels of O(k) vertices above the Edwards-Erdős bound, using additional rules like clique reductions and block mergers.^[23] Quantum algorithms offer promising avenues for maximum cut, leveraging superposition and entanglement for potentially superior approximations. The Quantum Approximate Optimization Algorithm (QAOA), introduced in 2014, applies alternating layers of mixing and cost Hamiltonians tailored to the max-cut objective, where the cost Hamiltonian encodes edge penalties for same-side vertices. For p-layer QAOA, variational optimization of parameters yields cuts outperforming the classical random 0.5-approximation on small instances (up to 20 qubits), with empirical ratios approaching 0.8 for p=1 and higher for larger p, with a worst-case guarantee of approximately 0.692 for p=1 on regular graphs, improving for higher p, though no quantum algorithm provably exceeds the classical Goemans-Williamson ratio in the worst case. Recent advances explore specialized quantum circuits for efficiency on near-term devices. In 2024, low-depth Clifford circuits, which use only Clifford gates (implementable with low overhead), were shown to approximately solve max-cut with approximation ratios exceeding 0.89 on weighted complete graphs via adaptive construction, surpassing the classical Goemans-Williamson 0.878 ratio in specific cases while maintaining depth linear in n.^[24] By 2025, edge-based QAOA variants encode the problem using edge states rather than vertex spins, using approximately n qubits and improving performance on sparse graphs through localized mixing operators. Despite these developments, no proven quantum speedup over classical approximations exists for max-cut, as QAOA's worst-case ratios match or lag semidefinite programming bounds; however, hybrid quantum-classical solvers, integrating QAOA with local search, demonstrate practical gains on NISQ hardware for instances up to 100 qubits.^[25] In the streaming model, where edges arrive sequentially with limited memory, quantum algorithms provide space advantages for approximating directed maximum cut. A 2024 quantum streaming algorithm achieves a 0.4844-approximation using \mathrm{polylog}(n) qubits, exponentially less space than classical algorithms requiring \Omega(\sqrt{n}) bits for similar ratios, by employing quantum fingerprinting to estimate cut values across passes. This highlights quantum benefits in data-intensive settings, though it applies to the directed variant.^[26]

Applications

Machine Learning

In machine learning, the maximum cut problem serves as a quadratic unconstrained binary optimization (QUBO) formulation for binary classification tasks, where data points are represented as vertices in a graph, and edges encode pairwise similarities or disagreements; the goal is to partition the vertices into two sets that maximizes the weight of edges crossing the cut, thereby separating dissimilar points. This approach models unsupervised partitioning by assigning binary labels to maximize inter-class disagreements, with the QUBO objective x^T Q x minimized over binary vectors x \in \{0,1\}^n, where Q is derived from a similarity matrix. Correlation clustering leverages maximum cut to minimize intra-cluster disagreements on similarity graphs, where positive edge weights indicate similarity (favoring same-cluster assignment) and negative weights indicate dissimilarity (favoring different clusters); for two clusters, this reduces to solving max-cut on a transformed graph to maximize the cut value corresponding to inter-cluster edges.^[27] Approximations are achieved via a semidefinite programming (SDP) relaxation similar to Goemans-Williamson, yielding guarantees on cluster quality.^[1] In community detection, maximum cut maximizes modularity in social networks by partitioning graphs to optimize the difference between intra-community edges and expected random connections, particularly effective in stochastic block models (SBMs) where ground-truth communities generate denser intra-block edges.^[28] SDP-based max-cut solvers approximate optimal partitions in SBMs by relaxing the modularity objective to a vector program, recursively splitting communities via hyperplane rounding to recover dense blocks with high fidelity.^[28] Post-2020 applications integrate max-cut SDP relaxations into graph neural networks (GNNs) for embedding learning, where low-rank SDP solvers optimize node embeddings on hyperspheres to capture cut-maximizing structures, enabling scalable inference in tasks like multi-class Markov random fields. These methods, such as the mixing algorithm for diagonally constrained SDPs, facilitate differentiable training of GNNs by providing convex relaxations that converge globally for rank exceeding \sqrt{2n}, outperforming spectral methods in embedding quality for community-structured graphs.^[29] Empirically, the 0.878-approximation from Goemans-Williamson suffices for large-scale clustering in SBM datasets, achieving near-optimal recovery of ground-truth partitions when intra-block densities exceed inter-block by a constant factor, as demonstrated on benchmarks with up to millions of nodes.

Theoretical Physics

The maximum cut problem finds a natural interpretation in statistical mechanics through its equivalence to the ground state of the classical Ising model. In this mapping, each vertex of the graph corresponds to a spin variable \sigma_i = \pm 1, and the ferromagnetic Ising Hamiltonian is given by H = -\sum_{(i,j) \in E} \sigma_i \sigma_j, where the sum is over the edges of the graph. Minimizing the energy H is equivalent to maximizing the cut size, as the number of edges crossing the cut equals \frac{|E| - H}{2}. This correspondence highlights how finding an optimal partition in a graph mirrors the alignment of spins to minimize interaction energy in a physical system. In spin glass models, which introduce frustration through random or antiferromagnetic interactions, the maximum cut problem plays a central role in analyzing disordered systems. The Sherrington-Kirkpatrick (SK) model, a mean-field spin glass with fully connected spins and Gaussian-distributed couplings, relates its ground state energy minimization to the maximum cut on a complete graph with random edge weights; the optimal cut fraction provides insights into the low-temperature phase structure. Phase transitions in these models, such as the spin glass transition, are probed through the distribution of cut sizes in random graphs, revealing critical behaviors like the onset of frustration where large cuts correspond to broken ergodicity. Replica symmetry breaking (RSB) in the SK model further connects to the inherent hardness of approximating maximum cut, as the rugged energy landscape with multiple metastable states mirrors the computational challenges in finding global optima. Quantum extensions of these models leverage maximum cut to study quantum phase transitions. Quantum annealing, as implemented on D-Wave systems, formulates maximum cut instances as quadratic unconstrained binary optimization (QUBO) problems equivalent to the Ising Hamiltonian, with experimental benchmarks on random graphs demonstrating scaling behaviors up to thousands of qubits, though limited by embedding overhead and noise. More recently, the quantum approximate optimization algorithm (QAOA) simulates the transverse-field Ising model for maximum cut, where the cost Hamiltonian encodes the classical cut and the mixer introduces quantum fluctuations; this approach ties into 2023–2025 advances in variational quantum algorithms, including symmetry-based expressive QAOA and edge-based variants offering improved approximation ratios on dense graphs and NISQ devices, providing a physics-inspired framework to explore quantum critical points and entanglement in frustrated systems.^[30]^[31]^[32]

VLSI and Network Design

In very large scale integration (VLSI) design, the maximum cut problem aids in optimizing circuit layouts by partitioning components to reduce wire lengths and enhance routing efficiency. Specifically, it is applied in via minimization for two-layer channel routing, where the task of assigning net segments to metal layers is modeled as finding a maximum cut in a derived planar graph; edges in the cut represent vias needed to connect segments across layers, and maximizing the cut minimizes the total vias required. Since maximum cut on planar graphs is solvable in polynomial time using matching algorithms, this approach enables efficient exact solutions for practical routing instances. Additionally, the size of the maximum cut provides a theoretical lower bound on the minimum area of a VLSI layout for a given graph, as the layout area must accommodate at least the squared value of the maximum cut size divided by the number of I/O pins, establishing fundamental limits on chip density.^[33] In telecommunications and network design, maximum cut facilitates graph partitioning to balance loads across subnetworks while maximizing the weight of edges crossing partitions, which corresponds to inter-switch traffic and improves overall throughput and resilience. This is particularly useful in large-scale communication networks, where approximation algorithms like the semidefinite programming relaxation achieve a 0.878 approximation ratio and are integrated into partitioning frameworks to handle real-world topologies. For instance, in multi-radio wireless mesh networks, maximum cut-based methods assign overlapping channels to interfaces, maximizing the cut to minimize interference and boost concurrent transmissions.^[34] Weighted variants of maximum cut are employed in computer vision for image segmentation, where pixels are modeled as vertices in a graph with edge weights reflecting similarity (e.g., color differences); the maximum cut partitions pixels into foreground and background sets to maximize the total weight of dissimilar edges across the boundary, yielding smooth segmentations. This approach extends to more complex scenes by incorporating Gaussian mixture models for pixel affinities, enabling robust handling of occlusions and shadows. In wireless ad-hoc networks, maximum cut optimizes channel allocation by partitioning nodes into sets assigned to different channels, maximizing the cut to ensure the highest number of interference-free links across channels and thus improving spatial reuse and throughput. Algorithms solving this NP-hard problem via heuristics or quantum-inspired methods have demonstrated gains in link utilization over greedy allocations in dense topologies.^[34] Beyond engineering, maximum cut analogies appear in business applications such as finance and logistics. In portfolio optimization, the problem models asset partitioning into inclusion/exclusion sets to maximize a quadratic objective akin to cut weight, capturing diversification benefits under transaction costs; quantum annealing solvers applied to these formulations have shown promise in scaling to hundreds of assets.^[35] Similarly, in logistics, maximum cut supports facility location partitioning by dividing customer demand graphs to maximize serviced inter-region flows, aiding efficient supply allocation. Recent advancements leverage maximum cut in supply chain models, where graph partitions identify robust supplier clusters under disruptions.^[36]

References

[1]
[PDF] Improved approximation algorithms for maximum cut and ...
We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions ...
[2]
[PDF] Reducibility Among Combinatorial Problems
This paper shows that many classic combinatorial problems are equivalent, meaning either they all have polynomial-bounded algorithms or none do. A polynomial- ...
[3]
[PDF] 2.1 The Max-Cut Problem
The Max-Cut problem is to find a cut (S, S) in a graph that maximizes the number of edges crossing between S and S.
[4]
[PDF] 7.1 Local Search 7.2 Max-Cut - cs.wisc.edu
Local search iteratively moves solutions by small changes. Max-Cut finds a cut with maximum value in a graph, and is NP-hard.
[5]
Maximum cut and related problems
In this lecture, we will discuss three fundamental NP-hard optimization problems that turn out to be intimately related to each other.
[6]
[PDF] Four Problems in Probability and Optimization - University of ...
A max cut is a cut maximizing |S|. In the complete graph Kn, the max cuts come from any partition of [n] into two sets of n/2 vertices, or (n ± 1)/2 when n is ...
[7]
[PDF] Improved Approximation Algorithms for MAX k-CUT and ... - CMU Math
In this paper we do so in two ways. First we consider. MAX k-CUT where the aim is to partition V into k subsets: for a partition. P = P1,P2 ...,Pℓ of V we let |P ...
[8]
[PDF] Lecture 8: Approximating Min UnCut and Min-2CNF Deletion
Remark 1 The Min UnCut problem is a complement to the MaxCut problem: The sum of the number of cut edges and uncut edges is equal to the total number of edges ...
[9]
[PDF] Correlation Clustering: Maximizing Agreements via Semidefinite ...
correlation clustering to maximize agreements. Each edge e has two weights ... MAX CUT by choosing multiple hyperplanes. Let. {xv ∈ Rn} be the optimal ...
[10]
Finding community structure in networks using the eigenvectors of ...
Indeed, the problem of modularity optimization is formally equivalent to an instance of the NP-hard MAX-CUT problem, so it is almost certainly the case that no ...
[11]
[PDF] Better Bounds for Max Cut - People
The paper determines f(m) and fw(m) for Max Cut, finding algorithms for large bipartite subgraphs, and generalizes to Max k-Cut and Max Directed Cut.Missing: K_n | Show results with:K_n
[12]
[PDF] Max Cut and the Smallest Eigenvalue∗ - Stanford CS Theory
(Equivalently, we count the number of cut edges minus the number of uncut edges.) For Max. CutGain we develop a more sophisticated spectral partition- ing ...Missing: complement | Show results with:complement
[13]
[2104.05536] Lower Bounds for Maximum Weighted Cut - arXiv
Apr 12, 2021 · In this paper, we launch an extensive study of lower bounds for Max Cut in weighted graphs. We introduce a new approach for obtaining lower bounds for Weighted ...
[14]
Some simplified NP-complete graph problems - ScienceDirect.com
First we show the completeness of Simple Max Cut (Max Cut with edge weights restricted to value 1), and, as a corollary, the completeness of the Optimal Linear ...
[15]
Some optimal inapproximability results | Journal of the ACM
We prove optimal, up to an arbitrary ε > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations.
[16]
Finding a Maximum Cut of a Planar Graph in Polynomial Time
The paper shows that finding a maximum cut of a planar graph can be translated into a maximum weighted matching problem, which has a polynomial bounded ...
[17]
[PDF] Parameterized Algorithms for Maximum Cut with Connectivity ... - arXiv
Aug 9, 2019 · Our algorithm is based on standard dynamic programming on a tree decomposition. This algorithm outputs a maximum minimal cut (S1,S2).
[18]
Linear-time computability of combinatorial problems on series ...
It is well known that series-parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series-parallel graph ...
[19]
[PDF] Yet Another Algorithm for Dense Max Cut: Go Greedy - Brown CS
The greedy algorithm for MaxCut places vertices one by one on the side maximizing crossing edges, based on neighbors already placed.<|control11|><|separator|>
[20]
Optimal Inapproximability Results for MAX‐CUT and Other 2 ...
... k ) -Max-Cut: An O ∗ ⁡ ( 2 p ) O ∗ ( 2 p ) -Time Algorithm and a ... We study the AprxColoring ( q , Q ) problem: Given a graph G, decide whether ...
[21]
Triangles Improve 0.878 Approximation for Maxcut - DROPS
Sep 15, 2025 · We revisit the Goemans–Williamson SDP and prove that the standard Maxcut SDP achieves a (α_{GW} + Ω(1))-approximation whenever the input graph ...
[22]
[PDF] Engineering Kernelization for Maximum Cut - EPrints
May 26, 2019 · Our experiments show that this can reduce the kernel size significantly. This is noteworthy, given that existing solvers for Max. Cut usually ...
[23]
Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
Oct 25, 2017 · The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were ...
[24]
[2310.15022] Low-depth Clifford circuits approximately solve MaxCut
Oct 23, 2023 · Our algorithm finds an approximate solution of MaxCut on an N-vertex graph by building a depth O(N) Clifford circuit. The algorithm has runtime ...Missing: 0.75 | Show results with:0.75
[25]
Edge-based quantum approximate optimization algorithm for MAX ...
Sep 23, 2025 · In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well- ...
[26]
Exponential Quantum Space Advantage for Approximating ... - arXiv
Nov 23, 2023 · Our quantum streaming algorithm 0.4844-approximates the value of the largest directed cut in a graph stream with n vertices using polylog(n) space.
[27]
[PDF] Semidefinite Program- ming: Max-Cut
Problem: Max Correlation Clustering: Have input in which each pair of objects dis- plays a degree of similarity or dissimilarity, want to cluster similar ...
[28]
[PDF] Modularity-Maximizing Graph Communities via Mathematical ...
algorithms for modularity maximization as well. Unfortu- nately, the shift ... [25] for the Max-Cut problem. In the Max-Cut problem, an undirected ...
[29]
[PDF] Learning and Reasoning with Fast Semidefinite Programming and ...
Abstract. Semidefinite programming has long been a theoretically powerful tool for solving relaxations of challenging, often NP-hard optimization problems.
[30]
Experimental investigation of performance differences between ...
The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on cubic graphs. ... 4 Time to solution for D-Wave and CIM at optimal annealing time dense MAX-CUT ...
[31]
[PDF] min cut and max cut
Nov 17, 2015 · max cut has applications in circuit layout. – The minimum area of a VLSI layout of a graph is not less than the square of its maximum cut size.
[32]
Max-Cut based overlapping channel assignment for 802.11 multi ...
The results show that the Max-Cut based overlapping channel assignment algorithm effectively and efficiently improves on the network capacity compared with ...
[33]
[PDF] Quantumized Graph Cuts in Portfolio Construction and Asset Selection
using the quantum computing variant of the Max-Cut algorithm. Following ... to the portfolio optimization algorithm. This is typically done as either a ...
[34]
[PDF] arXiv:2207.08189v2 [cond-mat.dis-nn] 26 Oct 2023
Oct 26, 2023 · limitation to supply chain, energy, and transportation. Providing ... (Max-Cut), the nurse scheduling problem (NSP), and the traveling ...