2026-07-20T11:15:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24919 2026-02-09T08:02:03Z ddc:004 open_access

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure de Berg, Mark López Martínez, Andrés Spieksma, Frits Diversity Lattice Theory Submodular Function Minimization We generalize the polynomial-time solvability of k-Diverse Minimum s-t Cuts (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, diverse stable matchings, and diverse market-clearing price vectors. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark de Berg and Andrés López Martínez and Frits Spieksma 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.11 urn:nbn:de:0030-drops-249197 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode