Maximum weakly stable matchings in graphs without odd preference cycles
Let (G,<) be a preference system with ties where in every odd cycle there is a node that prefers its clockwise neighbour to its other neighbour, and there is another node that prefers its anti-clockwise neighbour to its other neighbour. How well can we approximate the maximum size weakly stable matching?
Clearly, the maximum stable marriage problem is a special case, for which the best known approximation ratio is 3/2 by McDermid . On the other hand, the preference system is guaranteed to have a weakly stable matching since there are no odd preference cycles, and, as Irving and Manlove  showed, the size of the maximum weakly stable matching is at most twice the size of the minimum weakly stable matching, which immediately gives a 2-approximation algorithm (find a stable matching for an arbitrary break of ties).
- E. McDermid, A 3/2-Approximation Algorithm for General Stable Marriage, Proc. ICALP2009, Lecture Notes in Computer Science 5555 (2009), 689-700. DOI link. Author link.
- R. W. Irving, D. F. Manlove, The stable roommates problem with ties, Journal of Algorithms 43 (2002), 85-105. DOI link. Author link.