pith. sign in

arxiv: 1907.10458 · v1 · pith:IWA7JJQKnew · submitted 2019-07-24 · 💻 cs.DM

The stable marriage problem with ties and restricted edges

\'Agnes Cseh , Klaus Heeger This is my paper

Pith reviewed 2026-05-24 16:29 UTC · model grok-4.3

classification 💻 cs.DM
keywords stable marriage problemties in preferencesrestricted pairsweak stabilitystrong stabilitysuper-stabilitycomputational complexityNP-completeness
0
0 comments X

The pith

The stable marriage problem with ties and restricted edges has all its open existence cases resolved.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper completes the computational complexity analysis of finding stable matchings when preferences have ties and some pairs are designated as forced to be included, forbidden from inclusion, or free to not block. It addresses the three stability concepts—weak, strong, and super-stability—paired with each of the three restriction types. Previously open cases are settled either by polynomial algorithms or by NP-completeness proofs. The work also establishes NP-hardness for the maximum size weakly stable matching problem in dense graphs.

Core claim

For every combination of a stability notion and a restriction type on pairs, the problem of deciding whether a stable matching exists is either solvable in polynomial time or NP-complete, and all such cases that remained open are now classified accordingly.

What carries the argument

The nine combinations of weak/strong/super-stability with forced/forbidden/free pairs, each analyzed for existence via algorithms or hardness reductions.

If this is right

  • The existence question is settled for all variants.
  • Polynomial-time solvable cases admit efficient algorithms.
  • NP-complete cases indicate no efficient algorithm exists unless P=NP.
  • The maximum weakly stable matching remains hard even when the graph is dense.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Practitioners can now select stability notions based on whether efficient computation is possible for their instance type.
  • The density hardness result suggests that even complete preference lists do not make the problem easy.
  • Future work could explore approximation algorithms for the hard cases or extensions to other matching problems.

Load-bearing premise

The paper assumes that earlier works correctly identified which cases were still open and uses the standard definitions of the stability notions and pair restrictions.

What would settle it

Finding an instance that contradicts one of the polynomial-time claims by being hard, or disproving a hardness reduction by showing a poly-time solution for a claimed NP-complete case.

Figures

Figures reproduced from arXiv: 1907.10458 by \'Agnes Cseh, Klaus Heeger.

Figure 1
Figure 1. Figure 1 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 1
Figure 1. Figure 1: An example for the reduction. The legend on the right side lists the five groups of edges in the preference order at all vertices. The edges from the perfect-smti instance (drawn in solid black) keep their ranks. Every vertex ranks solid black edges best, then loosely dashed green edges, then densely dashed blue edges, then dotted red edges, then the wavy gray edge {u1, w1} and the forbidden violet zigzag … view at source ↗
Figure 2
Figure 2. Figure 2: While vertices ai and bi do not have any further edge, ci will be incident to three interconnecting edges leading to variable gadgets. Vertex bi is ranked first by ai and last by ci , and these two vertices are placed in a tie by bi . For each variable xi , occurring in the three clauses Ci1 , Ci2 , and Ci3 , we add a variable gadget with nine vertices y j i , z j i , and w j i for j ∈ [3], as indicated in… view at source ↗
Figure 2
Figure 2. Figure 2: An example of a clause gadget for the clause Ci, containing the variables x1, x4, and x5. The interconnecting edges are dashed and gray. following. At the top are all vertices of the form {z j i } in a single tie, followed by all vertices of the form {w j i } in a single tie, and finally, all other vertices ({bi}) at the bottom of the preference list. Claim: I is a YES-instance if and only if I ′ admits a … view at source ↗
Figure 3
Figure 3. Figure 3: An example of a variable gadget for the variable xi occurring, where xi occurs exactly in the clauses C1, C3, and C5. Free edges are marked by wavy lines, while interconnecting edges are dashed and gray. This proof aimed at the hardness of the restricted case, in which the under￾lying graph has a low maximum degree. For the sake of completeness, we add another variant, which is defined in a complete bipart… view at source ↗
read the original abstract

In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching. Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies the existence question for stable matchings in the stable marriage problem with ties, under the three standard stability notions (weak, strong, super-stability) and the three standard edge-restriction types (forced, forbidden, free pairs). It supplies explicit polynomial-time algorithms or NP-hardness proofs for every cell of the resulting 3×3 classification grid, thereby closing all previously open cases, and derives as a byproduct that maximum-cardinality weakly stable matching remains NP-hard even on dense instances.

Significance. A complete, explicit complexity map for these nine combinations is a useful consolidation of the literature on stable matchings with ties and side constraints. The byproduct hardness result for dense weakly-stable matchings is of independent interest because most prior hardness constructions for weak stability rely on sparse preference graphs.

minor comments (2)
  1. Abstract: the phrase 'very dense graphs' is left informal; a precise statement of the density parameter (e.g., minimum degree or number of acceptable pairs) would help readers locate the result.
  2. The manuscript should explicitly list, in the introduction or a table, which of the nine cells were already settled in the cited literature and which are new, so that the 'all open cases solved' claim can be verified at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, for the positive summary of our contributions, and for the recommendation to accept. We are glad that the complete resolution of the 3×3 complexity grid and the independent interest of the dense-graph hardness result for maximum weakly stable matchings were appreciated.

Circularity Check

0 steps flagged

No significant circularity; case analysis is self-contained via reductions

full rationale

The manuscript classifies all 3×3 combinations of stability notions (weak/strong/super) and edge restrictions (forced/forbidden/free) by supplying explicit algorithms or NP-hardness reductions for each cell. These reductions invoke only the standard definitions of stability and restricted pairs as given in the prior literature; no parameter is fitted to data, no quantity is renamed as a prediction, and no load-bearing uniqueness theorem is imported from the authors' own prior work. The byproduct hardness result for dense weakly-stable matchings is likewise obtained by direct reduction. Because every claimed result is externally falsifiable via the cited complexity problems and does not reduce to a self-definition or self-citation chain, the derivation chain contains no circular step.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of stability notions and edge restrictions taken from prior literature; no new free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (1)
  • domain assumption Standard definitions of weak, strong, and super-stability together with forced, forbidden, and free pairs as established in the cited literature.
    The nine-case classification table is defined using these pre-existing notions without re-derivation.

pith-pipeline@v0.9.0 · 5716 in / 1149 out tokens · 32909 ms · 2026-05-24T16:29:01.588574+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Askalidis, N

    G. Askalidis, N. Immorlica, A. Kwanashie, D. F. Manlove, and E. Pou n- tourakis. Socially stable matchings in the Hospitals / Residents proble m. In F. Dehne, R. Solis-Oba, and J.-R. Sack, editors, Algorithms and Data Structures, volume 8037 of Lecture Notes in Computer Science , pages 85–96. Springer Berlin Heidelberg, 2013

    work page 2013

  2. [2]

    P. Bir´ o. Applications of matching models under preferences. Trends in Computational Social Choice , page 345, 2017

    work page 2017

  3. [3]

    Cechl´ arov´ a and T

    K. Cechl´ arov´ a and T. Fleiner. Stable roommates with free edges. Technical Report 2009-01, Egerv´ ary Research Group on Combinatorial Optimization, Operations Research Department, E¨ otv¨ os Lor´ and University, 2009

    work page 2009

  4. [4]

    Cseh and D

    ´A. Cseh and D. F. Manlove. Stable marriage and roommates problems with restricted edges: complexity and approximability. Discrete Optimization , 20:62–89, 2016

    work page 2016

  5. [5]

    V. M. F. Dias, G. D. da Fonseca, C. M. H. de Figueiredo, and J. L. S zwarc- fiter. The stable marriage problem with restricted pairs. Theoretical Com- puter Science, 306:391–405, 2003

    work page 2003

  6. [6]

    Fleiner, R

    T. Fleiner, R. W. Irving, and D. F. Manlove. Efficient algorithms for gen- eralised stable marriage and roommates problems. Theoretical Computer Science, 381:162–176, 2007

    work page 2007

  7. [7]

    Fleiner, R

    T. Fleiner, R. W. Irving, and D. F. Manlove. An algorithm for a supe r- stable roommates problem. Theoretical Computer Science , 412(50):7059– 7065, 2011

    work page 2011

  8. [8]

    Gale and L

    D. Gale and L. S. Shapley. College admissions and the stability of mar riage. American Mathematical Monthly , 69:9–15, 1962

    work page 1962

  9. [9]

    M. R. Garey and D. S. Johnson. Computers and Intractability . Freeman, San Francisco, CA., 1979

    work page 1979

  10. [10]

    R. W. Irving. Stable marriage and indifference. Discrete Applied Mathe- matics, 48:261–272, 1994

    work page 1994

  11. [11]

    R. W. Irving, D. F. Manlove, and G. O’Malley. Stable marriage with t ies and bounded length preference lists. Journal of Discrete Algorithms , 7(2):213– 219, 2009

    work page 2009

  12. [12]

    R. W. Irving, D. F. Manlove, and S. Scott. Strong stability in the Hospitals / Residents problem. In Proceedings of STACS ’03: the 20th Annual Sym- posium on Theoretical Aspects of Computer Science , volume 2607 of Lecture Notes in Computer Science , pages 439–450. Springer, 2003

    work page 2003

  13. [13]

    Iwama, D

    K. Iwama, D. F. Manlove, S. Miyazaki, and Y. Morita. Stable marr iage with incomplete lists and ties. In J. Wiedermann, P. van Emde Boas, an d M. Nielsen, editors, Proceedings of ICALP ’99: the 26th International Collo- quium on Automata, Languages, and Programming , volume 1644 of Lecture Notes in Computer Science , pages 443–452. Springer, 1999

    work page 1999

  14. [14]

    D. Knuth. Mariages Stables . Les Presses de L’Universit´ e de Montr´ eal, 1976. English translation in Stable Marriage and its Relation to Other Combinato- rial Problems, volume 10 of CRM Proceedings and Lecture Notes, American Mathematical Society, 1997

    work page 1976

  15. [15]

    A. Kunysz. An algorithm for the maximum weight strongly stable m atching problem. In 29th International Symposium on Algorithms and Computatio n (ISAAC 2018) , pages 42:1–42:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018

    work page 2018

  16. [16]

    Kwanashie

    A. Kwanashie. Efficient algorithms for optimal matching problems under preferences. PhD thesis, University of Glasgow, 2015

    work page 2015

  17. [17]

    D. F. Manlove. Stable marriage with ties and unacceptable partn ers. Tech- nical Report TR-1999-29, University of Glasgow, Department of C omputing Science, January 1999

    work page 1999

  18. [18]

    D. F. Manlove. The structure of stable marriage with indifferenc e. Discrete Applied Mathematics, 122(1-3):167–181, 2002

    work page 2002

  19. [19]

    D. F. Manlove. Algorithmics of Matching Under Preferences . World Scien- tific, 2013

    work page 2013

  20. [20]

    D. F. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, and Y. Morita . Hard variants of stable marriage. Theoretical Computer Science , 276:261–279, 2002

    work page 2002

  21. [21]

    McDermid and D

    E. McDermid and D. F. Manlove. Keeping partners together: alg orithmic results for the Hospitals / Residents problem with couples. Journal of Combinatorial Optimization , 19:279–303, 2010

    work page 2010

  22. [22]

    Porschen, T

    S. Porschen, T. Schmidt, E. Speckenmeyer, and A. Wotzlaw. X SAT and NAE-SAT of linear CNF classes. Discrete Applied Mathematics , 167:1–14, 2014

    work page 2014

  23. [23]

    T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing , pages 216–

    work page

  24. [24]

    S. Scott. A study of stable marriage problems with ties . PhD thesis, Uni- versity of Glasgow, Department of Computing Science, 2005

    work page 2005