Smoothed Complexity of SWAP in Local Graph Partitioning

2023/05/25 by Chen, Xi, Guo, Chenghao, Vlatakis-Gkaragkounis, Emmanouil-Vasileios +1 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2305.15804

Abstract

We give the first quasipolynomial upper bound ϕn^polylog(n) for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width), where n is the number of nodes in the graph and ϕ is a parameter that measures the magnitude of perturbations applied on its edge weights. More generally, we show that the same quasipolynomial upper bound holds for the smoothed complexity of the 2-FLIP algorithm for any binary Maximum Constraint Satisfaction Problem, including local Max-Cut, for which similar bounds were only known for 1-FLIP. Our results are based on an analysis of cycles formed in long sequences of double flips, showing that it is unlikely for every move in a long sequence to incur a positive but small improvement in the cut weight.

Cited by

• Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Related

• Smoothed complexity of local Max-Cut and binary Max-CSP
• Improving the smoothed complexity of FLIP for max cut problems
• Local Max-Cut on Sparse Graphs
• Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
• Settling the complexity of local max-cut (almost) completely