Stable Matchings in Trees

摘要

The maximum stable matching problem (Max-SMP) and the minimum stable matching problem (Min-SMP) have been known to be NP-hard for bipartite graphs, while Max-SMP can be solved in polynomial time for a bipartite graph G with deg_G(v) ≤ 2 for any v ∈ X, where (X, Y) is a bipartition of G. This paper shows that both Max-SMP and Min-SMP can be solved in linear time for trees. This is the first polynomially solvable case for Min-SMP, as far as the authors know.