# 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?

## Remarks

Clearly, the maximum stable marriage problem is a special case, for which the best known approximation ratio is 3/2 by McDermid ^{[1]}. 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 ^{[2]} 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).

## References

- ↑ 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.