On exactness of SDP relaxation for the maximum cut problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911426353823744 |
|---|---|
| author | Bhardwaj, Avinash Gogoi, Hritiz Narayanan, Vishnu Pathapati, Abhishek |
| author_facet | Bhardwaj, Avinash Gogoi, Hritiz Narayanan, Vishnu Pathapati, Abhishek |
| contents | Semidefinite programming (SDP) provides a powerful relaxation for the maximum cut problem. For a graph with rational weights, the decision problem of whether the SDP relaxation for the maximum cut problem is exact is known to be $NP$-hard; however its complexity was unresolved for unweighted graphs. In this work, we extend the $NP$-hardness result to unweighted graphs. We characterize a few classes of graphs for which the SDP relaxation is exact. For each of these graph classes, we establish conditions for uniqueness of the SDP optimum. We complement these findings by identifying two graph operations that preserve the solution rank, and in turn exactness. These results reveal how the SDP relaxation for the maximum cut problem can remain exact in arbitrarily large graphs, owing to the presence of a small structural core that governs exactness. We further address two open problems posed by Mirka and Williamson (2024), by demonstrating that uniqueness of the maximum cut partition in exact relaxation does not imply uniqueness of the SDP optimum, and that exact relaxation with multiple optimal partitions may admit optimal SDP solutions lying outside the convex hull of rank-1 reference solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05200 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On exactness of SDP relaxation for the maximum cut problem Bhardwaj, Avinash Gogoi, Hritiz Narayanan, Vishnu Pathapati, Abhishek Optimization and Control 90C27, 90C22, 90C35 Semidefinite programming (SDP) provides a powerful relaxation for the maximum cut problem. For a graph with rational weights, the decision problem of whether the SDP relaxation for the maximum cut problem is exact is known to be $NP$-hard; however its complexity was unresolved for unweighted graphs. In this work, we extend the $NP$-hardness result to unweighted graphs. We characterize a few classes of graphs for which the SDP relaxation is exact. For each of these graph classes, we establish conditions for uniqueness of the SDP optimum. We complement these findings by identifying two graph operations that preserve the solution rank, and in turn exactness. These results reveal how the SDP relaxation for the maximum cut problem can remain exact in arbitrarily large graphs, owing to the presence of a small structural core that governs exactness. We further address two open problems posed by Mirka and Williamson (2024), by demonstrating that uniqueness of the maximum cut partition in exact relaxation does not imply uniqueness of the SDP optimum, and that exact relaxation with multiple optimal partitions may admit optimal SDP solutions lying outside the convex hull of rank-1 reference solutions. |
| title | On exactness of SDP relaxation for the maximum cut problem |
| topic | Optimization and Control 90C27, 90C22, 90C35 |
| url | https://arxiv.org/abs/2505.05200 |