# Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory

arXiv: https://arxiv.org/abs/1903.07410 · HTML: https://mlsanity.com/paper/1903.07410/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2019.

## Built on by (most cited first, 9 of 9)

- [Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems](https://mlsanity.com/paper/2402.02190/) (2024)
- [Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study](https://mlsanity.com/paper/2112.05403/) (2021)
- [DiversiTree: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems](https://mlsanity.com/paper/2204.03822/) (2022)
- [Diversity in Kemeny Rank Aggregation: A Parameterized Approach](https://mlsanity.com/paper/2105.09413/) (2021)
- [Bridging the Gap between Structural and Semantic Similarity in Diverse Planning](https://mlsanity.com/paper/2310.01520/) (2023)
- [From Width-Based Model Checking to Width-Based Automated Theorem Proving](https://mlsanity.com/paper/2205.10995/) (2022)
- [Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing](https://mlsanity.com/paper/2301.05146/) (2023)
- [Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential](https://mlsanity.com/paper/2407.08963/) (2024)
- [Representative Sets in Propositional Abduction](https://mlsanity.com/paper/2607.21183/) (2026)

## Abstract (arXiv)

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.