Max-Distance Sparsification for Diversification and Clustering

We define the following $(-1,1)$-optimization oracle on $𝒟$ and the exact extension oracle on $𝒟$.

$\mathbf{(}\mathbf{-}\mathrm{𝟏}\mathbf{,}\mathrm{𝟏}\mathbf{)}$-Optimization Oracle on $𝒟$: Let $U$ be a finite set, $𝒟\subseteq 2^U$, and $w\in {\{-1,1\}}^U$ be a weight vector. Return a set $D\in 𝒟$ that maximizes ${\sum }_{e\in D}{w}_e$.

Exact Extension Oracle on $𝒟$: Let $U$ be a finite set, $r\in {\mathbb{Z}}_{\ge 0}$, $𝒟\subseteq 2^U$, and $C\in 𝒟$. Let $X,Y\subseteq U$ be two disjoint subsets of $U$. If there exists a set $D\in 𝒟$ such that $|D\mathrm{△}C|=r$, $X\subseteq D$, and $Y\cap D=\mathrm{\varnothing }$, return one such set. If no such set exists, return $\perp$.

When $C=\mathrm{\varnothing }$ and $X=\mathrm{\varnothing }$, we specifically call the exact extension oracle on $𝒟$ the exact empty extension oracle on $𝒟$.

Exact Empty Extension Oracle on $𝒟$: Let $U$ be a finite set, $r\in {\mathbb{Z}}_{\ge 0}$, $𝒟\subseteq 2^U$, and $Y\subseteq U$. If there exists a set $D\in 𝒟$ such that $|D|=r$ and $Y\cap D=\mathrm{\varnothing }$, return one such set. If no such set exists, return $\perp$.

Let ${𝒫}_{𝒟}$ be the max-min/max-sum diversification problem or the $k$-center/$k$-sum-of-radii clustering problem on $𝒟$. Our main result is FPT algorithms for solving ${𝒫}_{𝒟}$ using these oracles. We construct frameworks for both types of parameterizations, $k+\mathrm{\ell }$ and $k+d$. The result for the parameterization by $k+\mathrm{\ell }$ is as follows.

The result for the parameterization by $k+d$ is as follows.

On most domains $𝒟$, the exact empty extension oracle can be designed by almost the same way as an algorithm to extract a single solution from $𝒟$. For example, consider the case where $𝒟$ is the $\mathrm{\ell }$-path domain, i.e., a domain of sets of edges on paths of length $\mathrm{\ell }$. In this case, the exact empty extension oracle on $𝒟$ is equivalent to the problem of finding an $\mathrm{\ell }$-path in the graph obtained by removing all edges in $Y$ from the input. Combining Theorem 1 with this empirical fact, we can claim that, for most domains $𝒟$, the diversification and clustering problems parameterized by $k+\mathrm{\ell }$ on $𝒟$ are as easy as determining the non-emptiness of $𝒟$.

To demonstrate that Theorem 1 yields existing tractability results, we design the oracles for the domains of the vertex cover [7, 8], $t$-hitting set [7], feedback vertex set [7], and common independent set of two matroids [17, 22]. We also apply our framework on new domains, $t$-represented linear matroid intersection, almost $2$-SAT, and independent set on subgraph-closed IS-FPT graph classes. Here, a graph class is subgraph-closed IS-FPT if it is closed under taking subgraphs and the problem of finding independent set of size $\mathrm{\ell }$ is FPT parameterized by $\mathrm{\ell }$. The following theorem summarizes our results, where the precise definitions of each domain are given in the full version.

Theorem 1 also generalizes existing frameworks for diversification. Baste et al. [8] provided an algorithmic framework for diversification using a loss-less kernel [9, 10], which, roughly speaking, is a kernel that completely preserves the information of the solution space. Since loss-less kernels are known for very limited domains, their framework requires very strong assumptions. Our framework has broader applicability than theirs because it relies on a weaker oracle, as the exact empty extension oracle can be constructed using a loss-less kernel. Hanaka et al. [26] developed a color-coding-based framework for diversification. The oracle they use can be regarded as the exact empty extension oracle with an additional colorfulness constraint. Our framework again has broader applicability than theirs because our oracle can be constructed using theirs. Moreover, our framework also treats clustering problems, which these two do not.

FPT algorithms for the max-min diversification problems on $𝒟$ parameterized by $k+d$ are known for the cases where $𝒟$ is the family of matroid bases [17, 22], perfect matchings [22], and shortest paths [23]. The result for the perfect matchings is later extended to the matchings of specified size, not necessarily perfect [17]. Additionally, for the cases where $𝒟$ is the family of interval schedulings [26] and the longest common subsequences of an absolute constant number of strings [31], FPT algorithms parameterized by $k+\mathrm{\ell }$ are known. Both of these two can be generalized to the domain of dynamic programming problems, which we define in the full version. Furthermore, the problem of finding a pair of a branching and an in-branching such that the Hamming distance between them is at least $d$ is investigated as the name of $d$-distinct branchings problem [5, 6, 25], which admits FPT algorithm parameterized by $d$. This problem can naturally be extended to the case that selects $k_1$ branchings and $k_2$ in-branching, rather than one each. We give FPT algorithms parameterized by $k+d$ for all those problems, where $k=k_1+k_2$ for the extended version of $d$-distinct branchings problem. We also give FPT algorithms on domains of minimum edge $s,t$-flows, Steiner trees, vertex sets of $s,t$-mincut, and vertex sets of edge bipartization, which are domains where no FPT algorithm for the max-min diversification problem is previously known. Remark that the domain of shortest paths [23] is the special case of the minimum edge $s,t$-flow domain and the minimum Steiner tree domain. The following theorem summarizes our results, where the precise definitions of each domain are given in the full version.

Eiben et al. [17] provided a technique called determinantal sieving, which is a general tool to give and speed up parameterized algorithms, including that for diversification problems. Particularly, they provided a framework to solve the diversification problem by using an oracle that, roughly speaking, counts the number of solutions modulo $2$. Using their framework, they improved the running times of FPT algorithms for max-min diversification problems on matchings and matroid bases, as well as the $d$-distinct branchings problem. Although not stated explicitly, their framework seems to yield FPT algorithms parameterized by $k+d$ when $𝒟$ is the dynamic programming domain, thereby improving the parameterizations in the results of [26] and [31], respectively, as well as the extended version of $d$-distinct branchings problems. We are not sure whether our framework generalizes theirs, that is, whether our oracle can be constructed using their oracle. However, we strongly believe that our framework has broader applicability because their framework assumes counting oracles, which is often hard even modulo $2$. In contrast, our framework uses optimization-type oracles, which are generally more tractable than counting. Indeed, our framework provides an FPT algorithm with the same parameterization for every domain which they explicitly considered. Moreover, we do not think their framework can give an FPT algorithm for the max-min diversification problem on the domains of minimum edge $s,t$-flows, vertex sets of minimum $s,t$-cut, and vertex sets of edge bipartization. Furthermore, our framework can be applied not only to diversification problems but also to clustering problems.

We begin by defining the max-distance sparsifiers. The key for Theorem 1 is designing the following $k$-max-distance sparsifier of $𝒟$.

Similarly, the key for Theorem 2 is designing the following $d$-limited $k$-max-distance sparsifier of $𝒟$.

The difference between the two sparsifiers is that the domain of $(z_1,\mathrm{\dots },z_k)$ is ${\mathbb{Z}}_{\ge 0}^k$ in the former case, while it is ${\{0,\mathrm{\dots },d\}}^k$ in the latter. By definition, any $k$-max-distance sparsifier is also a $d$-limited $k$-max-distance sparsifier for any $d\in {\mathbb{Z}}_{\ge 0}$. We can prove that given a $d$-limited $(k-1)$-max-distance sparsifier of $𝒟$ with size bounded by a constant that depends only on $k+d$, we can construct FPT algorithms parameterized by $k+d$ for the max-min/max-sum diversification problems on $𝒟$. Similarly, we can prove that given a $(d+1)$-limited $k$-max-distance sparsifier of $𝒟$ with size bounded by a constant that depends only on $k+d$, we can construct FPT algorithms parameterized by $k+d$ for the $k$-center/$k$-sum-of-radii clustering problems on $𝒟$. Therefore, to prove Theorems 1 and 2, it suffices to construct FPT oracle algorithms for designing $k$-max-distance sparsifiers and $d$-limited $k$-max-distance sparsifiers, respectively.

The remaining task towards Theorem 1 is to provide an FPT algorithm parameterized by $k+\mathrm{\ell }$ that constructs a $k$-max-distance sparsifier of $𝒟$ with size bounded by a constant that depends only on $k+\mathrm{\ell }$. The key lemma toward this is that, if $𝒦$ contains a sufficiently large sunflower (see Section 3 for the definition) consisting of sets of the same size, then we can safely remove one of them from $𝒦$ while preserving the property that $𝒦$ is a $k$-max-distance sparsifier (actually, for the sake of simplifying the framework, we prove a slightly stronger statement). Starting with $𝒦=𝒟$ and exhaustively removing such sets leads to a $𝒦$ that is still a $k$-max-distance sparsifier of $𝒟$, and by using the well-known sunflower lemma (Lemma 13), its size is bounded by a constant.

However, this observation is still not sufficient to obtain an FPT algorithm. The reason is that $𝒟$ generally has exponential size, and removing sets one by one would require an exponential number of steps. Instead, our algorithm starts with $𝒦=\mathrm{\varnothing }$ and exhaustively adds sets of $𝒟$ to $𝒦$ until $𝒦$ becomes a $k$-max-distance sparsifier. In this way, the number of steps is bounded by a constant. The remaining task is to choose a set to be added at each step. For this task, we design an FPT algorithm using constant number of calls of the exact empty extension oracle.

The algorithm in the previous section alone is insufficient to prove Theorem 2 since $\mathrm{\ell }$ is unbounded and the sunflower-lemma-based bound for the number of steps cannot be used. Our algorithm divides $𝒟$ into at most $k$ clusters, computes a $d$-limited $k$-max-distance sparsifier for each cluster, and outputs their union. Let $p>2d$ be a constant that depends only on $k+d$. We first find $𝒞\subseteq 𝒟$ satisfying the following properties: (i) $|𝒞|\le k$, (ii) for all distinct $C,C^{\prime }\in 𝒞$, $|C\mathrm{△}{C}^{\prime }|>2d$, and (iii) for all $D\in 𝒟$, there exists $C\in 𝒞$ such that $|D\mathrm{△}C|\le p$. If such a family does not exist, a trivial $d$-limited $k$-max-distance sparsifier of $𝒟$ will be found, and we output it and terminate.

We provide an algorithm for computing $𝒞$. Our algorithm starts with $𝒞=\mathrm{\varnothing }$ and exhaustively adds sets in $𝒟$ to $𝒞$ until $𝒞$ satisfies the above conditions or its size exceeds $k$. To choose the elements to be added, we randomly sample $w\in {\{-1,1\}}^U$ and call a $(-1,1)$-optimization oracle. We can prove for sufficiently large constant $p$ that if there exists $D\in 𝒟$ such that $|D\mathrm{△}C|>p$ for any $C\in 𝒞$, with a constant probability, the $(-1,1)$-optimization oracle will find a $D\in 𝒟$ such that $|D\mathrm{△}C|>2d$ for any $C\in 𝒞$. Thus, if $𝒞$ does not meet the conditions, by calling the $(-1,1)$-optimization oracle a sufficient number of times, we can find a set to add to $𝒞$ with high probability.

Here, we provide an algorithm for computing a $d$-limited $k$-max-distance sparsifier of $𝒟$ using $𝒞$. For each cluster ${𝒟}_C:=\{D\in 𝒟:|D\mathrm{△}C|\le p\}$, let ${𝒟}_C^{\ast }:=\{D\mathrm{△}C:D\in {𝒟}_C\}$. The algorithm computes a $k$-max-distance sparsifier of each ${𝒟}_C^{\ast }$ and outputs their union. For technical reasons, we actually compute a slightly more general object, but we will not delve into the details here. Since each ${𝒟}_C^{\ast }$ consists only of sets whose size is at most $p$, the $k$-max-distance sparsifier of ${𝒟}_C^{\ast }$ can be constructed using the algorithm in Section 1.3.2. The exact empty extension oracle on ${𝒟}_C^{\ast }$ corresponds to the exact extension oracle on $𝒟$.

Here, we note the difference between our framework and that used by Fomin et al. [22] and Funayama et al. [23] to provide FPT algorithms for the max-min diversification problem on $𝒟$ when $𝒟$ is the family of perfect matchings and shortest paths, respectively. Their algorithms also start by dividing $𝒟$ into clusters. However, their algorithms perform stricter clustering than ours. Specifically, in their clustering, clusters ${𝒟}_C$ corresponding to different $C\in 𝒞$ must be well-separated. In contrast, we allow clusters to overlap. This simplifies the clustering step compared to their approach at the cost of a more challenging task afterward. We resolve this more challenging task by introducing and designing the $d$-limited $k$-max-distance sparsifier.