REVIEW 1 major objections 1 minor 1 cited by
Control in Stable Marriage and Stable Roommates: Complexity and Algorithms
T0 review · 1 major / 1 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read This paper settles the complexity of all 27 control problems for stable marriage and stable roommates: adding agents is NP-complete in most cases, while deleting agents to cover a target agent or pair is polynomial-time solvable.
desk verdict A solid complexity-classification paper that closes a natural 27-cell table; the only load-bearing external step is a cited stable-partition theorem that deserves explicit statement. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the stable partition of Tan, a partition of the agents into ordered lists in which every agent prefers its predecessor to its successor, each even list is matched internally, and each odd list leaves one agent unmatched. The deletion algorithm removes all acceptability pairs that could threaten the target pair, computes a stable partition of the modified instance, and counts the forbidden odd parties (singletons formed by agents in the target pair's preferred sets, plus odd parties of size at least three); the theorem that deleting one agent destroys at most one odd party lets the algorithm certify that each forbidden party needs its own deletion. The hardness results are carried by preference gadgets built from CLIQUE and INDEPENDENT SET, where the only way to add few agents and reach the goal is to encode a clique or an independent set in the added agents.
What would settle it
Take any stable roommates instance, compute a stable partition, delete one agent, and recompute a stable partition of the smaller instance; if any single deletion eliminates two or more odd parties of size at least three, Tan and Hsueh's Corollary 3.9 is violated and Theorem 4's proof fails. A direct exhaustive check over all instances with up to eight agents would settle whether such a counterexample exists.
Extended reading notes
Core claim
The paper's central claim is that all 27 CONTROL IN STABLE MARRIAGE/ROOMMATES-A-G problems now have a definite complexity classification. On the hard side, Theorem 1 proves that CSM-AddAg-MA and CSM-AddAg-∃PSM are NP-complete, Theorem 2 proves that CSR-AddAg-MS is NP-complete, and Theorem 3 proves that CSR-AddAg-∃SM and CSR-AddAg-∃PSM are NP-complete; a corollary extends the hardness for matching a specified agent to the roommates setting. On the easy side, Theorem 4 puts CSR-DelAg-MP and CSR-DelAg-MA in P, and Proposition 2 puts CSR-DelAcc-MS in linear time. The remaining cells of the classification come from earlier work, and the complete table is the paper's contribution: a full map of when a controller can efficiently steer a stable matching market and when this is NP-hard.
Load-bearing premise
The deletion algorithm's correctness depends on the external theorem that removing a single agent from a roommates instance can destroy at most one 'odd party' of its stable partition; if that theorem fails for the specially modified instance, the only new polynomial-time claim collapses.
Editorial extensions
If this is right
- A controller who may delete agents can efficiently guarantee that a given agent or pair is matched in a stable matching, even in the roommates setting, because CSR-DelAg-MA and CSR-DelAg-MP are polynomial-time solvable.
- Adding agents is a hard form of control: in the roommates setting, making a prescribed matching stable or creating any stable matching is NP-complete, and in the marriage setting the same is true for matching a specified agent or forcing a perfect stable matching.
- The automatic existence of stable matchings in marriage instances means that existence-based control goals are only meaningful in the roommates setting, where adding agents can destroy or create stability at the price of NP-completeness.
- The classification identifies the polynomial cases (CSM-AddAg-MS, the DelAg goals for MA and MP in both settings, the DelAg existence goals in roommates, and DelAcc-MS in both settings) as the only candidates for practical optimal-control algorithms.
Reading between the lines
- An extension the paper does not explore is a combined budget for deleting agents and deleting acceptability edges; the stable-partition counting argument may adapt because both operations act on forbidden odd parties and blocking pairs.
- The reduction from CLIQUE to CSM-AddAg-MA suggests that approximating the minimum number of agents needed to match a target agent is as hard as approximating the clique number, so inapproximability results may be within reach.
- The independent-set gadgets in Theorems 2 and 3 could be reused to show parameterized hardness for these control problems with the budget as parameter, by importing parameterized intractability of independent set.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies control problems in stable marriage (SM) and stable roommates (SR), where a controller can add agents, delete agents, or delete acceptability edges to achieve one of five goals: making a given agent matched, making a given pair matched, making a given matching stable, making a stable matching exist, or making a perfect stable matching exist. For the resulting 27 problems the paper claims a complete complexity classification. The new technical results are NP-completeness for CSM-AddAg-MA, CSM-AddAg-∃PSM, CSR-AddAg-MA, CSR-AddAg-MS, CSR-AddAg-∃SM and CSR-AddAg-∃PSM (Theorems 1-3 and Corollary 1), and polynomial-time solvability for CSR-DelAg-MP and CSR-DelAg-MA (Theorem 4), together with two simple consequences of known results (Propositions 1-2). The paper positions these results inside the previously known entries of Table 1 and concludes that all open cases are settled.
Significance. If the results are correct, the paper provides a useful and fairly complete complexity map for a natural family of control problems in matching under preferences. The reductions in Theorems 1-3 are detailed, with explicit budgets, forward and reverse directions, and blocking-pair arguments, so they can be checked step by step. The polynomial-time algorithm in Theorem 4 is conceptually elegant and would be an interesting addition to the known tractability results for stable roommates, but its correctness depends on a cited structural theorem about stable partitions. The paper's main value is classificatory: it closes open cases and identifies exactly which control problems are hard and which are easy. The presentation is generally clear, and the connection to earlier work by Boehmer et al. and to Tan's stable-partition framework is well explained.
major comments (1)
- [Section 4.2, Claim 1] The last paragraph of Section 4.2 bases the only-if direction of Theorem 4 entirely on the cited result of Tan and Hsueh (1995, Corollary 3.9), but the exact statement and hypotheses of that corollary are not given. The proof needs the property that deleting one agent destroys at most one odd party of the original stable partition, where 'odd party' must include singleton odd parties of the kind collected in the set U, and the property must hold for the arbitrary stable partition Π computed in Step 2 by Tan's algorithm. If the corollary applies only to odd parties of size at least 3, then deleting the agents in U would not be counted in the lower bound and the inequality ℓ ≥ r + |U| would not follow. Since this is the only new polynomial-time result in the paper, the authors should quote the corollary explicitly, confirm that it covers singleton odd parties, and explain why the stable partition of I* - S used in the argument is a stable partition to which the corollary applies. This is a load-bearing point of the proof and needs to be fixed.
minor comments (1)
- [Section 2.1, AddAg definitions] In the reduction for Theorem 1, the preference list of each dummy man d is written as '{ mv : v ∈ V }'; from the construction it should be the set of women { w_v : v ∈ V }. The notation should be corrected.
Circularity Check
No circularity: new reductions and algorithm rest on external theorems (Clique/Independent Set, stable partitions), not on the claims being proved.
full rationale
After walking the derivation chain, I found no circular step. The new hardness results (Theorems 1-3) are reductions from Clique and Independent Set with explicitly constructed preference profiles, and the correctness arguments prove both directions without assuming the target complexity. Proposition 1 is a direct reduction to the known polynomial problem CSM-DelAg-MP, and Proposition 2 counts blocking pairs directly. Theorem 4's algorithm depends on stable partitions by Tan (1991a,b) and on Tan-Hsueh (1995, Corollary 3.9), an external published structural result about deleting one agent destroying at most one odd party. The paper cites that result without proof, but this is ordinary use of an established theorem, not circular reasoning: the cited theorem is not equivalent to the paper's conclusion and does not cite the present paper. The only same-author citation is Mnich and Schlotter (2020), used as an external NP-hardness input for CSM-DelAcc-MA; that result is not derived here and is not the central contribution. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled via self-citation.
Assumptions & free parameters
assumptions (6)
- standard math Gale-Shapley theorem: every stable marriage instance has a stable matching and it can be found in linear time.
- standard math Rural Hospitals Theorem: all stable matchings in a given instance cover the same set of agents.
- standard math Irving's algorithm: existence of a stable matching in a stable roommates instance is decidable in polynomial time.
- standard math Tan stable partition theory, including the Tan-Hsueh property that deleting one agent destroys at most one odd party.
- standard math NP-completeness of Clique and Independent Set.
- domain assumption The model assumes symmetric acceptability and strict linear preference lists.
Cite this review
Pith. "Pith review of Control in Stable Marriage and Stable Roommates: Complexity and Algorithms." pith.science (2026). https://pith.science/paper/B72WDJSP
@misc{pith2026250201215,
author = {Pith},
title = {Pith review of: Control in Stable Marriage and Stable Roommates: Complexity and Algorithms},
year = {2026},
howpublished = {\url{https://pith.science/paper/B72WDJSP}},
note = {Machine review of arXiv:2502.01215}
}
read the original abstract
We study control problems in the context of matching under preferences: We examine how a central authority, called the controller, can manipulate an instance of the Stable Marriage or Stable Roommates problems in order to achieve certain goals. We investigate the computational complexity of the emerging problems, and provide both efficient algorithms and intractability results.
Forward citations
Cited by 1 Pith paper
-
Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
Generalised stable partitions characterize the solution space of many-to-many non-bipartite stable matching, giving a solvability certificate and improved near-feasible algorithms.
Reference graph
Works this paper leans on
-
[1987]
An efficient algorithm for the “optimal” stable marriage. J. ACM 34, 3 (1987), 532–543. https://doi.org/10.1145/28869.28871 Naoyuki Kamiyama. 2025. Modifying an instance of the super-stable matching problem. Inform. Process. Lett. 189 (2025), 106549. https://doi.org/10.1016/j.ipl.2024.106549 David F. Manlove. 2013. Algorithmics of Match- ing Under Preferen...
-
[1989]
The Computational Difficulty of Manipulating an Election. Social Choice and W elfare6, 3 (1989), 227–241. https://doi.org/10.1007/BF00295861 Krist´ of B´ erczi, Gergely Cs´ aji, and Tam´ as Kir´ aly. 2024. Ma- nipulating the outcome of stable marriage and roommates problems. Games and Economic Behavior 147 (2024), 407–428. https://doi.org/10.1016/j.geb.202...
-
[2006]
“Almost stable” Matchings in the Roommates Problem. In WAOA 2005: Proceedings of the 3rd W ork- shop on Approximation and Online Algorithms (Lecture Notes in Computer Science, V ol. 3879) . Springer, 1–14. https://doi.org/10.1007/11671411 1 John J. Bartholdi III, Craig A. Tovey, and Michael A. Trick
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.