DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.11

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure

Authors: Mark de Berg, Andrés López Martínez, and Frits Spieksma

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

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.

Cite as

Mark de Berg, Andrés López Martínez, and Frits Spieksma. Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2025.11,
  author =	{de Berg, Mark and L\'{o}pez Mart{\'\i}nez, Andr\'{e}s and Spieksma, Frits},
  title =	{{Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.11},
  URN =		{urn:nbn:de:0030-drops-249197},
  doi =		{10.4230/LIPIcs.ISAAC.2025.11},
  annote =	{Keywords: Diversity, Lattice Theory, Submodular Function Minimization}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.24

Finding Diverse Minimum s-t Cuts

Authors: Mark de Berg, Andrés López Martínez, and Frits Spieksma

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

Recently, many studies have been devoted to finding diverse solutions in classical combinatorial problems, such as Vertex Cover (Baste et al., IJCAI'20), Matching (Fomin et al., ISAAC'20) and Spanning Tree (Hanaka et al., AAAI'21). Finding diverse solutions is important in settings where the user is not able to specify all criteria of the desired solution. Motivated by an application in the field of system identification, we initiate the algorithmic study of k-Diverse Minimum s-t Cuts which, given a directed graph G = (V, E), two specified vertices s,t ∈ V, and an integer k > 0, asks for a collection of k minimum s-t cuts in G that has maximum diversity. We investigate the complexity of the problem for two diversity measures for a collection of cuts: (i) the sum of all pairwise Hamming distances, and (ii) the cardinality of the union of cuts in the collection. We prove that k-Diverse Minimum s-t Cuts can be solved in strongly polynomial time for both diversity measures via submodular function minimization. We obtain this result by establishing a connection between ordered collections of minimum s-t cuts and the theory of distributive lattices. When restricted to finding only collections of mutually disjoint solutions, we provide a more practical algorithm that finds a maximum set of pairwise disjoint minimum s-t cuts. For graphs with small minimum s-t cut, it runs in the time of a single max-flow computation. These results stand in contrast to the problem of finding k diverse global minimum cuts - which is known to be NP-hard even for the disjoint case (Hanaka et al., AAAI'23) - and partially answer a long-standing open question of Wagner (Networks 1990) about improving the complexity of finding disjoint collections of minimum s-t cuts.

Cite as

Mark de Berg, Andrés López Martínez, and Frits Spieksma. Finding Diverse Minimum s-t Cuts. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2023.24,
  author =	{de Berg, Mark and L\'{o}pez Mart{\'\i}nez, Andr\'{e}s and Spieksma, Frits},
  title =	{{Finding Diverse Minimum s-t Cuts}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.24},
  URN =		{urn:nbn:de:0030-drops-193267},
  doi =		{10.4230/LIPIcs.ISAAC.2023.24},
  annote =	{Keywords: S-T MinCut, Diversity, Lattice Theory, Submodular Function Minimization}
}

Search Results

Documents authored by López Martínez, Andrés

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure

Abstract

Cite as

Finding Diverse Minimum s-t Cuts

Abstract

Cite as

Thanks for your feedback!

Could not send message