A General Framework for Finding Diverse Solutions via Network Flow and Its Applications

In modeling real-world problems as optimization problems, many factors are inevitably omitted from the model due to the limited information and the need for tractability. Consequently, finding a single optimal solution to the optimization problem may not be enough. Motivated by this issue, developing algorithms to find diverse multiple solutions has recently gained attention in the field of combinatorial optimization [3, 4, 7, 8, 9, 10, 11, 15, 17].

We formally define the $k$-diverse problem for a positive integer $k$. Let $d_{\mathrm{div}}$ be a function that measures the “diversity” for a $k$-tuple of subsets of some arbitrary fixed ground set $E$. For a combinatorial problem Prob, the $k$-diverse problem of Prob asks, given an instance $𝐈$ of Prob, to find a $k$-tuple $(S_1,S_2,\mathrm{\dots },S_k)$ of solutions of $𝐈$ that maximizes the fixed measure $d_{\mathrm{div}}$. Typical examples of the measure of diversity include the following:

If we use $d_{\mathrm{sum}}$ (resp. $d_{\mathrm{cov}}$) as the measure, then we refer to the corresponding $k$-diverse problem as Sum-$k$-Diverse (resp. Cov-$k$-Diverse).

In this paper, we present a general framework for efficiently finding diverse solutions to combinatorial optimization problems. Namely, we focus on Sum-$k$-Diverse/Cov-$k$-Diverse of a combinatorial problem Prob having two properties (S) and (R) introduced below. The first property (S) states that all solutions of each instance of Prob have the same size:

(S) For any instance $𝐈$ of Prob, there exist a finite ground set $E$ and a positive integer $q$ such that the family $𝒮(𝐈)$ of solutions of $𝐈$ consists of subsets of $E$ of size $q$.

The second property (R) indicates that $𝒮(𝐈)$ admits a lattice structure and $𝒮(𝐈)$ has a compact representation using the lattice. To state this property precisely, we first introduce some notation. Let $(P,⪯)$ be a finite poset with minimum element $\perp$ and maximum element $\top$. For such a poset $P$, let $P^{\ast }$ denote the poset obtained from $P$ by removing $\perp$ and $\top$. For a map $r:E\to P^2$ that assigns each element $e\in E$ to an ordered pair

of elements in $P$ with $e^{+}⪯e^{-}$, we define a set ${sup}_r(I)$ by

for each ideal $I\in ℐ(P^{\ast })$. Here, an ideal of a poset is a subset $I\subseteq P^{\ast }$ that is closed downward under $⪯$, that is, $y⪯x\in I$ implies $y\in I$ for all $x,y\in P^{\ast }$, and $ℐ(P^{\ast })$ denotes the family of ideals of the poset $P^{\ast }$. With this notation, the property (R) can be stated as follows:

(R) For any instance $𝐈$ of Prob, there exist a finite poset $(P,⪯)$ with distinct minimum element $\perp$ and maximum element $\top$ and a map $r:E\to P^2$ given by $e\mapsto (e^{+},e^{-})$ with $e^{+}⪯e^{-}$ such that

We refer to a map $r$ appearing in the property (R) as a reduction map. In other words, the property (R) requires that every instance $𝐈$ of Prob admits a reduction map $r$ such that ${sup}_r$ forms a surjection from the family $ℐ(P^{\ast })$ of ideals of $P^{\ast }$ to the family $𝒮(𝐈)$ of solutions of $𝐈$. A toy example of a reduction map is found in Example 1.

We show that if the problem Prob has the properties (S) and (R), then $𝒮(𝐈)$ with a partial order defined from a reduction map forms a distributive lattice (see Theorem 11).

Our framework exploits network flow techniques to efficiently compute diverse solutions. To utilize them, we will construct a directed acyclic graph (DAG) to represent a poset. Here, we say that a DAG $G$ represents a poset $(P,⪯)$ with distinct minimum element $\perp$ and maximum element $\top$ if the vertex set of $G$ is $P$, $\top$ is a source and $\perp$ is a sink in $G$, and for any $u,v\in P^{\ast }$, there is a $u$-$v$ path in $G$ if and only if $u⪰v$.

Our main result is stated as follows. We focus on deterministic algorithms in this paper.

We obtain Theorem 2 via the reduction of Sum-$k$-Diverse/Cov-$k$-Diverse of Prob to a classical network flow problem, called the minimum cost flow problem. This enables us to utilize the state-of-the-art (deterministic) algorithm [25] for the minimum cost flow problem in solving Sum-$k$-Diverse/Cov-$k$-Diverse of Prob. To this end, we introduce an intermediate problem called the minimum $k$-potential problem, and reduce the $k$-diverse problems to the minimum $k$-potential problem. Then we further reduce the minimum $k$-potential problem to the minimum cost flow problem by utilizing the idea of Ahuja, Hochbaum, and Orlin [1], who dealt with a more general problem. Our novelty is to identify the properties (S) and (R) as a sufficient condition to reduce the $k$-diverse problem to the minimum $k$-potential problem.

We also develop a reduction of Sum-$k$-Diverse/Cov-$k$-Diverse of Prob to the maximum $s$-$t$ flow problem via the minimum $k$-potential problem. We describe this in the full version. While the running-time of this reduction is slightly worse than that of the reduction to the minimum cost flow problem, its practical performance may be superior thanks to the simplicity of the reduction and the maximum $s$-$t$ flow problem.

As applications of our framework, we demonstrate that two classical combinatorial problems, Unweighted Minimum $s$-$t$ Cut and Stable Matching, have properties (S) and (R). Here, Unweighted Minimum $s$-$t$ Cut is to find an $s$-$t$ cut of a given digraph $G$ with the minimum size, and Stable Matching is to find a matching of two parties such that no unmatched pair both prefer each other to their current partners (see Sections 5.2 and 5.3 for the definitions). In fact, both problems are known to possess a distributive lattice structure. By applying Theorem 2 to Sum-$k$-Diverse/Cov-$k$-Diverse of these problems, we obtain the following results.

The polynomial-time solvability of Sum-$k$-Diverse/Cov-$k$-Diverse of Unweighted Minimum $s$-$t$ Cut has already been shown by De Berg, Martínez, and Spieksma [7]. Very recently, independently of our work, the same authors [8] developed a framework for solving Sum-$k$-Diverse/Cov-$k$-Diverse of a combinatorial problem having a certain property, and they show that Sum-$k$-Diverse/Cov-$k$-Diverse of Stable Matching can be solved in polynomial time. Both of their tractability results in [7, 8] are based on the polynomial-time solvability of the submodular function minimization (SFM) [2, 12]. Even if we use the state-of-the-art algorithm for SFM, given in [18], the running-time of their algorithms is (polynomial but) not very fast; it takes $O(k^5{n}^5)$ time for Sum-$k$-Diverse/Cov-$k$-Diverse of Unweighted Minimum $s$-$t$ Cut, and $O(k^5{n}^9)$ time for that of Stable Matching. As in Theorem 3, our proposed algorithms for Sum-$k$-Diverse/Cov-$k$-Diverse of Unweighted Minimum $s$-$t$ Cut/Stable Matching are much faster, thanks to recent advance in network flow algorithms. Moreover, we show that the framework of [8] for Sum-$k$-Diverse and Cov-$k$-Diverse can be captured by our framework (see Section 5.4). This allows us to improve the time complexity.

Due to the space limitation, all the proofs (marked with $\star$) are omitted, and they can be found in the full version.

Let $\mathbb{Z}$, ${\mathbb{Z}}_{+}$, $ℝ$, and ${ℝ}_{+}$ denote the set of integers, nonnegative integers, real numbers, and nonnegative real numbers, respectively. For a nonnegative integer $k$, let $[k]≔\{1,2,\mathrm{\dots },k\}$ and $[0,k]≔\{0,1,\mathrm{\dots },k\}$. The symmetric difference $(S\setminus T)\cup (T\setminus S)$ of sets $S$ and $T$ is denoted by $S\mathrm{△}T$. For a finite set $E$ and a nonnegative integer $q\in {\mathbb{Z}}_{+}$, let $\left(\genfrac{}{}{0pt}{}{E}{q}\right)$ denote the family of all subsets of $E$ of size $q$, i.e., $\left(\genfrac{}{}{0pt}{}{E}{q}\right)≔\{S\subseteq E\mid |S|=q\}$. For any finite set $E$, element $e\in E$, and $k$-tuple $𝐒=(S_1,S_2,\mathrm{\dots },S_k)$ of subsets of $E$, the multiplicity of $e$ with respect to $𝐒$, denoted by ${\mu }_e(𝐒)$, is defined as the number of subsets $S_i$ that contain $e$, i.e., ${\mu }_e(𝐒)≔|\{i\in [k]\mid e\in S_i\}|$.

In this section, we provide a reduction from the $k$-diverse problem of Prob to the minimum $k$-potential problem, which we introduce later.

In Sum-$k$-Diverse and Cov-$k$-Diverse of Prob, we can regard the diversity measures $d_{\mathrm{sum}}$ and $d_{\mathrm{cov}}$ as the functions over ${(𝒮(𝐈))}^k$ for each instance $𝐈$ of Prob. Since $𝒮(𝐈)\subseteq \left(\genfrac{}{}{0pt}{}{E}{q}\right)$ holds by the property (S), we have ${\sum }_{e\in E}{\mu }_e(𝐒)={\sum }_{i=1}^k|S_i|=kq$ for any $𝐒=(S_1,S_2,\mathrm{\dots },S_k)\in {(𝒮(𝐈))}^k$, which is a constant. Hence, the functions $d_{\mathrm{sum}}$ and $d_{\mathrm{cov}}$ are representable as

for each $𝐒\in {(𝒮(𝐈))}^k$. Thus, the problems Sum-$k$-Diverse and Cov-$k$-Diverse of Prob, namely, the problems of maximizing the functions $d_{\mathrm{sum}}$ and $d_{\mathrm{cov}}$ over ${(𝒮(𝐈))}^k$, are equivalent to those of minimizing

respectively.

By using the concept of discrete convex functions, we can uniformly handle these functions $d_{\mathrm{sum}}^{\ast }$ and $d_{\mathrm{cov}}^{\ast }$ as follows. A function $\phi :\mathbb{Z}\to \mathbb{Z}$ is said to be discrete convex [20, Chapter 3.4] if $\phi (x-1)+\phi (x+1)\ge 2\phi (x)$ for all $x\in \mathbb{Z}$, and said to be non-decreasing on ${\mathbb{Z}}_{+}$ if $\phi (x)\le \phi (x+1)$ for all $x\in {\mathbb{Z}}_{+}$. For a discrete convex function $\phi$ with $\phi (0)=0$ that is non-decreasing on ${\mathbb{Z}}_{+}$, we define

for $𝐒\in {(𝒮(𝐈))}^k$. Since the functions $x\mapsto x^2$ and $x\mapsto \max \{0,x-1\}$ are discrete convex functions that are non-decreasing on ${\mathbb{Z}}_{+}$ and satisfy $0\mapsto 0$, both of $d_{\mathrm{sum}}^{\ast }$ and $d_{\mathrm{cov}}^{\ast }$ admit such representations.

Our framework can be applied to the $k$-diverse problem with respect to the diversity measure of the form

for $𝐒\in {(𝒮(𝐈))}^k$, where $\phi$ is a discrete convex function with $\phi (0)=0$ that is non-decreasing on ${\mathbb{Z}}_{+}$. In the following, we consider the $k$-diverse problem with respect to $d_{\phi }$ of Prob, or equivalently, the problem of minimizing $d_{\phi }^{\ast }$ over ${(𝒮(𝐈))}^k$ for a discrete convex function $\phi$.

We then introduce the minimum $k$-potential problem, to which we reduce the problem of minimizing $d_{\phi }^{\ast }$ later. Let $G=(V,A)$ be a DAG having unique source vertex $\top$ and sink vertex $\perp$ with $\top \ne \perp$. We refer to an assignment $p:V\to {\mathbb{Z}}_{+}$ of integers to vertices as a $k$-potential if $p$ satisfies the following conditions:

(P1) $p(\perp )=k$ and $p(\top )=0$.

(P2) $0\le p(v)\le k$ for each $v\in V$.

(P3) $p$ is monotone non-increasing with respect to $A$, i.e., $p(u)\le p(v)$ for each $(u,v)\in A$.
In the minimum $k$-potential problem, we are given a DAG $G=(V,A)$ with unique source $\top$ and sink $\perp$, an arc weight $w:A\to {\mathbb{Z}}_{+}$, and a discrete convex function $\phi :\mathbb{Z}\to \mathbb{Z}$ with $\phi (0)=0$ that is non-decreasing on ${\mathbb{Z}}_{+}$, and asked to find a $k$-potential $p$ of $G$ that minimizes

We note that the function $H$ does not change even if we remove vertices $v\in V\setminus \{\perp ,\top \}$ with ${\mathrm{\Delta }}^{+}(v)={\mathrm{\Delta }}^{-}(v)=\mathrm{\varnothing }$, called isolated vertices, from $G$.

Finally, we reduce, for an instance $𝐈$ of Prob, the problem of minimizing $d_{\phi }^{\ast }$ over ${(𝒮(𝐈))}^k$ to the minimum $k$-potential problem by utilizing the property (R). Let $(P,⪯)$ be a poset having minimum element $\perp$ and maximum element $\top$, and let $r:E\to P^2$ be a reduction map as in the property (R). Then, we construct a DAG $G_{𝐈}$ whose vertex set is $V=P$ and whose arc set is $A=A_P\cup A_E$, where $A_P$ is an arc set such that a DAG $(P,A_P)$ represents the poset $(P,⪯)$, and $A_E≔\{(e^{-},e^{+})\mid e\in E\}$. The resulting $G_{𝐈}$ is still a DAG that represents $P$ and has unique source $\top$ and sink $\perp$; each arc $(e^{-},e^{+})\in A_E$ is compatible with the partial order $⪯$ of $P$, since $e^{-}⪰e^{+}$. An arc weight $w_{𝐈}:A\to {\mathbb{Z}}_{+}$ is defined by $w_{𝐈}(a)≔|\{e\in E\mid a=(e^{-},e^{+})\}|$ for $a\in A$. Note that $w_{𝐈}(a)=0$ for each $a\in A\setminus A_E$. We set $\phi$, which satisfies the non-decreasing property on ${\mathbb{Z}}_{+}$ and $\phi (0)=0$, as the input discrete convex function of the minimum $k$-potential problem. Then, the triple $(G_{𝐈},w_{𝐈},\phi )$ is an instance of the minimum $k$-potential problem; its construction time is $|E|$.

Intuitively, any $k$-potential represents the direct sum of $k$ ideals $I_1,I_2,\mathrm{\dots },I_k\in ℐ(P^{\ast })$ as a multiset. Conversely, for any $k$ ideals in $ℐ(P^{\ast })$, there exists a $k$-potential that represents their direct sum as a multiset. Furthermore, by the property (R), each ideal of $P^{\ast }$ corresponds to a solution of $𝐈$ via ${sup}_r$. The following lemma verifies this intuition.

Lemma 5 immediately implies that we can construct in $O(|E|+kq)$ time a minimizer ${𝐒}_p$ of $d_{\phi }^{\ast }$ over ${(𝒮(𝐈))}^k$ from a minimum $k$-potential $p$ for the instance $(G_{𝐈},w_{𝐈},\phi )$ of the minimum $k$-potential problem. Therefore, we obtain the following.

Here, we reduce the minimum $k$-potential problem to the minimum cost flow problem.

Let us first recall the minimum cost flow problem (see e.g., [19, Chapter 9] and [23, Chapter 12] for details). In this problem, we are given a digraph $G=(V,A)$, arc cost $\gamma :A\to \mathbb{Z}$, arc capacity $c:A\to {\mathbb{Z}}_{+}$, and vertex demand $d:V\to \mathbb{Z}$, and asked to find a feasible flow $f:A\to {\mathbb{Z}}_{+}$ (i.e., $f(a)\le c(a)$ for $a\in A$) that minimizes ${\sum }_{a\in A}\gamma (a)f(a)$ subject to $\partial f(v)=d(v)$ for all $v\in V$. An optimal solution of the minimum cost flow problem is called a minimum cost flow. We denote by $T_{\mathrm{mcf}}(n,m,\mathrm{\Gamma },C,D)$ the time required to solve the minimum cost flow problem for a network of $n$ vertices and $m$ arcs with cost at most $\mathrm{\Gamma }$ in absolute values, capacity at most $C$, and a demand vector with values at most $D$ in absolute values. Using the state-of-the-art algorithm for the minimum cost flow problem given in [25], we have $T_{\mathrm{mcf}}(n,m,\mathrm{\Gamma },C,D)=O(m^{1+o(1)}\log (\max \{C,D\})\log \mathrm{\Gamma })$.

Our reduction follows the work by Ahuja, Hochbaum, and Orlin [1], who dealt with a more general problem called the convex cost integer dual network flow problem. They showed that the Lagrangian dual of their problem is reduced to the minimum cost flow problem. For the complexity analysis, we explicitly provide the reduction in our case and the construction of a minimum $k$-potential from a minimum cost flow.

For a discrete convex function $\psi :\mathbb{Z}\to \mathbb{Z}$, an integer $x\in \mathbb{Z}$ is called a breakpoint of $\psi$ if $\psi (x+1)+\psi (x-1)>2\psi (x)$, i.e., the left slope $\psi (x)-\psi (x-1)$ and right slope $\psi (x+1)-\psi (x)$ of $\psi$ at $x$ are different. We can observe that, for each $x\in \mathbb{Z}$, the left slope of $\psi$ at $x$ is at most the right slope of $\psi$ at $x$. Let $B(\psi )$ denote the set of breakpoints of $\psi$.

Let $(G=(V,A),w:A\to {\mathbb{Z}}_{+},\phi :\mathbb{Z}\to \mathbb{Z})$ be an instance of the minimum $k$-potential problem. We define $B_k(\phi )≔\left(B(\phi )\cap [0,k]\right)\cup \{0,k\}$ and suppose that $B_k(\phi )=\{b_0,b_1,\mathrm{\dots },b_z\}$ with . Let $s_i^{-}$ (resp. $s_i^{+}$) denote the left (resp. right) slope of $\phi$ at $b_i\in B(\phi )\cap [k-1]$; note that . We set $M\in {\mathbb{Z}}_{+}$ as a sufficiently large integer satisfying $M>H(p)$ for any $k$-potential $p$ of $G$, e.g., $M={\sum }_{a\in A}w(a)\phi (k)+1$.

We construct an instance of the minimum cost flow problem. The vertex set of the input digraph $\overline{G}$ is $\overline{V}≔V\cup \{0\}$. We set the arc set $\overline{A}$ of $\overline{G}$, arc cost $\overline{\gamma }:\overline{A}\to \mathbb{Z}$, and capacity $\overline{c}:\overline{A}\to {\mathbb{Z}}_{+}$ by creating

• $\mathrm{■}$

  $|B_k(\phi )|=z+1$ copies of each $a\in A$ satisfying $w(a)>0$ with costs $b_0,b_1,\mathrm{\dots },b_{z-1},b_z$ and capacities $w(a)s_1^{-}+M,w(a)(s_1^{+}-s_1^{-}),w(a)(s_2^{+}-s_2^{-}),\mathrm{\dots },w(a)(s_{z-1}^{+}-s_{z-1}^{-}),M-w(a)s_{z-1}^{+}$, respectively,

• $\mathrm{■}$

  two copies of each $a\in A$ satisfying $w(a)=0$ or each $a=(0,u)$ for $u\in V\setminus \{\perp ,\top \}$ with costs $0,k$ and capacities $M,M$, respectively,

• $\mathrm{■}$

  arcs $(0,\perp )$ and $(0,\top )$ with cost $k$ and $0$, respectively, and capacity $2M$.

The vertex demand $\overline{d}:\overline{V}\to \mathbb{Z}$ is set as $\overline{d}(v)≔M(|{\mathrm{\Delta }}_{G^{\prime }}^{+}(v)|-|{\mathrm{\Delta }}_{G^{\prime }}^{-}(v)|)$ for each $v\in \overline{V}$, where $G^{\prime }≔(\overline{V},A^{\prime })$ and $A^{\prime }≔A\cup \{(0,v)\mid v\in V\}$.

Let $f^{\ast }$ be a minimum cost flow of the resulting instance $(\overline{G},\overline{\gamma },\overline{c},\overline{d})$. Then we construct the residual graph ${\overline{G}}_{f^{\ast }}$ of $\overline{G}$ with respect to $f^{\ast }$, and set the arc length $\mathrm{\ell }$ of ${\overline{G}}_{f^{\ast }}$ as $\mathrm{\ell }(a)≔\gamma (a)$ if $a\in \overline{A}$, and $\mathrm{\ell }(a)≔-\gamma (a)$ if $\overline{a}\in \overline{A}$. Let us define ${\overline{p}}^{\ast }:\overline{V}\to \mathbb{Z}$ as a feasible potential with ${\overline{p}}^{\ast }(0)=0$ in ${\overline{G}}_{f^{\ast }}$ with respect to arc length $\mathrm{\ell }$, i.e., an assignment ${\overline{p}}^{\ast }:\overline{V}\to \mathbb{Z}$ satisfying ${\overline{p}}^{\ast }(0)=0$ and $\mathrm{\ell }(a)\ge {\overline{p}}^{\ast }(v)-{\overline{p}}^{\ast }(u)$ for each arc $a=(u,v)\in \overline{A}$. The following lemma justifies our reduction.

The validity of Lemma 7 follows from exactly the same argument given in [1]. For the sake of completeness, we provide a direct proof in the full version.

We then show the time complexity of solving the minimum $k$-potential problem via our reduction. The digraph $\overline{G}$ has $|V|+1=O(|V|)$ vertices, and at most $2(|V|-1+|A_0|)+|B_k(\phi )||A_{+}|=O(|V|+|A_0|+|B_k(\phi )||A_{+}|)$ arcs. Here, $A_0$ and $A_{+}$ denote the set of arcs $a$ with $w(a)=0$ and $w(a)>0$, respectively. Thus, we can construct the minimum cost flow instance $(\overline{G},\overline{\gamma },\overline{c},\overline{d})$ in $O(|V|+|A_0|+|B_k(\phi )||A_{+}|)$ time. The costs and capacities are nonnegative integers at most $k$ and $\overline{C}≔\max \{2M,{\max }_{a\in A}w(a)\phi (k)+M\}$, respectively. The demands are at most $M|V|$ in absolute values. Hence, we can find a minimum cost flow $f^{\ast }:\overline{A}\to {\mathbb{Z}}_{+}$ of $(\overline{G},\overline{\gamma },\overline{c},\overline{d})$ in $O\left(T_{\mathrm{mcf}}(|V|,|V|+|A_0|+|B_k(\phi )||A_{+}|,k,\overline{C},M|V|)\right)$ time. The residual graph ${\overline{G}}_{f^{\ast }}$ of $\overline{G}$ with respect to $f^{\ast }$ is constructed in $O(|\overline{A}|)=O(|V|+|A_0|+|B_k(\phi )||A_{+}|)$ time. A feasible potential ${\overline{p}}^{\ast }$ in ${\overline{G}}_{f^{\ast }}$ with respect to $\mathrm{\ell }$ is found in $O\left(T_{\mathrm{mcf}}(|V|,|V|+|A_0|+|B_k(\phi )||A_{+}|,k,|V|,|V|)\right)$ time by computing shortest distances from a supernode to vertices in $\overline{V}$. Therefore, by Lemma 7, we can obtain a minimum $k$-potential $p^{\ast }$, which is a restriction of ${\overline{p}}^{\ast }$ to $V$, in $O\left(T_{\mathrm{mcf}}(|V|,|V|+|A_0|+|B_k(\phi )||A_{+}|,k,\overline{C},M|V|)\right)$ time.

By applying the algorithm in [25], we obtain the following, which implies Theorem 2.

In this section, we introduce two applications of our framework; one is the $k$-diverse problems of Unweighted Minimum $s$-$t$ Cut and the other is that of Stable Matching.

In order to apply our framework to the $k$-diverse problem of a concrete combinatorial problem, we need to construct a poset and a reduction map appearing in the property (R) for each instance. In Section 5.1, we develop a common strategy of building these components. In fact, it is known that both families of minimum $s$-$t$ cuts and stable matchings are naturally identified with set families called ring families. A ring family with inclusion order forms a poset, particularly a distributive lattice. We will utilize these facts to construct a reduction map for Unweighted Minimum $s$-$t$ Cut and Stable Matching in Sections 5.2 and 5.3, respectively. In Section 5.4, we briefly describe a framework for the $k$-diverse problem recently developed by De Berg, Martínez, and Spieksma in [8], and show that our framework can capture theirs in the case of Sum-$k$-Diverse/Cov-$k$-Diverse.