2024/11/05 by Kumabe, Soh · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2411.02845
Let D be a set family that is the solution domain of some combinatorial problem. The \emphmax-min diversification problem on D is the problem to select k sets from D such that the Hamming distance between any two selected sets is at least d. FPT algorithms parameterized by k+ℓ , where ℓ=maxD∈ D|D|, and k+d have been actively studied recently for several specific domains. This paper provides unified algorithmic frameworks to solve this problem. Specifically, for each parameterization k+ℓ and k+d, we provide an FPT oracle algorithm for the max-min diversification problem using oracles related to D. We then demonstrate that our frameworks provide the first FPT algorithms on several new domains D, including the domain of t-linear matroid intersection, almost 2-SAT, minimum edge s,t-flows, vertex sets of s,t-mincut, vertex sets of edge bipartization, and Steiner trees. We also demonstrate that our frameworks generalize most of the existing domain-specific tractability results. Our main technical breakthrough is introducing the notion of max-distance sparsifier of D, a domain on which the max-min diversification problem is equivalent to the same problem on the original domain D. The core of our framework is to design FPT oracle algorithms that construct a constant-size max-distance sparsifier of D. Using max-distance sparsifiers, we provide FPT algorithms for the max-min and max-sum diversification problems on D, as well as k-center and k-sum-of-radii clustering problems on D, which are also natural problems in the context of diversification and have their own interests.