Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings

Birkhoff’s fundamental theorem on distributive lattices states that for every distributive lattice LL there is a poset PLPL whose lattice of down-sets is order-isomorphic to LL. Let G(L)G(L) denote the cover graph of LL. In this paper, we consider the following problems: suppose we are simply given PLPL. How do we compute the eccentricity of an element of LL in G(L)G(L)? How about a center and the radius of G(L)G(L)? While eccentricity, center and radius computations have long been studied for various classes of graphs, our problems are different in that we are not given the graph explicitly; instead, we only have a structure that implicitly describes the graph. By making use of the comparability graph of PLPL, we show that all the said problems can be solved efficiently. One of the implications of these results is that a center stable matching, a kind of fair stable matching, can be computed in polynomial time.