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

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

Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1119-1125. https://doi.org/10.24963/ijcai.2020/156

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. We consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. Our main contribution is 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.
Keywords:
Constraints and SAT: Constraint Optimization
Constraints and SAT: Constraint Satisfaction