Finding Diverse Trees, Paths, and More

Authors

  • Tesshu Hanaka Chuo University
  • Yasuaki Kobayashi Kyoto University
  • Kazuhiro Kurita National Institute of Informatics
  • Yota Otachi Nagoya University

Keywords:

Other Foundations of Constraint Satisfaction

Abstract

Mathematical modeling is a standard approach to solve many real-world problems and 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 Vertex Cover, Feedback Vertex Set, d-Hitting Set}, and problems on bounded-treewidth graphs. In this work, we further 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.

Downloads

Published

2021-05-18

How to Cite

Hanaka, T., Kobayashi, Y., Kurita, K., & Otachi, Y. (2021). Finding Diverse Trees, Paths, and More. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3778-3786. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16495

Issue

Section

AAAI Technical Track on Constraint Satisfaction and Optimization