{"id":"69ad9c25-f17b-452f-909a-8fba4b2d05eb","arxiv_id":"2502.01215","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"All 27 control problems for stable marriage and stable roommates are classified, with new NP-completeness results for adding agents and a new polynomial algorithm for deleting agents in roommates.","lead":"This paper maps the computational difficulty of a central authority manipulating stable matching markets by adding people, removing people, or removing acceptable pairs. It completes the complexity classification for 27 control problems in stable marriage and stable roommates, adding several NP-completeness proofs and one new polynomial-time algorithm.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's P result rests on the cited Tan–Hsueh odd-party deletion theorem; standard and likely correct, but the counting argument deserves a direct small-instance verification before final reliance.","rationale":"The central claim is the complete complexity classification in Table 1. The new NP-completeness proofs (Theorems 1–3) are explicit reductions; I checked their budget counts and blocking-pair arguments and found no internal inconsistency (apart from light OCR corruption in the text). The single point where the argument imports deep external structure is Theorem 4, and the reader's weakest_assumption identifies exactly that point. The cited Tan–Hsueh corollary is a published theorem and the described use is the standard way stable partitions are used, so I do not regard this as a demonstrated error. For that reason I would not change the reader's ACCEPT verdict. A small brute-force test is nevertheless worthwhile because the paper neither states the corollary's precise hypotheses nor shows the induction over multiple deletions, and because the algorithm's correctness hinges on the count of singleton odd parties. The test would settle the concern with certainty at low cost.","tokens_in":12665,"tokens_out":21696,"duration_ms":716066,"concrete_test":"Brute-force verify the counting argument on all stable-roommates instances up to n=6 (or a large random sample if exhaustive enumeration is infeasible). For each instance, construct I*, compute one stable partition Π and r, U as in Step 2, then enumerate every deletion set S with |S|<r+|U| and test whether I*−S admits any stable matching that covers every agent in (A*∪B*) minus S. Finding such an S would refute Theorem 4's lower-bound proof; finding none on all tested instances would confirm that the Tan–Hsueh corollary is being applied correctly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4.2 (Theorem 4), the only-if direction of the CSR-DelAg-MP algorithm's correctness uses the external result that deleting one agent from an SR instance destroys at most one odd party of a stable partition (Tan–Hsueh 1995, Corollary 3.9). The proof needs this to conclude that fewer than r+|U| deletions from the reduced instance I* cannot remove all 'forbidden' odd parties: nonsingleton odd parties plus singleton parties consisting of agents in A*∪B*. If the corollary applies only to a specially chosen stable partition rather than to the arbitrary Π computed in Step 2, or if it does not count singleton odd parties, then the inequality ℓ ≥ r+|U| fails and the polynomial-time result for CSR-DelAg-MP/MA collapses. The paper cites the corollary without proof or statement of its exact hypotheses. Since Theorem 4 anchors the only new P entries in Table 1, this is the most load-bearing step in the paper. I found no comparable internal flaw in the reductions for Theorems 1–3.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12900,"tokens_out":28083,"duration_ms":269994,"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":[{"comment":"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.","section":"Section 4.2, Claim 1"}],"minor_comments":[{"comment":"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.","section":"Section 2.1, AddAg definitions"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and the main classification claim is plausible. The two load-bearing issues are the false statement of Claim 1 and the unstated exact content of the Tan-Hsueh corollary used in Theorem 4. Both appear fixable with a moderate revision; I do not see a reason to doubt the main results, but the proof as written is not yet fully rigorous."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis paper settles all open questions in the control-in-stable-marriage/roommates matrix for three actions and five goals. The new NP-completeness results (add-agent variants) are built on clean reductions from Clique and Independent Set, with forward/reverse directions and budget arguments. The genuinely new technique is the polynomial-time algorithm for CSR-DelAg-MP/MA using Tan stable partitions; that is a smart extension of the Boehmer et al. bipartite approach.\n\nThe paper is honest about provenance, marking which cells are new and which are easy consequences. The reductions in Theorems 1–3 are detailed enough to re-check; I did not find a gap. The one soft spot is Theorem 4's reliance on Tan–Hsueh Corollary 3.9: the authors cite it without stating its exact hypotheses or proof, and the counting argument (ℓ ≥ r+|U|) depends on it. This is a standard result in the stable-roommates literature and is almost certainly correct, but for a journal version the authors should either state the lemma explicitly or give a short proof, because the entire P-result rides on it.\n\nMinor issue: the arXiv text has OCR artifacts (broken glyphs like /parenleft, /uni29EB) that make some definitions hard to read; that's a production issue, not a scientific one.\n\nOverall: the paper is a fair, useful contribution for anyone working on control in matching markets. It doesn't reshape the field, but it closes a natural set of questions and gives clear guidance on tractability. Worth sending to a serious referee.\n\nBest,\n[Your name]","headline":"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.","tokens_in":13428,"tokens_out":1342,"would_cite":true,"duration_ms":11793,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","91B68"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["stable marriage","stable roommates","control problems","matching under preferences","computational complexity","NP-completeness","polynomial-time algorithm","stable partitions"],"falsifier":"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.","tokens_in":12506,"feed_emoji":"🎛️","tokens_out":14060,"duration_ms":129583,"temperature":0.7,"pith_summary":"The paper asks how hard it is for a central authority to steer a stable matching market by adding agents, deleting agents, or deleting acceptability edges. It closes every open cell in the 27-problem complexity table for control in stable marriage and stable roommates, combining three new NP-completeness proofs with one new polynomial-time result. The hardness results show that adding agents to make a specified agent matched, to make a given matching stable, or to create a stable and perfect matching is intractable. The tractability result shows that deleting agents to keep a given agent or pair matched in a roommates instance is decidable in polynomial time via stable partitions. If the paper is right, the computational boundary of such manipulation is now fully mapped, which matters for any market design question about who can steer matching outcomes.","feed_headline":"All 27 stable-matching control problems now classified","feed_subtitle":"Adding agents is NP-hard; deleting agents to keep a target pair matched is polynomial-time.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the control framework, the known polynomial algorithm for CSM-DelAg-MP, and the CLIQUE-based reduction that Theorems 1 and 2 modify.","marker":"Boehmer et al. (2021)"},{"why":"Provides Corollary 3.9, the external theorem that deleting one agent destroys at most one odd party, on which Theorem 4's correctness proof depends.","marker":"Tan and Hsueh (1995)"},{"why":"Gives the linear-time algorithm for computing a stable partition used in Theorem 4's Step 2.","marker":"Tan (1991a)"},{"why":"Introduces stable partitions and the equivalence between maximum stable matchings and agent deletion, grounding the deletion results and Table 1 entries.","marker":"Tan (1991b)"},{"why":"Provides the polynomial-time algorithm to decide stable matching existence in roommates, used for the NP membership of the existence goals.","marker":"Irving (1985)"},{"why":"Establishes the Rural Hospitals property that all stable matchings cover the same agents, used for NP membership of MA and ∃PSM under agent addition.","marker":"Irving et al. (1987)"},{"why":"Confirms that all stable matchings in a roommates instance have the same size, used to verify perfectness in NP membership.","marker":"Gusfield and Irving (1989)"},{"why":"Supplies NP-completeness of CLIQUE and INDEPENDENT SET, the source problems for the three hardness reductions.","marker":"Garey and Johnson (1979)"},{"why":"Shows hardness of almost stable roommates matchings, yielding the CSR-DelAcc-∃SM entry in Table 1.","marker":"Abraham et al. (2006)"},{"why":"Shows inapproximability of size versus stability in marriage, yielding the CSM-DelAcc-∃PSM entry in Table 1.","marker":"Biró et al. (2010)"}],"fun_headline_variants":["Stable matching control: all 27 cases now classified","Control in stable matching: complexity fully mapped","NP-hard vs poly-time: stable matching control solved","Stable marriage & roommates: control complexity complete"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Stable matching control: all 27 cases now classified","Control in stable matching: complexity fully mapped","NP-hard vs poly-time: stable matching control solved","Stable marriage & roommates: control complexity complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000172,"raw_usage":{"total_tokens":1191,"prompt_tokens":775,"completion_tokens":416,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":391,"completion_tokens_details":{"reasoning_tokens":354}},"tokens_in":391,"tokens_out":416,"duration_ms":4526,"temperature":1.0,"reasoning_tokens":354,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T16:01:35.956774+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}