Are stable instances easy? (Q2911066)

In this paper, the authors start from the following remark: proving that a problem is NP-hard means that there exists at least one ``hard'' instance. However, this hard instance (often obtained via reduction from another NP-hard problem) may be artifical, and not correspond to ``real life instances'', which may be solvable in polynomial time. This paper lies on the previous remark, and focuses on a particular problem, namely MAX-CUT (on an edge-weighted graph \(G\)). The authors define a notion of stability (basically, an instance of MAX-CUT is \(\gamma\)-stable if multiplying each weight by a factor between 1 and \(\gamma\) does not modify the optimal solution), and prove that MAX-CUT is polynomially solvable for \(\gamma\)-stable instances if \(\gamma\) is sufficiently large compared to (a) a certain function of \(\Delta\) and \(n\) (Theorem 3.1), or (b) a certain function of \(\delta\) and \(n\) (Theorem 3.2), where \(\Delta\) (resp. \(\delta\)) is the maximum (resp. minimum) degree of \(G\), and \(n\) is its number of vertices. Some more additional results are given in the following sections, which concern spectral conditions on \(G\) and the Goemans-Willimason algorithm for MAX-CUT.NEWLINENEWLINEAlthough the title and introduction suggest a very general (and promising) study, the contents of the paper are rather disappointing in this respect, since it focuses on a special problem (MAX-CUT), in the case where there is a unique optimal solution, and the positive results are very restricted (\(\gamma\) has to be very large, and one might wonder whether \(\gamma\)-stability is really interesting in that case). However, the results are fairly interesting, and the notion of stability seems quite original, although the paper is somewhat `oversold' in its introduction.