Back to search

Cornell University

On Graph Coloring, Max Cut, and Semidefinite Rank

Abstract

dc:description.abstract

In this thesis, we will focus on two of Karp's original NP-complete problems, graph coloring and max cut, both of which have established semidefinite programming relaxations. We introduce the use of semidefinite programming complementary slackness conditions to understand when an optimal solution to one of these SDP relaxations can be guaranteed to take the form of an optimal solution to the original problem. First, we consider the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a $k$-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if a graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. We then modify the semidefinite program to have an objective function with costs, and explore when we can create an objective function such that the optimal dual solution has sufficiently high rank. We show that it is always possible to construct such an objective function given the graph coloring. The construction of the objective function gives rise to heuristics for 4-coloring planar graphs which we also present. We enumerated all maximal planar graphs with an induced K4 of up to 14 vertices; the heuristics successfully found a 4-coloring for 99.75\% of them. Then we switch settings to max cut. We investigate when the rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank $n -1$. We show in the case of connected bipartite graphs that they have sufficiently high dual rank. Analogously to graph coloring, we also show that if the max cut of a graph is not unique, then there cannot exist an optimal dual solution of sufficiently high rank. We conclude with a theorem and corresponding conjecture for general graphs. Finally, we switch to an experimental perspective and evaluate the performance of several max cut approximation algorithms. In particular, we compare the results of the Goemans and Williamson algorithm using semidefinite programming with Trevisan's algorithm using spectral partitioning. The former algorithm has a known .878 approximation guarantee whereas the latter has a .614 approximation guarantee. We investigate whether this gap in approximation guarantees is evident in practice or whether the spectral algorithm performs as well as the SDP. We also compare the performances to the standard greedy max cut algorithm which has a .5 approximation guarantee, two additional spectral algorithms, and a heuristic from Burer, Monteiro, and Zhang. The algorithms are tested on Erd\H{o}s-Renyi random graphs, complete graphs from TSPLIB, and real-world graphs from the Network Repository. We find, unsurprisingly, that the spectral algorithms provide a significant speed advantage over the SDP. In our experiments, the spectral algorithms and BMZ heuristic return cuts with values which are competitive with those of the SDP.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mirka, Renee
Chair dc:contributor.chair
  • Williamson, David
Committee members dc:contributor.committeemember
  • Banerjee, Siddhartha
  • Gomes, Carla

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16575451
Dc Identifier Other
ProQuest Submission ID: 14220
ProQuest Publication ID: 31239159

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Mirka, Renee. On Graph Coloring, Max Cut, and Semidefinite Rank. Doctor of Philosophy thesis, Cornell University, 2024. https://hdl.handle.net/1813/115968