Skip to content
DraconiticResearch
Search Sources API
186,123 studies31 sourcesUpdated 54 min ago
Peer-reviewedCC BY 4.0The Electronic Journal of Combinatorics

How to Secure General Acceptance for a Matching? - Inverse Popular Matchings

  • Erika Bérczi-Kovács
  • Eszter Szabó
Open at sourcePDFDOICite

Abstract

Inverse optimization problems focus on minimizing the adjustments made to the input data to achieve a desired outcome. Popular matchings are relaxations of stable matchings that prioritize the overall welfare of society over individual preferences. In this work, we aim to determine a minimum cost set of nodes in order to make a given matching popular by updating preferences at the chosen set. We show that the problem is NP-hard, even if the input matching is perfect or the graph is bipartite. If the desired matching is maximum size in the graph, we present a polynomial time algorithm to determine this minimum in bipartite graphs, and provide a dual characterization.

Related

  1. A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables
    Cheng Chi, Shuang Sun, Yan Wang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  2. Reconstruction-Aware Distribution Matching for Inverse Problems with Unpaired Data
    Thomas Ryckeboer, Giacomo Meanti, Julien Mairal
    HALPreprintCC BY-SA 4.0Full textStatisticsHALarXiv
  3. Flow Matching for Fast Posterior Sampling in Bayesian Inverse Problems
    Jan Blechschmidt, Oliver G. Ernst, Moritz Poguntke +1
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingStatisticsarXiv
  4. Physics-Guided Conditional Flow Matching with Energy Regularization for Robust PDE Inverse Problems
    Yongsheng Chen, Shuo Lu, Wei Guo +1
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv
  5. Finite inverse nodal problems for singular weighted Sturm--Liouville equations: variational selection and spectral matching
    Zhibo Cheng, Yuchao He, Sunan Wang +1
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@article{berczikovacs2026secure,
  title = {{How to Secure General Acceptance for a Matching? - Inverse Popular Matchings}},
  author = {Erika Bérczi-Kovács and Eszter Szabó},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  month = oct,
  doi = {10.37236/13747},
  url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p11},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - How to Secure General Acceptance for a Matching? - Inverse Popular Matchings
AU  - Erika Bérczi-Kovács
AU  - Eszter Szabó
PY  - 2026
DA  - 2026/10/09
JO  - The Electronic Journal of Combinatorics
DO  - 10.37236/13747
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p11
AB  - Inverse optimization problems focus on minimizing the adjustments made to the input data to achieve a desired outcome. Popular matchings are relaxations of stable matchings that prioritize the overall welfare of society over individual preferences. In this work, we aim to determine a minimum cost set of nodes in order to make a given matching popular by updating preferences at the chosen set. We show that the problem is NP-hard, even if the input matching is perfect or the graph is bipartite. If the desired matching is maximum size in the graph, we present a polynomial time algorithm to determine this minimum in bipartite graphs, and provide a dual characterization.
SN  - 1077-8926
ER  -