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 subcubic bipartite graphs, while Max-SMP can be solved in polynomal time for a bipartite graph G with a bipartition (X, Y) such that \(\mathrm{deg}_{G}(v)\le 2\) for any \(v\in X\). 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. We also consider some extensions to the case when G is a general/bipartite graph with edge weights.