Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure

We generalize the polynomial-time solvability of $k$-$\text{textsc}DiverseMinimums-tCuts$ (De Berg et al., ISAAC’23) to a wider class of combinatorial problems whose solution sets have a distributive lattice structure. We identify three structural conditions that, when met by a problem, ensure that a $k$-sized multiset of maximally-diverse solutions – measured by the sum of pairwise Hamming distances – can be found in polynomial time. We apply this framework to obtain polynomial time algorithms for finding diverse minimum $s$-$t$ cuts and diverse stable matchings. Moreover, we show that the framework extends to two other natural measures of diversity. Lastly, we present a simpler algorithmic framework for finding a largest set of pairwise disjoint solutions in problems that meet these structural conditions.