Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.02369 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We generalize the polynomial-time solvability of $k$-\textsc{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 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.