Abstrakt. Vi anser att problemet med att hitta en lokal optimal för Max-Cut med FLIP-grannskap, där exakt en nod ändrar partitionen. Schäffer och Yannakakis (SICOMP, 1991) visade PLSfullständighet av detta problem på grafer med obegränsad grad. Å andra sidan, Poljak (SICOMP, 1995) visade att i kubikdiagram varje FLIP lokal sökning tar O(n 2 ) steg, där n är antalet noder. På grund av den enorma klyftan mellan grad tre och obegränsad grad, Ackermann, Röglin, och Vöcking (JACM, 2008) bad om den minsta d  på N för vilken lokala Max-Cut problem med FLIP-grannskap på grafer med maximal grad d är PLS-komplett. I detta dokument visar vi att beräkningen av en lokal optimal på grafer med maximal grad fem är PLS-fullständig. På så sätt löser vi problemet med Ackermann m.fl. nästan helt genom att visa att d är antingen fyra eller fem (om inte PLS P). På andra sidan, Vi bevisar också att på grafer med grad O(log n) varje FLIP lokal sökning har förmodligen polynom utjämnad komplexitet. Ungefärligt, för alla fall, där kant vikter är perturbated av en (Gaussian) slumpmässiga buller med varians σ 2, varje FLIP lokal sökning slutar med tiden polynom i n och σ −1, med sannolikhet 1 − n −.(1). Att sätta båda resultaten tillsammans, kan vi dra slutsatsen att även om lokala Max-Cut är sannolikt att vara svårt på grafer med begränsad grad, kan det lösas i polynom tid för något perturberade fall med hög sannolikhet.
Elässer och Tscheuschner REF visade att om kantvikterna är perturbed med Gaussian brus i grafer med maximal grad O(log n), då komplexiteten i FLIP-metoden är polynom.
Settling the complexity of local max-cut (almost) completely
{'venue': None, 'journal': 'arXiv: Computational Complexity', 'mag_field_of_study': ['Mathematics', 'Computer Science']}