# Finding Diverse Trees, Paths, and More

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2020.

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

- [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)
- [Patrol Security Game: Defending Against Adversary with Freedom in Attack Timing, Location, and Duration](https://mlsanity.com/paper/2410.15600/) (2024)

## Abstract (arXiv)

Mathematical modeling is a standard approach to solve many real-world problems and em diversity of solutions is an important issue, emerging in applying solutions obtained from mathematical models to real-world problems. Many studies have been devoted to finding diverse solutions. Baste et al. (Algorithms 2019, IJCAI 2020) recently initiated the study of computing diverse solutions of combinatorial problems from the perspective of fixed-parameter tractability. They considered problems of finding r solutions that maximize some diversity measures (the minimum or sum of the pairwise Hamming distances among them) and gave some fixed-parameter tractable algorithms for the diverse version of several well-known problems, such as sc Vertex Cover, sc Feedback Vertex Set, sc d-Hitting Set, and problems on bounded-treewidth graphs. In this work, we investigate the (fixed-parameter) tractability of problems of finding diverse spanning trees, paths, and several subgraphs. In particular, we show that, given a graph G and an integer r, the problem of computing r spanning trees of G maximizing the sum of the pairwise Hamming distances among them can be solved in polynomial time. To the best of the authors' knowledge, this is the first polynomial-time solvable case for finding diverse solutions of unbounded size.