arxiv: 2603.26943 · v2 · submitted 2026-03-27 · 💻 cs.DS · cs.GT· math.CO

Recognition: 2 theorem links

· Lean Theorem

Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings

Christine T. Cheng , Will Rosenbaum

Authors on Pith no claims yet

Pith reviewed 2026-05-14 22:43 UTC · model grok-4.3

classification 💻 cs.DS cs.GTmath.CO

keywords stable roommatesstable marriageoptimal stable matchingparameterized algorithmsfixed-parameter tractabilitycrossing distancematching problems

0 comments

The pith

When minimum crossing distance is k, an optimal stable matching in Stable Roommates can be found in 2 to the O(k) times n to the O(1) time.

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

The paper defines minimum crossing distance as a structural measure of how far a Stable Roommates instance lies from a Stable Marriage instance. It proves that this distance k yields a fixed-parameter tractable algorithm that computes an optimal stable matching in 2^{O(k)} n^{O(1)} time. When k equals zero the instance reduces exactly to Stable Marriage, recovering the known polynomial-time methods. The result therefore interpolates between the tractable bipartite case and the general NP-hard case by controlling the number of crossings needed to restore bipartiteness in the preference structure.

Core claim

The authors establish that an SR instance with minimum crossing distance k admits an algorithm computing an optimal stable matching in time 2^{O(k)} n^{O(1)}. The minimum crossing distance counts the fewest crossings required to transform the cyclic preference lists of SR into the bipartite lists of SM while preserving the stability and optimality properties of the resulting matchings.

What carries the argument

Minimum crossing distance, which quantifies the smallest number of preference crossings needed to reduce an SR instance to an equivalent SM instance.

If this is right

Optimal stable matchings become fixed-parameter tractable in the minimum crossing distance.
Instances at distance zero inherit the efficient algorithms already known for Stable Marriage.
The exponential cost is confined to the parameter k, leaving only polynomial dependence on the number of agents.
The same reduction technique applies to any optimization criterion that is efficiently solvable on SM instances.

Where Pith is reading between the lines

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

Real-world preference data could be classified by their crossing distance to decide whether exact optimal matchings are feasible.
The crossing-distance idea may extend to other NP-hard matching variants whose hardness stems from non-bipartite cycles.
One could seek approximation schemes whose ratio improves as the crossing distance shrinks.

Load-bearing premise

The minimum crossing distance is well-defined and any structural reduction to SM instances for bounded k preserves both stability and optimality of the matching.

What would settle it

An SR instance whose minimum crossing distance equals zero yet requires super-polynomial time to find an optimal stable matching would falsify the claim.

Figures

Figures reproduced from arXiv: 2603.26943 by Christine T. Cheng, Will Rosenbaum.

**Figure 2.** Figure 2: On the left is a mirror poset P with five dual pairs. On the right is the median graph 𝐺(P) formed by its seven complete closed subsets. Two subsets are adjacent in the median graph if and only if they differ by one element. It is interesting that median graphs, the meta-structures for SR stable matchings, are unordered while distributive lattices, the meta-structures for SM stable matchings, are ordered. … view at source ↗

**Figure 3.** Figure 3: At the top left is the median semilattice [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

**Figure 4.** Figure 4: This time around, the median graph 𝐺(P) in [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗

read the original abstract

In the Stable Roommates Problem (SR), a set of $2n$ agents rank one another in a linear order. The goal is to find a matching that is stable: one that has no pair of agents who mutually prefer each other over their assigned partners. We consider the problem of finding an optimal stable matching. Agents associate weights with each of their potential partners, and the goal is to find a stable matching that minimizes the sum of the associated weights. Efficient algorithms exist for finding an optimal stable matching in the Stable Marriage Problem (SM), but the problem is NP-hard for general SR instances. In this paper, we define a notion of structural distance between SR instances and SM instances, which we call the minimum crossing distance. When an SR instance has minimum crossing distance $0$, the instance is structurally equivalent to an SM instance, and this structure can be exploited to find an optimal stable matching efficiently. More generally, we show that when an SR instance has minimum crossing distance $k$, an optimal stable matching can be computed in time $2^{O(k)} n^{O(1)}$. Thus, the optimal stable matching problem is fixed-parameter tractable (FPT) with respect to minimum crossing distance.

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.

Desk Editor's Note private letter to a colleague

This paper defines a minimum crossing distance parameter and gives an FPT algorithm for optimal stable matchings in stable roommates instances.

read the letter

The main thing to know is that the authors introduce minimum crossing distance as a parameter and prove that optimal stable matchings in stable roommates can be found in 2^{O(k)} n^{O(1)} time when that distance is at most k. When the distance is zero the instance reduces to stable marriage and the known polynomial algorithm applies directly. For positive k they give a structural reduction that handles the crossings while preserving stability and the weight sum objective. This is new; prior parameterized work on stable matchings used different measures such as the number of unstable pairs or treewidth, and this parameter sits more directly on the SR-SM distinction. The approach looks clean and the runtime bound is standard for FPT. The abstract states the claim without circularity or hidden assumptions about preferences. One minor soft spot is that the abstract does not spell out the time to compute the minimum crossing distance itself. If that step is not FPT then the end-to-end result would be weaker, though the stress-test note indicates the reduction itself is straightforward and no such gap appears. The paper is aimed at people working on parameterized algorithms for matching problems in algorithmic game theory. A reader who already knows the stable marriage and stable roommates literature would get the most out of it and could use the new parameter in follow-up work. It is solid enough to deserve a serious referee.

Referee Report

2 major / 2 minor

Summary. The paper defines a structural parameter called the minimum crossing distance k between a Stable Roommates (SR) instance and a Stable Marriage (SM) instance. It claims that when this distance is bounded by k, an optimal stable matching in the SR instance can be computed in 2^{O(k)} n^{O(1)} time via a structural reduction to an SM instance, establishing that the optimal stable matching problem is FPT with respect to minimum crossing distance.

Significance. If the reduction and algorithm are correct, the result supplies a clean parameterized bridge between the polynomial-time solvable SM case and the NP-hard general SR case. The parameter is natural (measuring deviation from bipartiteness) and the runtime is standard FPT; the work would be useful for instances whose preference structure is nearly bipartite, with potential extensions to other matching problems.

major comments (2)

[§3] §3 (Reduction and algorithm): the central claim requires a detailed, self-contained proof that the structural reduction to an SM instance preserves both stability and optimality of the matching when the crossing distance is at most k; the abstract asserts preservation but the load-bearing step is the explicit correspondence between stable matchings in the reduced instance and optimal stable matchings in the original SR instance.
[§2] Definition of minimum crossing distance (likely §2): it must be shown that the parameter is well-defined for every SR instance and that the reduction does not introduce new blocking pairs or alter the weight sum in a way that changes optimality; without this, the FPT claim does not go through.

minor comments (2)

[Abstract] Abstract: the phrase 'structurally equivalent' for k=0 should be replaced by a precise statement (e.g., the instance is bipartite with a fixed bipartition) to avoid ambiguity.
[Throughout] Notation: ensure that the weight function and the crossing-distance definition use consistent symbols throughout; a small table summarizing the reduction steps would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We appreciate the referee's positive evaluation and recommendation for minor revision. The comments highlight areas where additional details in the proofs would strengthen the presentation. We will revise the manuscript accordingly to address these points.

read point-by-point responses

Referee: [§3] §3 (Reduction and algorithm): the central claim requires a detailed, self-contained proof that the structural reduction to an SM instance preserves both stability and optimality of the matching when the crossing distance is at most k; the abstract asserts preservation but the load-bearing step is the explicit correspondence between stable matchings in the reduced instance and optimal stable matchings in the original SR instance.

Authors: We thank the referee for pointing this out. While the manuscript sketches the reduction, we agree that a fully self-contained proof is essential. In the revised version, we will provide a detailed proof in Section 3 that explicitly constructs the correspondence: for every stable matching in the reduced SM instance, we map it back to a matching in the original SR instance and prove it is stable and has the same total weight. Conversely, we show that every optimal stable matching in the SR instance corresponds to a stable matching in the reduced instance. This will include lemmas showing that blocking pairs cannot arise from the non-crossing parts due to the SM structure, and crossings are limited by k. revision: yes
Referee: [§2] Definition of minimum crossing distance (likely §2): it must be shown that the parameter is well-defined for every SR instance and that the reduction does not introduce new blocking pairs or alter the weight sum in a way that changes optimality; without this, the FPT claim does not go through.

Authors: The parameter is well-defined because the minimum crossing distance is the smallest number of edges that need to be 'removed' or 'crossed' to bipartition the agents into two sets with no intra-set preferences, making it an SM instance. We will add a formal definition and proof of existence in Section 2, noting that k is at most the number of possible edges within one side. For the reduction, the proof will demonstrate that the weight sums are preserved exactly for corresponding matchings, and any new blocking pair would imply a crossing that contradicts the minimality of k or the stability in the reduced instance. We will include this in the expanded Section 3 as well. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation defines minimum crossing distance as an external structural parameter on SR instances, shows equivalence to SM at k=0, and constructs an FPT algorithm whose 2^{O(k)} n^{O(1)} runtime follows from standard branching/DP over the k crossings. No equation reduces the output matching or runtime to a fitted quantity, self-referential definition, or load-bearing self-citation; the stability and optimality invariants are preserved by the explicit reduction rather than by construction from the target result itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the definition of minimum crossing distance and standard facts from matching theory. No free parameters are fitted. One invented entity is the crossing distance itself.

axioms (1)

domain assumption Stability and optimality are preserved under the structural reduction when crossing distance is bounded
Invoked in the statement that distance k yields the FPT runtime

invented entities (1)

minimum crossing distance no independent evidence
purpose: Measure of structural distance between SR and SM instances
Newly defined parameter that enables the FPT result

pith-pipeline@v0.9.0 · 5525 in / 1107 out tokens · 30933 ms · 2026-05-14T22:43:20.623344+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

When an SR instance has minimum crossing distance k, an optimal stable matching can be computed in time 2^{O(k)} n^{O(1)}
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

mirror poset R'(I) ... crossing edges ... median semilattice L(I, η)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages

[1]

S. P. Avann. Metric ternary distributive semi-lattices.Proceedings of the American Mathematical Society, 12:407–414, 1961

work page 1961
[2]

Metric graph theory and geometry: A survey.Contemporary Mathematics, pages 49–86, 2008

Hans-J¨ urgen Bandelt and Victor Chepoi. Metric graph theory and geometry: A survey.Contemporary Mathematics, pages 49–86, 2008

work page 2008
[3]

Sampling Stable Marriages: Why Spouse- swapping Won’t Work

Nayantara Bhatnagar, Sam Greenberg, and Dana Randall. Sampling Stable Marriages: Why Spouse- swapping Won’t Work. InProceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, pages 1223–1232, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics

work page 2008
[4]

Rings of sets.Duke Mathematical Journal, 3(3):443–454, September 1937

Garrett Birkhoff. Rings of sets.Duke Mathematical Journal, 3(3):443–454, September 1937. ISSN 0012-7094, 1547-7398. doi:10.1215/S0012-7094-37-00334-X

work page doi:10.1215/s0012-7094-37-00334-x 1937
[5]

How hard is it to satisfy (almost) all roommates?, February 2018

Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion. How hard is it to satisfy (almost) all roommates?, February 2018. 22

work page 2018
[6]

Matchings under preferences: Strength of stability and trade-offs

Jiehua Chen, Piotr Skowron, and Manuel Sorge. Matchings under preferences: Strength of stability and trade-offs. In Anna R. Karlin, Nicole Immorlica, and Ramesh Johari, editors,Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 41–59. ACM, 2019. doi:10.1145/3328526.3329555. URL https://d...

work page doi:10.1145/3328526.3329555 2019
[7]

Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik

Jiehua Chen, Christine Cheng, David Manlove, and Ildik´o Schlotter, editors.Frontiers of Parameterized Algorithmics of Matching under Preferences (Dagstuhl Seminar 25342), Dagstuhl Reports, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. URL https://www.dagstuhl.de/ 25342

work page 2025
[8]

Christine T. Cheng. The Generalized Median Stable Matchings: Finding Them Is Not That Easy. In Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, and Luerbio Faria, editors,LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science, pages 568–579, Berlin, Heidelberg,

work page 2008
[9]

ISBN 978-3-540-78773-0

Springer. ISBN 978-3-540-78773-0. doi:10.1007/978-3-540-78773-0 49

work page doi:10.1007/978-3-540-78773-0
[10]

Christine T. Cheng. Understanding the Generalized Median Stable Matchings.Algorithmica, 58(1): 34–51, September 2010. ISSN 1432-0541. doi:10.1007/s00453-009-9307-2

work page doi:10.1007/s00453-009-9307-2 2010
[11]

Cheng and Anhua Lin

Christine T. Cheng and Anhua Lin. Stable roommates matchings, mirror posets, median graphs, and the local/global median phenomenon in stable matchings.SIAM Journal on Discrete Mathematics, 25(1): 72–94, 2011. doi:10.1137/090750299

work page doi:10.1137/090750299 2011
[12]

Cheng and Will Rosenbaum

Christine T. Cheng and Will Rosenbaum. Stable Matchings with Restricted Preferences: Structure and Complexity.ACM Transactions on Economics and Computation, 10(3):1–45, September 2022. ISSN 2167-8375, 2167-8383. doi:10.1145/3565558

work page doi:10.1145/3565558 2022
[13]

Cheng, Eric McDermid, and Ichiro Suzuki

Christine T. Cheng, Eric McDermid, and Ichiro Suzuki. Center stable matchings and centers of cover graphs of distributive lattices. In Luca Aceto, Monika Henzinger, and Jir ´ı Sgall, editors,Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, volume 6755 ofLecture Notes...

work page 2011
[14]

URL https://doi.org/10.1007/978-3-642-22006-7 57

doi:10.1007/978-3-642-22006-7 57. URL https://doi.org/10.1007/978-3-642-22006-7 57

work page doi:10.1007/978-3-642-22006-7
[15]

Cheng, Eric McDermid, and Ichiro Suzuki

Christine T. Cheng, Eric McDermid, and Ichiro Suzuki. Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings.Discret. Appl. Math., 205: 27–34, 2016. doi:10.1016/J.DAM.2015.11.016. URL https://doi.org/10.1016/j.dam.2015.11.016

work page doi:10.1016/j.dam.2015.11.016 2016
[16]

T. Feder. A new fixed point approach for stable networks stable marriages. InProceedings of the Twenty-First Annual ACM Symposium on Theory of Computing - STOC ’89, pages 513–522, Seattle, Washington, United States, 1989. ACM Press. ISBN 978-0-89791-307-2. doi:10.1145/73007.73056

work page doi:10.1145/73007.73056 1989
[17]

T. Feder. A new fixed point approach for stable networks and stable marriages.Journal of Computer and System Sciences, 45:233–284, 1992

work page 1992
[18]

American Mathematical Soc., 1995

Tom ´as Feder.Stable Networks and Product Graphs, volume 555. American Mathematical Soc., 1995

work page 1995
[19]

Lattice structure from planar graphs.Electronic Journal of Combinatorics, 11:R15, 2004

Stefan Felsner. Lattice structure from planar graphs.Electronic Journal of Combinatorics, 11:R15, 2004

work page 2004
[20]

Gale and L

D. Gale and L. S. Shapley. College Admissions and the Stability of Marriage.The American Mathematical Monthly, 69(1):9–15, January 1962. ISSN 0002-9890. doi:10.1080/00029890.1962.11989827

work page doi:10.1080/00029890.1962.11989827 1962
[21]

Garey, D.S

M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems.Theoretical Computer Science, 1(3):237–267, 1976. ISSN 0304-3975. doi:10.1016/0304-3975(76)90059-1. 23

work page doi:10.1016/0304-3975(76)90059-1 1976
[22]

Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum

Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum. A stable marriage requires communication.Games and Economic Behavior, 2019. ISSN 0899-8256. doi:10.1016/j.geb.2018.10.013

work page doi:10.1016/j.geb.2018.10.013 2019
[23]

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization).SIAM Journal on Discrete Mathematics, 36(1):596–681, March 2022

Sushmita Gupta, Saket Saurabh, and Meirav Zehavi. On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization).SIAM Journal on Discrete Mathematics, 36(1):596–681, March 2022. ISSN 0895-4801, 1095-7146. doi:10.1137/19M130491X

work page doi:10.1137/19m130491x 2022
[24]

The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments.SIAM Journal on Computing, 17(4):742–769, August 1988

Dan Gusfield. The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments.SIAM Journal on Computing, 17(4):742–769, August 1988. ISSN 0097-5397, 1095-7111. doi:10.1137/0217048

work page doi:10.1137/0217048 1988
[25]

Foundations of Computing

Dan Gusfield and Robert W Irving.The Stable Marriage Problem: Structure and Algorithms. Foundations of Computing. MIT Press, London, England, August 1989

work page 1989
[26]

Hochbaum

Dorit S. Hochbaum. A new—old algorithm for minimum-cut and maximum-flow in closure graphs. Networks, 37(4):171–193, July 2001. ISSN 0028-3045, 1097-0037. doi:10.1002/net.1012

work page doi:10.1002/net.1012 2001
[27]

John Wiley & Sons, New York, 2000

Wilfried Imrich and Sandi Klavˇ zar.Product Graphs: Structure and Recognition. John Wiley & Sons, New York, 2000. ISBN 978-0-471-37039-0

work page 2000
[28]

stable roommates

Robert W Irving. An efficient algorithm for the “stable roommates” problem.Journal of Algorithms, 6 (4):577–595, December 1985. ISSN 01966774. doi:10.1016/0196-6774(85)90033-1

work page doi:10.1016/0196-6774(85)90033-1 1985
[29]

Robert W. Irving. On the stable room-mates problem. Technical Report CSC/86/R5, University of Glasgow, Department of Computing Science, Glasgow, Scotland, 1986

work page 1986
[30]

Irving and Paul Leather

Robert W. Irving and Paul Leather. The Complexity of Counting Stable Marriages.SIAM Journal on Computing, 15(3):655–667, 1986. doi:10.1137/0215048

work page doi:10.1137/0215048 1986
[31]

Irving, Paul Leather, and Dan Gusfield

Robert W. Irving, Paul Leather, and Dan Gusfield. An efficient algorithm for the “optimal” stable marriage.Journal of the ACM, 34(3):532–543, July 1987. ISSN 0004-5411. doi:10.1145/28869.28871

work page doi:10.1145/28869.28871 1987
[32]

Karlin, Shayan Oveis Gharan, and Robbie Weber

Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber. A simply exponential upper bound on the maximum number of stable matchings. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors,Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 920–925. ACM, 2018. doi:10....

work page doi:10.1145/3188745.3188848 2018
[33]

Richard M. Karp. Reducibility Among Combinatorial Problems. In Michael J¨ unger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A. Wolsey, editors,50 Years of Integer Programming 1958-2008, pages 219–241. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. ISBN 978-3-540-682...

work page doi:10.1007/978-3-540-68279-0 1958
[34]

Complexity of the sex-equal stable marriage problem.Japan Journal of Industrial and Applied Mathematics, 10(1):1, February 1993

Akiko Kato. Complexity of the sex-equal stable marriage problem.Japan Journal of Industrial and Applied Mathematics, 10(1):1, February 1993. ISSN 1868-937X. doi:10.1007/BF03167200

work page doi:10.1007/bf03167200 1993
[35]

Median graphs: Characterizations, location theory and related structures.Journal of Combinatorial Mathematics and Combinatorial Computing, 30:103–127, 1999

Sandi Klavˇ zar and Henry Martyn Mulder. Median graphs: Characterizations, location theory and related structures.Journal of Combinatorial Mathematics and Combinatorial Computing, 30:103–127, 1999

work page 1999
[36]

Knuth, N.G

D.E. Knuth, N.G. De Bruijn, and M. Goldstein.Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms. CRM Proceedings & Lecture Notes. American Mathematical Society, 1997. ISBN 978-0-8218-0603-6. 24

work page 1997
[37]

Knuth.Mariages stables et leurs relations avec d’autres probl `emes combinatoires

Donald E. Knuth.Mariages stables et leurs relations avec d’autres probl `emes combinatoires. Les Presses de l’Universit´e de Montr´eal, Montr´eal, 1976

work page 1976
[38]

Eric McDermid and Robert W. Irving. Sex-Equal Stable Matchings: Complexity and Exact Algorithms. Algorithmica, 68(3):545–570, March 2014. ISSN 1432-0541. doi:10.1007/s00453-012-9672-0

work page doi:10.1007/s00453-012-9672-0 2014
[39]

J. Picard. Maximum closure of a graph and applications to combinatorial problems.Management Science, 22:1268–1272, 1976

work page 1976
[40]

Generating random elements of finite distributive lattices.Electronic Journal of Combinatorics, 4:R15, 1997

James Propp. Generating random elements of finite distributive lattices.Electronic Journal of Combinatorics, 4:R15, 1997

work page 1997
[41]

Almost 2-SAT is fixed-parameter tractable.Journal of Computer and System Sciences, 75(8):435–450, December 2009

Igor Razgon and Barry O’Sullivan. Almost 2-SAT is fixed-parameter tractable.Journal of Computer and System Sciences, 75(8):435–450, December 2009. ISSN 00220000. doi:10.1016/j.jcss.2009.04.002

work page doi:10.1016/j.jcss.2009.04.002 2009
[42]

A quadratic lower bound for stable roommates solvability, 2025

Will Rosenbaum. A quadratic lower bound for stable roommates solvability, 2025. https://arxiv.org/abs/ 2502.06464. A Appendix The goal of this section is to prove two results from the main section of the paper: Corollary 3.5 and Lemma 3.10. To do so, we need to discuss Irving’s algorithm and the notions of tables and rotations in more detail. We will ment...

work page arXiv 2025
[43]

The elimination of the rotations after 𝜎1 in Π𝑆 may 29 still delete entries from 𝑎’s list, but none of them can delete𝑐0 because 𝑎 is not in their 𝑌-sets

Then ℓ𝑇 (𝑎)=𝑐 0. The elimination of the rotations after 𝜎1 in Π𝑆 may 29 still delete entries from 𝑎’s list, but none of them can delete𝑐0 because 𝑎 is not in their 𝑌-sets. Hence, 𝑐0 is the only entry left in𝑎’s list once all the rotations inΠ 𝑆 are deleted. We have shown that whenX𝑎 ≠∅ or Y𝑎 ≠∅, the partner of 𝑎 in 𝜇 can be determined by just examining th...

work page