Maximum weakly stable matchings in graphs without odd preference cycles

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph. Each vertex has a complete weak order on its neighbors, permitting ties; every listed neighbor is preferred to remaining unmatched. Write $u\succ_v w$ when $v$ strictly prefers $u$ to $w$.

For each odd simple cycle $v_0v_1\cdots v_{2r}v_0$, with indices read cyclically, assume that some vertex strictly prefers its successor to its predecessor and another strictly prefers its predecessor to its successor. Ties alone do not witness either requirement.

A matching $M$ is weakly stable if there is no edge $uv\notin M$ such that both endpoints strictly prefer one another to their partners in $M$, with an unmatched endpoint treating any neighbor as preferable. Let \[ \operatorname{OPT}(G,\succ)=\max\{|M|:M\text{ is weakly stable}\}. \] The cycle hypothesis guarantees existence of a weakly stable matching. Determine how well this maximum can be approximated in polynomial time. An approximation factor $\alpha\ge1$ means an algorithm always produces a weakly stable $M$ with $|M|\ge\operatorname{OPT}/\alpha$.

Seek the best factor for this whole class and, separately, its dependence on a bound on the size of ties in individual lists. The graph need not be bipartite. Ignoring ties or replacing weak stability by strong or super-stability changes the feasible set. In particular, producing a stable matching of arbitrary size does not settle the maximum-size approximation question.

Short English statement

How closely can polynomial-time algorithms approximate the largest weakly stable matching under the stated prohibition on odd preference cycles?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000052 (AMR-029-0052), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Maximum weakly stable matchings in graphs without odd preference cycles. Original source indexed by AMR-029-0052. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Maximum weakly stable matchings in graphs without odd preference cycles. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Maximum_weakly_stable_matchings_in_graphs_without_odd_preference_cycles.