1 Introduction↩︎

We denote by \(\mathbb{Z}\) the set of integers. For \(i,j\in\mathbb{Z}\) \((i\le j)\), we let \([i,j]\mathrel{\vcenter{:}}=\{i,i+1,\dots,j\}\). Let \(G = (V,E)\) be an undirected graph with a vertex set \(V\) and an edge set \(E\). We denote \(n=|V|\) and \(m=|E|\). The degree of a vertex \(v \in V\) is the number of edges in \(G\) that are incident to \(v\) and is denoted by \(\deg_G(v)\). We denote by \(N_G(v)\) the set of open neighbors of \(v\). For a subset \(S \subseteq V\), we denote by \(G[S]\) the subgraph of \(G\) induced by \(S\) and by \(G-S\) the subgraph induced by \(V \setminus S\), i.e., \(G[V\setminus S]\). If \(S = \{v\}\), then we write \(G - \{v\}\) as \(G - v\) for simplicity. A subset \(S\subseteq V\) (or \(G[S]\)) is called the \(k\)-core (of \(G\)) if \(G[S]\) is the inclusion-wise maximal induced subgraph such that the minimum degree is no less than \(k\), where the \(k\)-core of \(G\) is unique [1]. We call \(G\) a \(k\)-core graph if the \(k\)-core of \(G\) is \(G\) itself (i.e., the minimum degree of \(G\) is no less than \(k\)). We regard a null graph as a \(k\)-core graph.

The \(k\)-core of a graph \(G\) can be computed in linear time by a simple iterative procedure [2] and has various applications in network analyses [3]; e.g., social networks [1], [4]–[6], biological networks [7]–[9]. For \(v\in V\), the \(k\)-core of \(G-v\) may be significantly smaller than that of \(G\). This means that the \(k\)-core of a real-world network is not necessarily robust against attacks, disasters, or failures. When a network is partially destroyed, the \(k\)-core of the remaining graph may be much smaller than the original one, or it may even be empty. This phenomenon, known as core collapse, indicates the vulnerability of \(k\)-cores [10], [11].

Figure 1 illustrates this issue. It shows a graph \(G\) and the 3-cores of some proper subgraphs obtained by removing a vertex from \(G\). Note that the 3-core of \(G\) is \(G\) itself. As shown in (ii), the 3-core of \(G - v_3\) is \(G - v_3\) itself. On the other hand, in (iii) and (iv), the 3-core of \(G - v\) for \(v \in \{ v_1, v_8 \}\) is not necessarily equal to \(G - v\). In (iii), the 3-core of \(G - v_8\) is \(G - \{v_8, v_9\}\). In (iv), the 3-core of \(G - v_1\) consists of only four vertices \(\{v_2, v_3, v_5, v_6\}\). Furthermore, the 3-core of \(G - v_2\) is empty.

For a \(k\)-core graph \(G=(V,E)\), let \(Y_1,Y_2,\dots,Y_q\subseteq V\) denote the minimal nonempty subsets of \(V\) such that \(G-Y_i\), \(i\in[1,q]\) is a \(k\)-core graph. We claim that computing \(Y_1,Y_2,\dots,Y_q\) would provide useful information on evaluating the robustness of the \(k\)-core \(G\) against vertex removals. For example, the size \(|Y_i|\) indicates the degree of core collapse when \(v\in Y_i\) is removed from \(G\), where it is easy to see that \(Y_i\cap Y_j=\emptyset\) holds for every \(i,j\in[1,q]\) \((i\ne j)\). Furthermore, for \(v\in V\setminus(Y_1\cup Y_2\cup\dots\cup Y_q)\), the \(k\)-core of \(G-v\) is not any of \(G-Y_i\), \(i\in[1,q]\); it is a proper subset of \(G-Y_j\) for some \(j\in[1,q]\), indicating that the removal of \(v\) yields a larger collapse than any vertex in \(Y_j\).

In Figure 1, such minimal nonempty subsets of \(V\) are \(Y_1=\{v_3\}\) and \(Y_2=\{v_8,v_9\}\), where the 3-cores of \(G-Y_1\) and \(G-Y_2\) are shown in (ii) and (iii), respectively. For \(v\in V\setminus(Y_1\cup Y_2)=\{v_1,v_2,v_4,v_5,v_6,v_7\}\), the \(k\)-core of \(G-v\) is not any of \(G-Y_1\) or \(G-Y_2\); it is a proper subset of \(G-Y_1\) and/or \(G-Y_2\); e.g., the 3-core of \(G-v_1\) in (iv) is a proper subgraph of \(G-Y_2\).

Let us introduce terminologies to formalize a problem based on the above motivation. Suppose that an element set \(U\) and a property \(\Pi\) are given. Let \(S\subseteq U\). A nonempty subset \(Y\subseteq S\) is a removable set of \(S\) if \(S\setminus Y\) satisfies \(\Pi\), where whether or not \(S\) satisfies \(\Pi\) does not matter. We abbreviate a removable set into an RS for simplicity and call an inclusion-wise minimal RS a MinRS. For example, when we discuss \(k\)-cores, a MinRS of a graph \(G=(V,E)\) is a minimal nonempty subset \(Y\subseteq V\) such that \(G-Y\) is a \(k\)-core graph.

We formalize the problem MinRSs of \(k\)-Core: Given a \(k\)-core graph \(G=(V,E)\), find all MinRSs. Obviously, the problem can be solved by the following simple algorithm: compute the MinRS of \(G-v\) for each \(v\in V\) and collect the minimal subsets among them. This algorithm takes at least \(\Omega((n+m)n+\tau_{\mathrm{col}})\) time, where \(\tau_{\mathrm{col}}\) denotes the time for collecting minimal subsets and \(\tau_{\mathrm{col}}=O(n^3)\) holds.

In this paper, we show that the problem MinRSs of \(k\)-Corecan be solved in \(O((n+m)\log n)\) time under a general framework based on what we call a monotone system. For a ground set \(U\) and \(\mathcal{F}\subseteq 2^U\), we call \((U,\mathcal{F})\) a set system, or a system for short. When \(U\) is clear from the context, we may regard \(\mathcal{F}\) as a system for simplicity. Let \(\mathcal{Z}=(Z,\leqslant)\) be a poset; \(\omega: 2^U\times U\to Z\) be a function; and \(\theta\in Z\). For \(S\subseteq U\) and \(u\in U\), we may state \(\omega(S,u)\) as \(\omega_S(u)\). Given a tuple \((U,\mathcal{Z},\omega,\theta)\), we call \(S\subseteq U\) a \(\theta\)-solution if \(\theta\leqslant\omega_S(u)\) holds for every \(u\in S\). We regard an empty set as a \(\theta\)-solution. We define \(\mathcal{S}(U,\mathcal{Z},\omega,\theta)\mathrel{\vcenter{:}}=\{S\subseteq U\mid S\text{ is a }\theta\text{-solution}\}\) to be the family of all \(\theta\)-solutions.

• We say that \(\omega\) is monotone if \(\omega_S(u)\leqslant\omega_{S'}(u)\) holds for any \(S\subseteq S'\subseteq U\) and \(u\in U\). We call \((U,\mathcal{S}(U,\mathcal{Z},\omega,\theta))\) (or \(\mathcal{S}(U,\mathcal{Z},\omega,\theta)\)) a monotone system if \(\omega\) is monotone.

• Assuming an underlying graph \(G=(V,E)\), we say that \(\omega\) is local (with respect to \(G\)) [12], [13] if \(\omega_S(u)=\omega_{S\cap N_G(u)}(u)\) holds for any \(S\subseteq V\) and \(u\in V\), that is, \(\omega_S(u)\) depends only on the neighbors of \(u\) that belong to \(S\). We call \((V,\mathcal{S}(V,\mathcal{Z},\omega,\theta))\) (or \(\mathcal{S}(V,\mathcal{Z},\omega,\theta)\)) local monotone if \(\omega\) is local and monotone. To emphasize \(G\), we may state it as \(\mathcal{S}(V,\mathcal{Z},\omega,\theta;G)\).

Suppose that we are given a local monotone system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,\theta;G)\). We consider the problem of finding all MinRSs \(Y\) of \(V\) such that \(V\setminus Y\) is a \(\theta\)-solution. As we will see, the problem is a generalization of MinRSs of \(k\)-Core. Let us denote by \(\tau_\omega\) and \(\kappa_\omega\) upper bounds on the time and space complexity to compute \(\omega_S(u)\) for \(S\subseteq V\) and \(u\in V\), respectively. Our first theorem is summarized as follows.

Note that whether \(V\) itself is a \(\theta\)-solution or not does not matter. To show the theorem, we examine mathematical properties of a monotone system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,\theta)\), not limited to local monotone systems, and design an algorithm to enumerate all MinRSs of \(V\), where we exploit two auxiliary digraphs, that is propagation digraphs and seed-relation (SR) digraphs. Then we analyze the computational complexity of the algorithm when \(\mathcal{S}\) is local monotone with respect to an underlying graph \(G\), yielding Theorem [thm:main_local_system].

Next, we show that the time complexity can be improved if a local monotone system satisfies what we call the in-dominating seed property.

Our framework can be applied to a lot of extensions of \(k\)-cores [3]; e.g., generalized cores [12], [13], \((k,\ell)\)-cores in digraphs [14], weighted \(k\)-cores [15], multi-layer \(\boldsymbol{k}\)-cores [16]. For these extensions, we show that all MinRSs of \(V\) can be generated in \(O((n+m)n)\) time by Theorem [thm:main_local_system], whereas the baseline algorithm requires at least \(\Omega((n+m)n+\tau_{\mathrm{col}})\) time. Furthermore, for \(k\)-cores in undirected graphs, we can show the following theorem, using the in-dominating seed property and Theorem 2.

For algorithmic studies on core collapse, given an undirected graph \(G\) and integers \(b,x,k\), the problem Collapsed \(k\)-Core asks for whether there is a subset \(S\) of at most \(b\) vertices such that the \(k\)-core of \(G-S\) has at most \(x\) vertices. The problem is NP-hard [17], and fixed-parameter tractability [18] and mathematical optimization models [19] are investigated. The papers [20]–[23] study problems on core collapse caused by edge removal. For example, Honcharov et al. [20] study the problem of finding a spanning subgraph with the minimum number of edges such that the core number of each vertex is the same as in the input graph.

The paper is organized as follows. We prepare notations and terminologies in Section [sec:prel]. In Section [sec:mmw], we discuss monotone systems to analyze their mathematical properties and to present an algorithm that enumerates all MinRSs of the ground set of a given system. Then in Section [sec:lms], we explain how we achieve computational efficiency for local monotone systems and those satisfying the in-dominating seed property, along with the proofs for Theorems 1 and 2. We also describe how we apply the framework to \(k\)-cores and the extensions, where we provide a proof for Theorem 3. Finally, we consider the problem of enumerating “all” \(\theta\)-solutions in a monotone system. For the enumeration of all \(k\)-core subgraphs in a given graph, our algorithm achieves a better time bound than an algorithm based on Boley et al.’s framework [24]. We conclude the paper in Section [sec:conc].

2 Preliminaries↩︎

Throughout the paper, we use \(V\) to represent the vertex set of a graph or the ground set of elements. We use the terms “maximal” or “minimal” to indicate “inclusionwise-maximal” or “inclusionwise-minimal” if no confusion arises. If the domain of a function \(f\) is a family of subsets (e.g., \(2^V\) for a ground set \(V\)), we write \(f(\{x_1,x_2,\dots,x_k\})\) as \(f(x_1,x_2,\dots,x_k)\) for simplicity.

For a ground set \(V\), we represent a subset of \(V\) by italic (e.g., \(A\subseteq V\)); a family of subsets of \(V\) by calligraphic (e.g., \(\mathcal{A}\subseteq 2^V\)); and a collection of families of subsets of \(V\) by blackboard bold (e.g., \(\mathbb{A}\subseteq 2^{2^V}\)). We use the union operator \(\cup\) to represent descending the set hierarchy (i.e., \(\cup\mathbb{A}=\bigcup_{\mathcal{A}\in\mathbb{A}}\mathcal{A}\subseteq 2^V\), \(\cup\mathcal{A}=\bigcup_{A\in\mathcal{A}}A\subseteq V\)).

For a graph \(G\), let \(S\) be a subset of vertices. We may abbreviate \(G[S]\) into \(S\) for simplicity when \(G[S]\) appears in a subscript if no confusion arises; e.g., \(N_{G[S]}(v)\) may be written as \(N_S(v)\) for a vertex \(v\).

For an undirected graph \(G=(V,E)\), let \(v\in V\). we denote by \(N_G[v]=N_G(v)\cup\{v\}\) the set of closed neighbors. For \(S\subseteq V\), we let \(N_G(S)\mathrel{\vcenter{:}}=\big(\bigcup_{v\in S}N_G(v)\big)\setminus S\) and \(N_G[S]\mathrel{\vcenter{:}}= N_G(S)\cup S\).

For a directed graph (or a digraph) \(D=(V,A)\), let \(v\in V\). We denote the set of open out-neighbors (resp., in-neighbors) of \(v\) by \(N^+_D(v)\) (resp., \(N^-_D(v)\)). We also denote the set of closed out-neighbors (resp., in-neighbors) of \(v\) by \(N^+_D[v]\mathrel{\vcenter{:}}= N^+_D(v)\cup\{v\}\) (resp., \(N^-_D[v]\mathrel{\vcenter{:}}= N^-_D(v)\cup\{v\}\)). For convenience, we define \(N_D(v)\mathrel{\vcenter{:}}= N^+_D(v)\cup N^-_D(v)\) and \(N_D[v]\mathrel{\vcenter{:}}= N^+_D[v]\cup N^-_D[v]\). We denote by \(R_D(v)\) the set of vertices that are reachable from \(v\). We regard \(v\notin R_D(v)\) and let \(R_D[v]\mathrel{\vcenter{:}}= R_D(v)\cup\{v\}\). For \(S\subseteq V\), we let \(R_D(S)\mathrel{\vcenter{:}}=\big(\bigcup_{v\in S}R_D(v)\big)\setminus S\) and \(R_D[S]\mathrel{\vcenter{:}}= R_D(S)\cup S\). We abbreviate a weakly connected component and a strongly connected component into WCC and SCC, respectively. In the SCC decomposition, we call an SCC that has no outgoing arcs a bottom SCC, and a vertex in a bottom SCC a bottom vertex.

Let \(\mathcal{Z}=(Z,\leqslant)\) be a partially ordered set (poset) that consists of a ground set \(Z\) and a partial order \(\leqslant\) on \(V\). For \(x,y\in Z\), we may write \(y\geqslant x\) if \(x\leqslant y\). A mapping \({\mathit{cl}}:Z\to Z\) is a closure operator (on \(\mathcal{P}\)) if it satisfies the extensivity (i.e., \(x\leqslant{\mathit{cl}}(x)\)), the monotonicity (i.e., \(x\leqslant y\) \(\Rightarrow\) \({\mathit{cl}}(x)\leqslant{\mathit{cl}}(y)\)), and the idempotence (i.e., \({\mathit{cl}}({\mathit{cl}}(x))={\mathit{cl}}(x)\)). The element \({\mathit{cl}}(x)\) is called the closure of \(x\).

3 Monotone Systems↩︎

In this section, we examine mathematical properties of monotone systems \(\mathcal{S}(V,\mathcal{Z},\omega,\theta)\) in Section [sec:mmw_prop] and design an algorithm to enumerate all MinRSs of \(V\) in Section [sec:mono_alg].

3.1 Mathematical Properties↩︎

For a monotone system \(\mathcal{S}(V,\mathcal{Z},\omega,\theta)\), let \(S\subseteq V\) be a non-empty subset. If \(S\) is not a \(\theta\)-solution, then there is \(u\in S\) such that \(\omega_S(u) \not\geqslant \theta\). We say that \(u\) is violating \(S\). Also there is an RS \(Y\subseteq S\) of \(S\) such that \(S\setminus Y\) is a \(\theta\)-solution; recall that we regard \(\emptyset\) as a \(\theta\)-solution. A violating element \(u\) belongs to \(Y\) since otherwise we would have \(\omega_{S}(u)\geqslant\omega_{S\setminus Y}(u)\geqslant\theta\), contradicting \(\omega_{S}(u)\not\geqslant\theta\). In particular, if \(Y\) is a MinRS of \(S\), then \(S\setminus Y'\) is not a \(\theta\)-solution for any \(Y'\subsetneq Y\) and there is \(v\in Y\setminus Y'\) such that \(\omega_{S\setminus Y'}(v) \not\geqslant \theta\). This simple observation is used in the following discussions.

The following lemma generalizes the fact that, if an undirected graph \(G\) is not a \(k\)-core graph, then the \(k\)-core of \(G\) is unique, or equivalently, the MinRS of \(G\) is unique, to the context of monotone systems.

If \(S\) itself is a \(\theta\)-solution, then we are done. Otherwise, suppose that there are two different MinRSs of \(S\), say \(Y_1,Y_2\subseteq S\), for contradiction. There is \(u\in S\) such that \(\omega_S(u)\not\geqslant\theta\) since \(S\) is not a \(\theta\)-solution. Both \(Y_1\) and \(Y_2\) contain such \(u\) and hence \(u\in Y_1\cap Y_2\) holds. By the minimality, neither \(Y_1\setminus Y_2\) nor \(Y_2\setminus Y_1\) is empty. The subset \(S\setminus (Y_1\cap Y_2)\) is not a \(\theta\)-solution, and there is an element \(v\in Y_1\setminus Y_2\) such that \(\omega_{S\setminus(Y_1\cap Y_2)}(v) \not\geqslant \theta\). However, this would yield \(\omega_{S\setminus(Y_1\cap Y_2)}(v)\geqslant\omega_{S\setminus Y_2}(v)\geqslant\theta\), a contradiction. \(\Box\)

For \(C\subseteq V\), let \(Y\) denote the unique superset of \(C\) such that \(V\setminus Y\) is the maximal \(\theta\)-solution among subsets of \(V\setminus C\). The uniqueness of such \(Y\) is guaranteed by Lemma 1. We define a function \(\rho:2^V\to2^V\) to be \(\rho(C)\triangleq Y\). In other words, when \(C\ne\emptyset\), \(\rho(C)\) is the unique RS of \(V\) that is minimal among supersets of \(C\). Note that \(\rho(C)\) is an RS of \(V\), but not necessarily a MinRS of \(V\).

It is immediate from the definition that \(\rho\) satisfies the extensivity (i.e., \(C\subseteq\rho(C)\)) and the idempotence (i.e., \(\rho(\rho(C))=\rho(C)\)). For the monotonicity, let \(C_1,C_2\subseteq V\). We show that \(\rho(C_2)\subseteq\rho(C_1)\) holds if \(C_2\subseteq C_1\). Note that \(C_2\subseteq\rho(C_1)\) holds by the extensivity.

If \(\rho(C_1)=V\), then we have \(\rho(C_1)=V\supseteq\rho(C_2)\). Suppose \(\rho(C_1)\subsetneq V\) and \(C_2=\emptyset\). If \(V\) is a \(\theta\)-solution, then \(\rho(C_2)=\emptyset\subseteq\rho(C_1)\) holds. Otherwise, \(\rho(C_2)=\rho(\emptyset)\) is the unique MinRS of \(V\). Any RS of \(V\) should contain \(\rho(C_2)\) as a subset, and hence \(\rho(C_2)\subseteq\rho(C_1)\).

Let us consider the remaining case; suppose \(\rho(C_1)\subsetneq V\) and \(C_2\ne\emptyset\). By \(C_2\subseteq\rho(C_1)\) and \(C_2\subseteq\rho(C_2)\), we have \(C_2\subseteq\rho(C_1)\cap\rho(C_2)\), implying that \(\rho(C_1)\cap\rho(C_2)\) is not empty. Suppose \(\rho(C_2)\not\subseteq\rho(C_1)\) for contradiction. For any \(C_2\subseteq R\subsetneq\rho(C_2)\), \(V\setminus R\) is not a \(\theta\)-solution. Then \(V\setminus(\rho(C_1)\cap\rho(C_2))\) is not a \(\theta\)-solution since \(C_2\subseteq \rho(C_1)\cap\rho(C_2)\subsetneq\rho(C_2)\), where the last inclusion relationship holds by \(\rho(C_2)\setminus\rho(C_1)\ne\emptyset\). There is an element \(v\in\rho(C_2)\setminus\rho(C_1)\) such that \(\omega_{V\setminus(\rho(C_1)\cap\rho(C_2))}(v)\not \geqslant \theta\). However, we would have \(\omega_{V\setminus(\rho(C_1)\cap\rho(C_2))}(v)\geqslant\omega_{V\setminus\rho(C_1)}(v)\geqslant \theta\), a contradiction. \(\Box\)

We can compute the closure \(\rho(C)\) of \(C\) by a simple iterative procedure in Algorithm 2. This is regarded as a generalization of the algorithm that computes the \(k\)-core of a given graph.

3.1.0.1 Propagation Digraphs.

To understand the structure of RSs of \(V\) in a monotone system \(\mathcal{S}\mathrel{\vcenter{:}}=\mathcal{S}(V,\mathcal{Z},\omega,\theta)\), we introduce the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}=(V,A^{\mathrm{pr}}_\mathcal{S})\) that consists of the vertex set \(V\) and the arc set \(A^{\mathrm{pr}}_\mathcal{S}\triangleq\{(u,v)\in V\times V\mid \omega_{V\setminus\{u\}}(v)\not\geqslant \theta\}\). The digraph shows the propagation of weights falling below the threshold \(\theta\) when one element is removed from \(V\). Any path from a vertex \(u\) to other vertex represents that, if \(u\) is removed from \(V\), then all the other vertices on the path should be removed to obtain a \(\theta\)-solution, that is, any RS of \(V\) that contains \(u\) must contain all vertices on the path, whereas they may not be sufficient. Thus, for the purpose of enumerating MinRSs of \(V\), bottom SCCs in the digraph must be important since, for every vertex \(u\), there is a bottom SCC which is reachable from \(u\). Let \(u\in V\) and \(C\subseteq V\). For notational convenience, let us write \(R_{H^{\mathrm{pr}}_{\mathcal{S}}}[u]\) (resp., \(R_{H^{\mathrm{pr}}_{\mathcal{S}}}[C]\); \(N^+_{H^{\mathrm{pr}}_\mathcal{S}}(u)\); and \(N^+_{H^{\mathrm{pr}}_\mathcal{S}}[u]\)) as \(R^{\mathrm{pr}}_{\mathcal{S}}[u]\) (resp., \(R^{\mathrm{pr}}_{\mathcal{S}}[C]\); \(N^{\mathrm{pr}+}_\mathcal{S}(u)\); and \(N^{\mathrm{pr}+}_\mathcal{S}[u]\)).

We denote by \(\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\subseteq 2^V\) the family of bottom SCCs in the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\). For \(B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\), if \(|B|=1\), say \(B=\{u\}\), then \(\{u\}\) is a MinRS of \(V\) since its out-degree is zero and hence \(\omega_{V\setminus\{u\}}(v)\geqslant\theta\) holds for all \(v\in V\setminus\{u\}\), indicating that \(V\setminus\{u\}\) is a \(\theta\)-solution. If \(|B|\ge2\), then \(B\) is not necessarily an RS; for \(B=\{u_1,u_2,\dots,u_k\}\), it is possible that \(\omega_{V\setminus B}(v)\not\geqslant \theta\) holds for \(v\in V\setminus B\) even when \(\omega_{V\setminus\{u_i\}}(v)\geqslant\theta\), \(i\in[1,k]\). If \(V\) is not a \(\theta\)-solution, then the bottom SCC is unique since each violating vertex has an incoming edge from any other vertex.

Using bottom SCCs, we have the following characterization of MinRSs.

For the necessity, \(Y\) must contain all bottom SCCs \(B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) that are reachable from \(Y\), and such \(B\) always exists. Then \(Y=\rho(Y)\supseteq\rho(B)\) holds. The closure \(\rho(B)\) is an RS of \(V\) and, by the minimality of \(Y\), \(Y=\rho(B)\) holds, showing (i). (ii) is immediate.

For the sufficiency, we have \(Y=\rho(B)\) by (i) and \(\rho(B)\) is an RS of \(V\) by the definition of \(\rho\). If \(\rho(B)\) is not a MinRS of \(V\), then there is a MinRS \(Y'\subsetneq\rho(B)\) that is a proper subset of \(\rho(B)\). By the necessity of MinRS, there would be \(B'\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) such that \(\rho(B')=Y'\), yielding \(\rho(B')=Y'\subsetneq\rho(B)=Y\), contradicting (ii). \(\Box\)

We see that any MinRS of \(V\) can be generated by computing the closure \(\rho(B)\) of some bottom SCC \(B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\). Thus we call a bottom SCC in the propagation graph a seed and vertices in a seed seed vertices. We can enumerate all MinRSs of \(V\) as follows: (1) Construct the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\). (2) Compute the seeds, that is, the bottom SCCs of \(H^{\mathrm{pr}}_\mathcal{S}\). (3) For each seed \(B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\), compute \(\rho(B)\) by Algorithm 2. (4) Collect the minimal subsets in \(\{\rho(B)\mid B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\}\); they are MinRSs of \(V\) by Lemma [lem:minRS_necsuf]. However, by this approach, it must be hard to achieve a better time bound than the baseline algorithm mentioned in Section [sec:intro] since the number of seeds is \(|\mathcal{B}^{\mathrm{pr}}_\mathcal{S}|=O(n)\).

3.2 Algorithms to Enumerate MinRSs↩︎

Again, let \(\mathcal{S}\mathrel{\vcenter{:}}=\mathcal{S}(V,\mathcal{Z},\omega,\theta)\) be a monotone system. In this subsection, we describe an alternative algorithm to enumerate all MinRSs of \(V\). As shown in the next section, this algorithm achieves a better time bound than the baseline algorithm when \(\mathcal{S}\) is local monotone.

In the proposed algorithm, we use a partition of the seed set \(\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) to maintain candidates of seeds whose closures are MinRSs of \(V\). For a subset \(\mathcal{B}\subseteq\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) of seeds, we define \(\Sigma(\mathcal{B})\mathrel{\vcenter{:}}=\{B^\ast\in\mathcal{B}\mid\forall B\in\mathcal{B},\;\rho(B^\ast)\subseteq\rho(B)\}\). We call \(\mathcal{B}\) pointed if \(\Sigma(\mathcal{B})\ne\emptyset\). When \(\mathcal{B}\) is pointed, \(\rho(B^\ast)=\rho(B^{\ast\ast})\) holds for any \(B^\ast,B^{\ast\ast}\in\Sigma(\mathcal{B})\), and we write \(\rho(B^\ast)\) or \(\rho(B^{\ast\ast})\) as \(\rho(\mathcal{B})\) for simplicity. Let \(\mathbb{B}\) be a partition of the seed set \(\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\). We call \(\mathbb{B}\) pointed if every \(\mathcal{B}\in\mathbb{B}\) is pointed. For example, the partition \(\mathbb{B}_\bot\mathrel{\vcenter{:}}=\bigcup_{B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}}\{\{B\}\}\) that consists of singletons of seeds is pointed. The following lemma motivates us to utilize a pointed partition of the seed set \(\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\).

By Lemma [lem:minRS_necsuf], there is a seed \(B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) such that \(\rho(B)=Y\). Let \(\mathcal{B}\in\mathbb{B}\) denote the subset in \(\mathbb{B}\) such that \(B\in\mathcal{B}\). The partition \(\mathbb{B}\) is pointed, and hence \(\mathcal{B}\) is pointed. Any \(B^\ast\in\Sigma(\mathcal{B})\) satisfies \(\rho(\mathcal{B})=\rho(B^\ast)\subseteq\rho(B)=Y\), where the inclusion relationship must hold by equality due to the minimality of \(Y\). \(\Box\)

Informally, the proposed algorithm enumerates MinRSs of \(V\) as follows; starting from the trivial pointed partition \(\mathbb{B}=\mathbb{B}_\bot\), we repeat updating \(\mathbb{B}\) by \(\mathbb{B}\gets(\mathbb{B}\setminus\{\mathcal{B},\mathcal{B}'\})\cup\{\mathcal{B}\cup\mathcal{B}'\}\) for \(\mathcal{B},\mathcal{B}'\in\mathbb{B}\) such that \(\rho(\mathcal{B})\subseteq\rho(\mathcal{B}')\) (resp., \(\rho(\mathcal{B}')\subseteq\rho(\mathcal{B})\)) holds, where \(\mathcal{B}\cup\mathcal{B}'\) is pointed in such a case since \(\Sigma(\mathcal{B}\cup\mathcal{B}')\supseteq\Sigma(\mathcal{B})\ne\emptyset\) (resp., \(\Sigma(\mathcal{B}\cup\mathcal{B}')\supseteq\Sigma(\mathcal{B}')\ne\emptyset\)). Finally we obtain a pointed partition \(\mathbb{B}\) such that, for any \(\mathcal{B}\in\mathbb{B}\), no \(\mathcal{B}'\in\mathbb{B}\) \((\mathcal{B}'\ne\mathcal{B})\) satisfies \(\rho(\mathcal{B})\supseteq\rho(\mathcal{B}')\). We can show that there is a one-to-one correspondence between \(\mathbb{B}\) and the MinRSs of \(V\) (i.e., for each MinRS \(Y\), there is a unique \(\mathcal{B}\in\mathbb{B}\) such that \(\rho(\mathcal{B})=Y\)), by which we are done.

3.2.0.1 SR Digraphs and 1-SR Digraphs.

Maintaining a pointed partition \(\mathbb{B}=\{\mathcal{B}_i\}_{i=1}^q\), the algorithm runs with another auxiliary digraph. Let \(F^\ast[\mathbb{B}]\mathrel{\vcenter{:}}=\{(\mathcal{B}_i,\mathcal{B}_j)\in\mathbb{B}\times\mathbb{B}\mid \rho(\mathcal{B}_i)\supseteq\rho(\mathcal{B}_j),\;i\ne j\}\). We call the digraph \(H^\ast_\mathbb{B}=(\mathbb{B},F^\ast[\mathbb{B}])\) the seed-relation (SR) digraph of \(\mathbb{B}\). We call a subset \(\mathcal{B}\in\mathbb{B}\) of seeds a seed-subset node in the context of an SR digraph. Let \(H=(\mathbb{B},F)\) be a spanning subgraph of \(H^\ast_\mathbb{B}\). We call \(H\) a one-degree SR (1-SR) digraph of \(\mathbb{B}\) if \(\deg^+_H(\mathcal{B})\le 1\) holds for every \(\mathcal{B}\in\mathbb{B}\); and \(\deg^+_H(\mathcal{B})=1\) holds whenever \(\deg^+_{H^\ast_\mathbb{B}}(\mathcal{B})\ge1\). In other words, \(H\) is obtained by picking up precisely one outgoing arc for each seed-subset node in \(H^\ast_\mathbb{B}\) if one exists. Observe that every WCC of a 1-SR digraph is either an in-tree (i.e., an arborescence such that all arcs are reversed) or a functional graph (i.e., all out-degrees are one). For an in-tree WCC, we call the unique node with out-degree zero the root of the WCC. An example of a 1-SR digraph is shown in Figure 3.

In the proposed algorithm, we do not deal with SR digraphs explicitly since its size is \(O(n^2)\), but construct 1-SR digraphs \(H=(\mathbb{B},F)\) repeatedly, updating the pointed partition \(\mathbb{B}\), where the size of \(H\) is \(O(n)\).

Let us introduce mathematical properties of auxiliary digraphs and describe how \(\mathbb{B}\) is updated. For a pointed partition \(\mathbb{B}\), let \(H=(\mathbb{B},F)\) be a 1-SR digraph. Let us denote by \(s\) the number of WCCs in \(H\). For \(j\in[1,s]\), we denote by \(H_j\) the \(j\)-th WCC and by \(\mathbb{B}_j\) the collection of seed-subset nodes in \(H_j\), that is, \(H_j=H[\mathbb{B}_j]\) and \(\mathbb{B}=\mathbb{B}_1\cup\mathbb{B}_2\cup\dots\cup\mathbb{B}_s\). We define a partition \(\mathbb{B}[F]\) of \(\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) by \(\mathbb{B}[F]\triangleq\{\cup\mathbb{B}_1,\cup\mathbb{B}_2,\dots,\cup\mathbb{B}_s\}\), where \(\cup\mathbb{B}_j\) is the subset of seeds in the seed-subset nodes in \(H_j\). Let \(z_j\mathrel{\vcenter{:}}=|\mathbb{B}_j|\). We define \(\mu(H)\) to be the number of seed-subset nodes in \(H\) that belong to functional WCCs, i.e., \(\mu(H)\triangleq\sum_{j\in[1,s]:\,H_j\textrm{ is functional}} z_j\). In Figure 3, for example, \(\mathbb{B}_6=\{\{B_{4,1}\},\{B_{4,2}\},\{B_{5,1}\}\}\) is a set of singletons whereas \(\cup\mathbb{B}_6=\{B_{4,1},B_{4,2},B_{5,1}\}\) is the set of seeds that appear in \(\mathbb{B}_6\). We also see that \(H_1,\dots,H_5\) are functional, that \(H_6\) is an in-tree and that \(\mu(H)=11\) holds.

In the following lemma, (ii) says that \(\mathbb{B}[F]\) is a pointed partition. The algorithm employs \(\mathbb{B}[F]\) as the successor pointed partition of \(\mathbb{B}\). (iv) is a useful property for bounding the iteration times of the algorithm, where (iii) is used in the proof for (iv). (i) will be used in later analyses.

(i) Let \(B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) be any seed. If \(B\in\mathcal{B}\), then \(\rho(B)\supseteq\rho(\mathcal{B})\) holds by the definition. Otherwise, let \(\mathcal{B}'\in\mathbb{B}\) denote the seed-subset node such that \(B\in\mathcal{B}'\). Then \(\rho(\mathcal{B})\not\supseteq\rho(B)\) must hold since otherwise \(\rho(\mathcal{B})\supseteq\rho(B)\supseteq\rho(\mathcal{B}')\) would hold, contradicting that \(H\) contains no arc \((\mathcal{B},\mathcal{B}')\). We have seen that there is no seed \(B\in\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) that satisfies \(\rho(\mathcal{B})\supsetneq\rho(B)\), and hence \(\rho(\mathcal{B})\) is a MinRS of \(V\) by Lemma [lem:minRS_necsuf].

(ii) We show that \(\cup\mathbb{B}_j\) is pointed for each \(j\in[1,s]\), that is, there is a seed \(B^\ast\in(\cup\mathbb{B}_j)\) such that \(\rho(B^\ast)\subseteq\rho(B)\) holds for any \(B\in(\cup\mathbb{B}_j)\). For \(B\in(\cup\mathbb{B}_j)\), let \(\mathcal{B}\in\mathbb{B}_j\) denote the seed-subset node such that \(B\in\mathcal{B}\). Choose the seed-subset node \(\mathcal{B}^\ast\in\mathbb{B}_j\) as follows; if \(H_j\) is an in-tree, then choose the root seed-subset node as \(\mathcal{B}^\ast\), and otherwise (i.e., if \(H_j\) is functional), choose any seed-subset node on the only cycle as \(\mathcal{B}^\ast\). The chosen seed-subset node \(\mathcal{B}^\ast\in\mathbb{B}\) is pointed, and there is \(B^\ast\in\Sigma(\mathcal{B}^\ast)\) such that \(\rho(B^\ast)=\rho(\mathcal{B}^\ast)\). Then it holds that \(\rho(B)\supseteq\rho(\mathcal{B})\supseteq\rho(\mathcal{B}^\ast)=\rho(B^\ast)\).

(iii) Let \(\mathcal{B}^\ast\) denote the root seed-subset node of \(H_i\). There is a seed \(B^\ast\in\mathcal{B}^\ast\) such that \(\rho(\mathcal{B}^\ast)=\rho(B^\ast)\subseteq\rho(B)\) holds for every \(B\in(\cup\mathbb{B}_i)\). Then \(B^\ast\in\Sigma(\cup\mathbb{B}_i)\) holds and thus we have \(\rho(B^\ast)=\rho(\cup\mathbb{B}_i)\). In the SR digraph of \(\mathbb{B}[F]\), if there is an arc \((\cup\mathbb{B}_i,\cup\mathbb{B}_j)\) for some \(j\in[1,s]\), then \(\rho(\cup\mathbb{B}_i) \supseteq \rho(\cup\mathbb{B}_j)\) holds. There would exist \(\mathcal{B}\in\mathbb{B}_j\) such that \(\rho(\mathcal{B})=\rho(\cup\mathbb{B}_j)\subseteq\rho(\cup\mathbb{B}_i)=\rho(\mathcal{B}^\ast)\), contradicting that the arc \((\mathcal{B}^\ast,\mathcal{B})\) does not exist in \(H\).

(iv) Let \(s_1\) (resp., \(s_2\)) denote the number of in-tree (resp., functional) WCCs of \(H\), where \(s=s_1+s_2\). A functional digraph consists of at least two nodes, and thus we have \(2s_2\le\mu(H)\). In \(H'\), there are \(s\) seed-subset nodes each of which corresponds to a WCC of \(H\). By (iii), each in-tree WCC of \(H\) becomes the root seed-subset node of an in-tree WCC of \(H'\). Then in \(H'\), there are at least \(s_1\) in-tree WCCs and at most \(s_2\) seed-subset nodes belong to functional WCCs. Hence we have \(\mu(H')\le s_2\le\mu(H)/2\). \(\Box\)

See Figure [fig:1-SR_r2] for an example of \(H'=(\mathbb{B}[F],F')\) that is constructed for the 1-SR digraph \(H=(\mathbb{B},F)\) in Figure 3. In this example, we see \(s=6\), \(s_1=1\), \(s_2=5\), \(\mu(H)=11\), and \(\mu(H')=2\), where \(\mu(H')\le\mu(H)/2\) holds.

Let \(\mathcal{Y}\) denote the set of all MinRSs of \(V\). We can enumerate \(\mathcal{Y}\) as follows; starting from \(\mathbb{B}=\mathbb{B}_\bot\), we repeat constructing a 1-SR digraph \(H=(\mathbb{B},F)\) somehow and updating \(\mathbb{B}\mathrel{\vcenter{:}}=\mathbb{B}[F]\), where \(\mathbb{B}[F]\) is pointed by Lemma 5(ii), until \(F=\emptyset\). The iteration is repeated \(O(\log n)\) times since \(\mu(H)\) becomes zero in \(O(\log n)\) iterations by Lemma 5(iv), indicating that all WCCs become in-trees. This means that all seed-subset nodes become isolated in \(O(\log n)\) iterations. Let \(\mathcal{B}_1,\mathcal{B}_2,\dots,\mathcal{B}_t\) denote the isolated seed-subset nodes of the resulting \(H\) and \(\mathcal{R}\mathrel{\vcenter{:}}=\{\rho(\mathcal{B}_j)\mid j\in[1,t]\}\). It holds that \(\mathcal{Y}\subseteq\mathcal{R}\) by Lemma [lem:minrs_pointed] and that \(\mathcal{Y}\supseteq\mathcal{R}\) by Lemma 5(i), by which \(\mathcal{Y}\) is obtained.

3.2.0.2 How to Construct 1-SR Digraphs.

We show how to construct a 1-SR digraph \(H=(\mathbb{B},F)\) of a pointed partition \(\mathbb{B}\). For each seed-subset node \(\mathcal{B}\in\mathbb{B}\), we need to decide whether there is \(\mathcal{B}'\) such that \(\rho(\mathcal{B})\supseteq\rho(\mathcal{B}')\) or not; if such \(\mathcal{B}'\) exists, then we include the arc \((\mathcal{B},\mathcal{B}')\) into \(F\), and otherwise, we conclude that the seed-subset node \(\mathcal{B}\) has no outgoing arcs.

The main lemma is Lemma 8, and the preceding Lemmas 6 and 7 are preparatory.

(ii) \(\Longrightarrow\) (i) is trivial since \(N^{\mathrm{pr}+}_\mathcal{S}[u]\subseteq R^{\mathrm{pr}}_\mathcal{S}[u]\) holds. For (i) \(\Longrightarrow\) (ii), by the definition of \(R^{\mathrm{pr}}_\mathcal{S}[u]\), there is a path from \(u\) to some vertex \(v \in R^{\mathrm{pr}}_\mathcal{S}[u] \cap B'\) in the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\). We have \(v\in R^{\mathrm{pr}}_\mathcal{S}[u] \subseteq \rho(u)\subseteq \rho(B)\). The vertex \(v\) belongs to \(B'\) and \(B\cap B'=\emptyset\), and hence \(v\in\rho(B)\setminus B\). It is obvious that \(v\in N^{\mathrm{pr}+}_\mathcal{S}[v]\) and thus \(v\in N^{\mathrm{pr}+}_\mathcal{S}[v]\cap B'\) holds. By the monotonicity of \(\rho\), we have \(\rho(B) \supseteq R^{\mathrm{pr}}_\mathcal{S}[B] \supseteq R^{\mathrm{pr}}_\mathcal{S}[u]\), which implies that \(v \in R^{\mathrm{pr}}_\mathcal{S}[u] \subseteq \rho(B)\). Since \(B \neq B'\), we have \(v \in \rho(B) \setminus B\) and \(v \in N_{\mathcal{S}}^{\mathrm{pr}+}[v] \cap B' \neq \emptyset\). \(\Box\)

(i) If \(u\in B'\), then we have \(\rho(B')=\rho(u)\subseteq\rho(B)\). Otherwise, there is an element \(v\in N^{\mathrm{pr}+}_{\mathcal{S}}(u)\cap B'\). To obtain \(\rho(B)\) by the iterative procedure, we need to remove \(u\), its neighbor \(v\), and eventually all elements in \(B'\). Hence \(\rho(B)\supseteq\rho(B')\) holds.

(ii) If \(\rho(B)\setminus B=\emptyset\) (i.e., \(\rho(B)=B\)), then \(\rho(B')\not\subseteq\rho(B)\) holds since \(B'\subseteq\rho(B')\) and \(B=\rho(B)\) are disjoint. Suppose that \(N^{\mathrm{pr}+}_\mathcal{S}[u]\cap B'=\emptyset\) for any \(u\in\rho(B)\setminus B\). By Lemma 6, \(R^{\mathrm{pr}}_\mathcal{S}[u]\cap B'=\emptyset\) holds for any \(u\in\rho(B)\setminus B\). If \(\rho(B) \cap B' \neq \emptyset\), then let \(v \in \rho(B) \cap B'\). However, by \(B\cap B'=\emptyset\), we would have \(v \in \rho(B) \setminus B\) and \(v \in R^{\mathrm{pr}}_\mathcal{S}[v] \cap B' \neq \emptyset\), a contradiction. Then \(\rho(B)\cap B'=\emptyset\) holds, implying \(\rho(B)\not\supseteq\rho(B')\). \(\Box\)

For (i), we see \(B\ne B'\). By Lemma 7(i), we have \(\rho(B)\supseteq\rho(B')\supseteq\rho(\mathcal{B}')\). For (ii), for any seed \(B'\in\mathcal{B}'\) \((\mathcal{B}'\ne\mathcal{B})\), \(\rho(B')\not\subseteq\rho(B)\) holds by Lemma 7(ii). For any seed \(B'\in\mathcal{B}\), it holds that \(\rho(B')\supseteq\rho(\mathcal{B})=\rho(B)\) by the definition of \(B\). No \(\rho(B')\) is a proper subset of \(\rho(B)\), and by Lemma [lem:minRS_necsuf], \(\rho(B)\) is a MinRS of \(V\). \(\Box\)

For a pointed partition \(\mathbb{B}\) and a seed-subset node \(\mathcal{B}\in\mathbb{B}\), we explain how to decide whether there is another seed-subset node \(\mathcal{B}'\in\mathbb{B}\) such that \(\rho(\mathcal{B})\supseteq\rho(\mathcal{B}')\). We exploit Lemma 8(i) and Algorithm 2. Let \(B\in\Sigma(\mathcal{B})\). Starting from \(Y\gets B\), we attempt to construct the closure \(\rho(B)\) in the manner of Algorithm 2. During the construction, we repeatedly add a violating vertex \(u\in V\setminus Y\) (i.e., \(\omega_{V\setminus Y}(u)\not\geqslant\theta\)) to \(Y\). This \(u\) must belong to \(\rho(B)\setminus B\). If there is a seed \(B'\in\mathcal{B}'\) \((\mathcal{B}'\ne\mathcal{B})\) such that \(N^{\mathrm{pr}+}_\mathcal{S}[u]\cap B'\ne\emptyset\), then \(\rho(\mathcal{B}')\subseteq\rho(B)\) holds by Lemma 8(i), indicating that the SR digraph includes the arc \((\mathcal{B},\mathcal{B}')\), and so does a 1-SR digraph. On the other hand, if no violating vertex is left as the result of the repetition, then \(Y=\rho(B)\) holds, that is, the closure is constructed. In this case, the seed subset-node \(\mathcal{B}\) has no outgoing arcs.

For a given seed-subset node \(\mathcal{B}\in\mathbb{B}\), we summarize in Algorithm 5 the algorithm that identifies whether or not there is \(\mathcal{B}'\ne\mathcal{B}\) such that \((\mathcal{B},\mathcal{B}')\in F^\ast[\mathbb{B}]\) and outputs the closure \(\rho(\mathcal{B})\) if no such \(\mathcal{B}'\) exists. Executing Algorithm 5 for each \(\mathcal{B}\in\mathbb{B}\), we can construct a 1-SR digraph \(H=(\mathbb{B},F)\), where \(F\) is the set of all \((\mathcal{B},\mathcal{B}')\) that are output by Algorithm 5.

3.2.0.3 Algorithms for Enumerating MinRSs of \(V\).

Now we are ready to present an algorithm to enumerate all MinRSs of \(V\). Starting from \(\mathbb{B}=\mathbb{B}_\bot\), the algorithm iteratively constructs a 1-SR digraph \(H=(\mathbb{B},F)\) and updates \(\mathbb{B}\mathrel{\vcenter{:}}=\mathbb{B}[F]\) until \(F=\emptyset\). Finally we have a pointed partition \(\mathbb{B}\) such that the 1-SR digraph consists of isolated seed-subset nodes. The algorithm outputs the closure of each node as a MinRS of \(V\). The preceding discussion guarantees the correctness of the algorithm.

The algorithm is summarized in Algorithm [alg:local_minrs]. In Algorithm [alg:local_minrs], for a seed-subset node \(\mathcal{B}\subseteq\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\), a variable \(\sigma(\mathcal{B})\) stores a seed in \(\Sigma(\mathcal{B})\); and a variable \(\ifmmode\text{\normalfont\scshape in-Tree}\else{\normalfont\scshape in-Tree}\fi(\mathcal{B})\) indicates whether the seed-subset node \(\mathcal{B}\) belonged to an in-tree of the 1-SR digraph that was constructed in the last iteration, where it is initialized for each singleton to \(\ifmmode\text{\normalfont\scshape False}\else{\normalfont\scshape False}\fi\) in Line [line:minrs_init].

In Line [line:from_minrs_extrho_call], we execute Algorithm 5 to obtain either \((\mathcal{B},\mathcal{B}^\dagger)\) or \(\rho(\mathcal{B})\) only for a seed-subset node \(\mathcal{B}\in\mathbb{B}\) with \(\ifmmode\text{\normalfont\scshape in-Tree}\else{\normalfont\scshape in-Tree}\fi(\mathcal{B})=\ifmmode\text{\normalfont\scshape False}\else{\normalfont\scshape False}\fi\). This is because we do not need to do it for \(\mathcal{B}'\) with \(\ifmmode\text{\normalfont\scshape in-Tree}\else{\normalfont\scshape in-Tree}\fi(\mathcal{B}')=\ifmmode\text{\normalfont\scshape True}\else{\normalfont\scshape True}\fi\) (i.e., \(\mathcal{B}'\) corresponds to an in-tree of the 1-SR digraph in the last iteration); by Lemma 5(iii), it is guaranteed that the seed-subset node \(\mathcal{B}'\) has no outgoing arcs in the 1-SR digraph that is to be constructed in the current iteration. As we will see in the next section, this leads to an improvement in time complexity.

For the time complexity, Algorithm [alg:local_minrs] runs in \(O(n^3\log n\cdot\tau_\omega)\) time since the repeat-loop from Line [line:local_minrs_repeat_start] to [line:local95minrs95repeat95end] is iterated \(O(\log n)\) times by Lemma 5(iv), and the most time-consuming part, the for-loop from Line [line:for_MB_local_minrs] to [line:local95minrs95returned], takes \(O(n^3\cdot\tau_\omega)\) time; Algorithm 5 is called \(O(n)\) times and runs in \(O(n^2\cdot\tau_\omega)\) time per each call.

In the next section, we improve the time complexity when \(\mathcal{S}\) is local monotone, along with space complexity analyses.

4 Local Monotone Systems↩︎

In this section, we consider the MinRS enumeration problem on local monotone systems. In Section [sec:mmw_improve_eff], we analyze the computational complexity of the MinRS enumeration algorithm that was presented as Algorithm [alg:local_minrs] when we are given a local monotone system, as a proof for Theorem [thm:main_local_system]. In Section [sec:in-dominating_property], we improve the complexity when the local monotone system satisfies what we call the in-dominating seed property, as a proof for Theorem 2. Finally in Section [sec:examples_local_monotone_systems], we provide application examples of the framework, including a proof for Theorem 3.

4.1 Complexity of MinRS Enumeration↩︎

For a local monotone system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,\theta;G)\) with an underlying graph \(G\), it is easy to see that the propagation graph is a subgraph of (oriented) \(G\) if \(V\) is a \(\theta\)-solution.

The whole vertex set \(V\) is a \(\theta\)-solution, and hence \(\omega_{V}(x)\geqslant \theta\) holds for any \(x \in V\). For an undirected (resp., a directed) \(G\), suppose that there is no edge (resp., arc) between \(u\) and \(v\). We have \(\omega_{V\setminus\{u\}}(v) = \omega_{(V\setminus\{u\}) \cap N_G(v)}(v) = \omega_{V \cap N_G(v)}(v) = \omega_V(v) \geqslant \theta\), implying that \((u,v)\) is not an arc in \(H^{\mathrm{pr}}_\mathcal{S}\). \(\Box\)

We can decide whether \(V\) is a \(\theta\)-solution or not in \(O(n\tau_\omega)\) time and \(O(\kappa_\omega)\) space. If \(V\) is not a \(\theta\)-solution, then we can obtain its unique MinRS by Algorithm 2, which can be done in \(O((n+m)\tau_\omega)\) time and \(O(n+m+\kappa_\omega)\) space. Otherwise, before executing Algorithm [alg:local_minrs], we need to construct the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\) and then to decompose it into SCCs to obtain seeds. When \(V\) is a \(\theta\)-solution, let \(u,v\) be any vertices in the underlying graph \(G=(V,E)\). If \(G\) is undirected (resp., directed), then by Lemma 9, an arc \((u,v)\) exists in \(H^{\mathrm{pr}}_\mathcal{S}\) only when \(uv\in E\) (resp., \((u,v)\in E\) and/or \((v,u)\in E\)). Hence we can obtain the arc set of \(H^{\mathrm{pr}}_\mathcal{S}\) by evaluating whether \(\omega_{V\setminus\{u\}}(v)\geqslant\theta\) or not for each \(u\in V\) and \(v\in N_G(u)\). The propagation graph \(H^{\mathrm{pr}}_\mathcal{S}\) consists of \(n\) vertices and \(O(n+m)\) arcs. We see that construction of \(H^{\mathrm{pr}}_\mathcal{S}\) and its SCC decomposition can be done in \(O((n+m)\tau_\omega)\) time and \(O(n+m+\kappa_\omega)\) space.

We examine the computational complexity of Algorithm 5 for local monotone systems, which is repeatedly called as a subroutine from Algorithm [alg:local_minrs].

For the correctness, see the discussion on Algorithm 5 in Section [sec:mono_alg]. Here we analyze the complexity.

In Algorithm 5, we maintain a subset \(Q\) of vertices. We may assume that it takes \(O(1)\) time to insert a vertex into \(Q\) or to delete a vertex from \(Q\) since \(Q\) can be implemented by a queue or a stack. In Line [line:extrho_pre], to initialize \(Q\), we evaluate \(\omega_{V\setminus Y}(u)\) for each \(u \in V \setminus Y\), which can be done in \(O(n\tau_\omega)\) time.

We claim that, during the algorithm, each vertex \(v\) is inserted into \(Q\) at most once. It is inserted into \(Q\) in Line [line:extrho95pre] or [line:extrho95if95Q95update] when \(\omega_{V\setminus Y}(v) \not\geqslant \theta\) holds. Once \(v\) is inserted into \(Q\), it continues to belong to \(Q\) until it is picked up as \(u\) in Line [line:extrho_while_select]. After that, Algorithm 5 halts or it is inserted into \(Y\) and is not inserted to \(Q\) again, showing the claim. We see that a vertex \(v\) is inserted into \(Q\) when \(\omega_{V\setminus Y}(v) \not\geqslant \theta\) holds for the first time. This can happen only when a neighbor \(u\in N_G(v)\) is added to \(Y\) in Line [line:extrho_insertY] since \(\omega\) is local monotone. Then in Line [line:extrho_for], it suffices to search \(N_G(u) \setminus (Y \cup Q)\), instead of \(V \setminus (Y \cup Q)\), for vertices \(w\) such that \(\omega_{V\setminus Y}(w)\not\geqslant\theta\). The for-loop of Line [line:extrho_for] takes \(O(n+m\tau_\omega)\) time in all.

In Line [line:extrho_if], we decide whether there is \(\mathcal{B}'\in\mathbb{B}\) \((\mathcal{B}'\ne\mathcal{B})\) such that \(N^{\mathrm{pr}+}_\mathcal{S}[u]\cap B'\neq\emptyset\) for some \(B'\in\mathcal{B}'\), which can be done in \(O(\deg_G(u))\) time. Summing over all vertices, the total time is \(O(n+m)\). We see that Algorithm 5 runs in \(O((n+m)\tau_\omega)\) time.

For the space complexity, we use \(O(n+m)\) space to store the underlying graph \(G\), the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\) and sets such as \(Y\) and \(Q\). We also use \(\kappa_\omega\) space to compute \(\omega_S(u)\) for a vertex \(u\) and a subset \(S\subseteq V\). Thus, Algorithm 5 runs in \(O(n+m+\kappa_\omega)\) space. \(\Box\)

For the correctness, see the discussion on Algorithm [alg:local_minrs] in Section [sec:mono_alg]. Here we analyze the complexity.

The most time-consuming part is the for-loop from Line [line:for_MB_local_minrs] to [line:local95minrs95returned]. A rough analysis may be as follows; the for-loop takes \(O(|\mathbb{B}|(n+m)\tau_\omega)=O((n+m)n\tau_\omega)\) time since Algorithm 5 runs in \(O((n+m)\tau_\omega)\) time by Lemma [lem:1-br_local]. The repeat-loop from Line [line:local_minrs_repeat_start] to [line:local95minrs95repeat95end] iterates \(O(\log n)\) times by Lemma 5(iv), and the overall time complexity is \(O((n+m)n\log n\cdot\tau_\omega)\).

We claim that the \(O(\log n)\) factor can be dropped from the above time bound. Observe that, in the for-loop from Line [line:for_MB_local_minrs] to [line:local95minrs95returned], Algorithm 5 is executed only for a seed-subset node \(\mathcal{B}\in\mathbb{B}\) with \(\ifmmode\text{\normalfont\scshape in-Tree}\else{\normalfont\scshape in-Tree}\fi(\mathcal{B})=\ifmmode\text{\normalfont\scshape False}\else{\normalfont\scshape False}\fi\). Let \(s\) denote the number of seed-subset nodes \(\mathcal{B}\) with \(\ifmmode\text{\normalfont\scshape in-Tree}\else{\normalfont\scshape in-Tree}\fi(\mathcal{B})=\ifmmode\text{\normalfont\scshape False}\else{\normalfont\scshape False}\fi\). We can implement the for-loop so that it iterates precisely \(s\) times; e.g., by maintaining the \(s\) seed-subset nodes by queue.

It holds that \(s=n\) in the first iteration of the repeat-loop, and in subsequent iterations, \(s\) is the number of functional WCCs in the 1-SR digraph of the last iteration. Similarly to Lemma 5(iv), we can show that the number \(s\) is at most halved in the next iteration. Therefore, the for-loop from Line [line:for_MB_local_minrs] to [line:local95minrs95returned] iterates at most \(n+\frac{1}{2}n+(\frac{1}{2})^2n+\dots=O(n)\) times, indicating that Algorithm 5 is called \(O(n)\) times over an execution of Algorithm [alg:local_minrs], showing the claim.

In Line [line:if_F_not_empty_local_minrs], we can compute required WCCs of \(H=(\mathbb{B},F)\) by running a graph search algorithm from each seed-subset node \(\mathcal{B}\in\mathbb{B}\) with \(\ifmmode\text{\normalfont\scshape in-Tree}\else{\normalfont\scshape in-Tree}\fi(\mathcal{B})=\ifmmode\text{\normalfont\scshape False}\else{\normalfont\scshape False}\fi\). The size of WCCs is \(O(s)\) and this part takes \(O(s)\) time per iteration of the repeat-loop, and thus \(O(n)\) time over the algorithm. One can readily see that the time complexity of the remaining parts is \(O((n+m)n\tau_\omega)\).

For the space complexity, we use \(O(n+m)\) space to store the underlying graph \(G\), the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\) and sets such as \(Y\) and \(Q\) for Algorithm 5, and we use \(O(n)\) space to store the 1-SR digraph \(H=(\mathbb{B},F)\) and the pointed partition \(\mathbb{B}\). In addition, we use \(O(n + m + \kappa_\omega)\) space in each execution of Algorithm 5. Thus, the overall space complexity is \(O(n+m+\kappa_\omega)\). \(\Box\)

4.1.0.1 Proof of Theorem [thm:main_local_system].

Based on the discussion at the beginning of this subsection, it suffices to consider the case when \(V\) is a \(\theta\)-solution. We can construct the propagation graph and compute the SCC decomposition in \(O((n+m)\tau_\omega)\) time and \(O(n+m+\kappa_\omega)\) space. By Lemma [lem:local_minrs], Algorithm [alg:local_minrs] outputs all MinRSs of \(V\) in \(O((n+m)n\tau_\omega)\) time and \(O(n+m+\kappa_\omega)\) space, showing Theorem [thm:main_local_system]. \(\Box\)

4.2 Efficiency Enabled by In-Dominating Seed Property↩︎

For a digraph \(D=(V,A)\), a subset \(S \subseteq V\) is an in-dominating set in \(D\) if, for every vertex \(u \in V \setminus S\), there is a vertex \(v \in S\) such that \((u,v) \in A\), i.e., \(N^+_D(u) \cap S \neq \emptyset\) holds. We say that a monotone system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,\theta)\), not necessarily local, satisfies the in-dominating seed property if the set \(\cup\mathcal{B}^\mathrm{pr}_\mathcal{S}\) of seed vertices is an in-dominating set in the propagation graph \(H^{\mathrm{pr}}_\mathcal{S}\).

Let \(\mathcal{B}\subseteq \mathcal{B}^\mathrm{pr}_\mathcal{S}\) be a subset of seeds in the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\). We define \(C_\mathcal{B}\) to be the set of elements \(u\in V\) such that, for any closed out-neighbor \(v\in N^{\mathrm{pr}+}_\mathcal{S}[u]\) in the propagation digraph, \(v\) belongs to \(\cup\mathcal{B}\) whenever \(v\) is a seed vertex, that is, \[\begin{align} C_\mathcal{B} &\triangleq \{u \in V \mid N^{\mathrm{pr}+}_\mathcal{S}[u] \cap (\cup\mathcal{B}^\mathrm{pr}_\mathcal{S}) \subseteq (\cup\mathcal{B}) \} = \{u \in V \mid N^{\mathrm{pr}+}_\mathcal{S}[u] \cap (\cup\mathcal{B}^\mathrm{pr}_\mathcal{S}\setminus \cup\mathcal{B}) = \emptyset \} \nonumber\\ &= \{ u \in V \mid \text{\(N^{\mathrm{pr}+}_\mathcal{S}[u] \cap (\cup\mathcal{B}') = \emptyset \) for any \(\mathcal{B}' \in \mathbb{B}\setminus \{\mathcal{B}\}\)} \} \nonumber\\ &= \{ u \in V \mid \text{\(N^{\mathrm{pr}+}_\mathcal{S}[u] \cap B' = \emptyset\) for any \(B'\in\mathcal{B}'\) with \(\mathcal{B}'\neq\mathcal{B}\)} \}.\label{eq:C95MB} \end{align}\tag{1}\] Obviously we have \((\cup\mathcal{B})\subseteq C_\mathcal{B}\), and \(C_\mathcal{B}\setminus(\cup\mathcal{B})\) is the set of elements \(u\in V\) such that every out-neighbor of \(u\) that is a seed vertex belongs to a seed in \(\mathcal{B}\).

Given a monotone system \(\mathcal{S}\), let \(\mathbb{B}\) be a partition of the seed set \(\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\). The following lemma says that, if \(\mathcal{S}\) satisfies the in-dominating seed property, then \(C_\mathcal{B}\cap C_{\mathcal{B}'}=\emptyset\) holds for any \(\mathcal{B},\mathcal{B}'\in\mathbb{B}\).

Suppose \(C_\mathcal{B}\cap C_{\mathcal{B}'}\ne\emptyset\) for contradiction. Let \(v\in C_\mathcal{B}\cap C_{\mathcal{B}'}\). By the definition of \(C_\mathcal{B}\) and \(C_{\mathcal{B}'}\), we have \(N^{\mathrm{pr}+}_\mathcal{S}[v] \cap (\cup\mathcal{B}^\mathrm{pr}_\mathcal{S})\subseteq ((\cup\mathcal{B})\cap(\cup\mathcal{B}'))=\emptyset\), where the last equality holds by \(\mathcal{B}\cap\mathcal{B}'=\emptyset\). We claim that \(v\) is not a seed vertex (i.e., \(v\in(\cup\mathcal{B}^\mathrm{pr}_\mathcal{S})\)), since otherwise \(N^{\mathrm{pr}+}_\mathcal{S}[v] \cap (\cup\mathcal{B}^\mathrm{pr}_\mathcal{S})\) would not be empty. In the propagation digraph, by \(N^{\mathrm{pr}+}_\mathcal{S}[v] \cap (\cup\mathcal{B}^\mathrm{pr}_\mathcal{S})=\emptyset\), no out-neighbor of \(v\) would be a seed vertex, indicating that \(\cup\mathcal{B}^{\mathrm{pr}}_\mathcal{S}\) is not in-dominating, a contradiction. \(\Box\)

Observe that, if \(\mathcal{S}\) does not satisfy the in-dominating seed property, then \(C_\mathcal{B}\cap C_{\mathcal{B}'}\) is not empty; there is a vertex \(v\in V\) such that no out-neighbor is a seed vertex, and \(v\) belongs to both \(C_\mathcal{B}\) and \(C_{\mathcal{B}'}\) by the definition.

4.2.0.1 Proof of Theorem 2.

In Algorithm [alg:local_minrs], recall that the repeat-loop from Line [line:local_minrs_repeat_start] to [line:local95minrs95repeat95end] iterates \(O(\log n)\) times by Lemma 5(iv). We show that the most time-consuming part, the for-loop from Line [line:for_MB_local_minrs] to [line:local95minrs95returned], can be done in \(O(n+m)\) time per iteration of the repeat-loop.

Let \(\mathbb{B}=\{\mathcal{B}_1,\mathcal{B}_2,\dots,\mathcal{B}_z\}\) denote the pointed partition at the beginning of any iteration of the repeat-loop. For \(v\in V\), let \(\ell(v)\mathrel{\vcenter{:}}=\{i\in[1,z]\mid N^{\mathrm{pr}+}_\mathcal{S}[v]\cap(\cup\mathcal{B}_i)\ne\emptyset\}\). The system \(\mathcal{S}\) satisfies the in-dominating property and hence \(|\ell(v)|\ge1\) holds for all \(v\in V\), and \(v\in C_{\mathcal{B}_i}\) holds when and only when \(\ell(v)=\{i\}\). We compute \(\ell(v)\) for all \(v\in V\) as a preprocessing of the for-loop, which can be done in \(O(n+m)\) time.

In each iteration of the for-loop, we execute Algorithm 5 for each \(\mathcal{B}_i\in\mathbb{B}\) such that \(\ifmmode\text{\normalfont\scshape in-Tree}\else{\normalfont\scshape in-Tree}\fi(\mathcal{B}_i)=\ifmmode\text{\normalfont\scshape False}\else{\normalfont\scshape False}\fi\). We claim that the time complexity is \(O(|C_{\mathcal{B}_i}|+|E[C_{\mathcal{B}_i}]|+|E(C_{\mathcal{B}_i})|)\), where \(E[C_{\mathcal{B}_i}]\) (resp., \(E(C_{\mathcal{B}_i})\)) is the subset of edges in the underlying graph \(G=(V,E)\) such that both endpoints belong to \(C_{\mathcal{B}_i}\) (resp., exactly one of the endpoints belong to \(C_{\mathcal{B}_i}\)). To show the claim, in Algorithm 5, recall that each vertex is inserted into \(Q\) at most once; see the proof for Lemma [lem:1-br_local]. Let \(u\) denote any vertex chosen in Line [line:extrho_while_select]. The algorithm terminates if the condition in Line [line:extrho_if] is satisfied, that is, there are \(\mathcal{B}_j\in\mathbb{B}\) \((\mathcal{B}_j\ne\mathcal{B}_i)\) and \(B'\in\mathcal{B}_j\) such that \(N^{\mathrm{pr}+}_\mathcal{S}[u]\cap B'\ne\emptyset\). In this case, \(u\not\in C_{\mathcal{B}_i}\) holds by ([eq:C_MB]). We can decide whether \(u\in C_{\mathcal{B}_i}\) or not in constant time using \(\ell(u)\); if \(\ell(u)=\{i\}\), then \(u\in C_{\mathcal{B}_i}\) holds, and otherwise, \(u\notin C_{\mathcal{B}_i}\) holds. We can run Algorithm 5 runs in linear time with respect to \(|C_{\mathcal{B}_i}|\) and the number of arcs incident to \(C_{\mathcal{B}_i}\), that is \(|E[C_{\mathcal{B}_i}]|+|E(C_{\mathcal{B}_i})|\).

Finally we see that \(\sum_{i=1}^zO(|C_{\mathcal{B}_i}|+|E[C_{\mathcal{B}_i}]|+|E(C_{\mathcal{B}_i})|)=O(n+m)\) since \(C_{\mathcal{B}_i}\cap C_{\mathcal{B}_j}=\emptyset\), \(i,j\in[1,z]\) \((i\ne j)\) by Lemma [lem:C_disjoint], as required.

The space complexity follows by Theorem [thm:main_local_system]. \(\Box\)

4.3 Application Examples↩︎

We show that the MinRSs of a \(k\)-core \(G=(V,E)\) can be computed in \(O((n+m)\log n)\) time, as a proof for Theorem 3. For this, we prove that the local monotone system that is defined somehow based on \(k\)-cores satisfies the in-dominating seed property. Then we can apply Theorem 2 to the system.

There are a lot of extensions of \(k\)-cores [3]. It is easy to see that each extension determines a similar local monotone system, and that, by Theorem [thm:main_local_system], we can enumerate all MinRSs of an extended \(k\)-core in \(O((n+m)n)\) time. So far we have not found any extensions such that the bounds can be improved by using Theorem 2; in these cases, the in-dominating seed property does not hold.

This paper has focused on enumerating MinRSs of a ground set \(V\) of a local monotone system \(\mathcal{S}(V,\mathcal{Z},\omega,\theta;G)\). We show that, using the notion of SD property [25], we can enumerate all \(\theta\)-solutions efficiently. In particular, for standard \(k\)-cores in undirected graphs, the resulting algorithm achieves a better time complexity than Boley et al.’s framework [24].

4.3.1 Enumeration of MinRSs of \(k\)-Cores↩︎

For a positive integer \(k\), let \(G=(V,E)\) be a \(k\)-core graph; \(\mathcal{Z}=(\mathbb{Z},\le)\); and \(\omega\) denote the function such that \(\omega_S(u)=\deg_{G[S\cup\{u\}]}(u)\) for \(S\subseteq V\) and \(u\in V\). We see that \(\omega\) is local monotone. We denote \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,k;G)\), which is a local monotone system such that \(S\subseteq V\) is a \(k\)-solution if and only if \(S\) induces a \(k\)-core graph.

We show that \(\mathcal{S}\) satisfies the in-dominating seed property. Let us examine the structure of the propagation graph \(H^{\mathrm{pr}}_\mathcal{S}= (V, A^{\mathrm{pr}}_\mathcal{S})\), where the arc set is given by \(A^{\mathrm{pr}}_\mathcal{S}=\{(u,v)\in V\times V\mid \deg_{G - u}(v) < k\}\). The following lemma is obvious and will be used soon.

The sufficiency is obvious. For the necessity, we see that \(\deg_G(v)\ge k\) holds since \(G\) is a \(k\)-core graph. It holds that \(u\in N_G(v)\) by \(\deg_{G-u}(v)<k\le\deg_G(v)\). Further, \(\deg_G(v)=k\) must hold by \(\deg_{G-u}(v)=\deg_G(v)-1\). \(\Box\)

We partition the vertex set \(V\) of a \(k\)-core graph \(G=(V,E)\) into \(V=V_1\sqcup V_2\sqcup V_3\) such that \(V_1 := \{ v \in V \mid \deg_G(v) > k \text{ and } \deg_G(u) > k \text{ for any } u \in N_G(v) \}\); \(V_2 := \{ v \in V \mid \deg_G(v) > k \text{ and } \deg_G(u) = k \text{ for some } u \in N_G(v) \}\); and \(V_3 := \{ v \in V \mid \deg_G(v) = k \}\). The following lemma analyzes the structure of the propagation graph \(H^{\mathrm{pr}}_\mathcal{S}= (V, A^{\mathrm{pr}}_\mathcal{S})\). In particular, (v) says that \(\mathcal{S}\) satisfies the in-dominating seed property.

By Lemma [lem:deg-at-least-k_degree_condition], the arc set of the propagation graph \(H^{\mathrm{pr}}_\mathcal{S}\) is \(A^{\mathrm{pr}}_\mathcal{S}=\{(u,v)\in V\times V \mid \deg_G(v)=k\;\text{and}\;u\in N_G(v)\}\).

(i) If there is \((u,v)\in A^{\mathrm{pr}}_\mathcal{S}\), then \(\deg_G(v)=k\) holds by the definition, and hence \(v\in V_3\). If \(v\in V_3\), then \(\deg_G(v)=k\geq 1\) and hence \(v\) has a neighbor \(u\) in \(G\). Then \((u,v)\in A^{\mathrm{pr}}_\mathcal{S}\) holds.

(ii) Let \(v\in V_1\). Since every neighbor of \(v\) has degree at least \(k+1\), no arc leaves \(v\). Moreover, by (i), no arc enters \(v\). Hence \(v\) is isolated in \(H^{\mathrm{pr}}_\mathcal{S}\), and \(\{ v \}\) is a seed.

(iii) Let \(v\in V_2\). By definition, \(v\) has a neighbor \(u\in V_3\), and hence \((v,u)\in A^{\mathrm{pr}}_\mathcal{S}\). On the other hand, by (i), no arc enters \(v\). Therefore \(v\) cannot belong to any seed.

(iv) By (ii), \(\{u\}\) is a seed for each \(u\in V_1\). By (iii), no vertex in \(V_2\) belongs to a seed. For \(u\in V_3\), if \(u\) has no outgoing arcs in \(H^{\mathrm{pr}}_\mathcal{S}\), then \(\{u\}\) is a seed. Otherwise, there is an arc \((u,v)\) in \(H^{\mathrm{pr}}_\mathcal{S}\), and \(v\in V_3\) holds by (i). This indicates the arc \((v,u)\) also exists in \(H^{\mathrm{pr}}_\mathcal{S}\), and hence \(u\) and \(v\) belong to the same SCC. This SCC should be a seed since no arc from \(V_3\) to \(V_j\), \(j\in[1,2]\) can exist by (i).

(v) For \(u\in V\setminus (V_1\cup V_3)=V_2\), there is an arc \((u,v)\in A^{\mathrm{pr}}_\mathcal{S}\) such that \(v\in V_3\). We see that \(v\in V_3\subseteq (\cup\mathcal{B}^{\mathrm{pr}}_\mathcal{S})\) holds, where the latter relationship is due to (iv). \(\Box\)

4.3.1.1 Proof of Theorem 3.

By Lemma [lem:deg-at-least-k_propagation_graph](v), the local monotone system \(\mathcal{S}\) satisfies the in-dominating seed property. By Theorem 2, we can enumerate all MinRSs of \(G\) in \(O((n+m)\log n\cdot\tau_\omega)\) time and \(O(n+m+\kappa_\omega)\) space.

We show that we can implement the algorithm so that \(\tau_\omega=O(1)\) and \(\kappa_\omega=O(n+m)\). Observe that, in the MinRS enumeration algorithm, we compute \(\omega_S(v)=\deg_S(v)\) for \((S,v)\in 2^V\times V\) in Lines [line:extrho95pre] and [line:extrho95if95Q95update] of Algorithm 5. Specifically, we compute \(\omega_{V\setminus Y}(v)\) for a subset \(Y\subseteq V\) of vertices, and the set \(Y\) is non-decreasing with respect to set-inclusion, during a single execution of Algorithm 5.

During Algorithm 5, we maintain the degree \(\omega_{V\setminus Y}(v)\) for the present \(Y\subseteq V\) and each \(v\in V\) in an array. Clearly, if a vertex \(u\) is added to \(Y\), then we decrease by one the entry of each neighbor \(v\in N_G(u)\), which can be done in \(O(1)\) time per \(v\), indicating \(\tau_\omega=O(1)\). This array is first initialized in the preprocessing of Algorithm [alg:local_minrs]. Algorithm 5 may update the array during its execution, and when it terminates, we restore the array in linear time with respect to the number of visited vertices. It is easy to see \(\kappa_\omega=O(n+m)\). The overall complexity is not affected in the big-O notation. \(\Box\)

4.3.2 Enumeration of MinRSs of Extended \(k\)-Cores↩︎

Our framework is applicable to extensions of \(k\)-cores. We take up weighted \(k\)-cores [15]; multi-layer \(\boldsymbol{k}\)-cores [16]; and \((k,\ell)\)-cores [14] here. See [3] for other examples.

4.3.2.1 Weighted \(k\)-Cores [15].

We denote by \(\mathbb{R}_{\ge 0}\) the set of non-negative reals. Let \(\mathcal{N}=[G,w]\) be a network that consists of an undirected graph \(G=(V,E)\) and an edge-weight function \(w:E\to\mathbb{R}_{\ge 0}\). The weighted degree of a vertex \(v\in V\) is defined to be \(\sum_{u\in N_G(v)} w(uv)\). Let \(k\in\mathbb{R}_{\ge 0}\) be a constant. A subset \(S\subseteq V\) is the weighted \(k\)-core (of \(\mathcal{N}\)) if it is the maximal subset such that every weighted degree in \(G[S]\) is no less than \(k\). The graph \(G\) is a weighted \(k\)-core graph if \(G\) itself is the weighted \(k\)-core of \(G\).

Let \(\mathcal{Z}=(\mathbb{R}_{\ge0},\le)\); and \(\omega:2^V\times V\to\mathbb{R}_{\ge0}\) denote the function such that \(\omega_S(v)=\sum_{u\in N_{S\cup\{v\}}(v)} w(uv)\), \(S\subseteq V\), \(v\in V\). One readily sees that \(\omega\) is local monotone. The system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,k;\mathcal{N})\) is local monotone such that \(S\subseteq V\) is a \(k\)-solution if and only if it induces a weighted \(k\)-core graph.

We can enumerate MinRSs of a weighted \(k\)-core in \(O((n+m)n)\) time and \(O(n+m)\) space by Theorem [thm:main_local_system], where we can implement the algorithm so that \(\tau_\omega=O(1)\) and \(\kappa_\omega=O(n+m)\) hold, in an analogous manner with (unweighted) \(k\)-cores; see the proof of Theorem 3.

The system does not satisfy the in-dominating seed property in general. See Figure [fig:weight-and-sumdegree_counterexample]. Consider a local monotone system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,k;\mathcal{N})\) such that \(k=2\) and \(\mathcal{N}=[G,w]\) is a network that corresponds to an edge-weighted graph in (i). The propagation digraph is shown in (ii). We see that the in-dominating seed property does not hold; the seed set is \(\mathcal{B}^{\mathrm{pr}}_\mathcal{S}=\{\{v_1\},\{v_3\},\{v_5\}\}\), and hence \(\cup\mathcal{B}^{\mathrm{pr}}_\mathcal{S}=\{v_1,v_3,v_5\}\). This set is not in-dominating in the propagation digraph since there is no outgoing arc from \(v_2\notin(\cup\mathcal{B}^{\mathrm{pr}}_\mathcal{S})\) to any of \(\cup\mathcal{B}^{\mathrm{pr}}_\mathcal{S}=\{v_1,v_3,v_5\}\).

4.3.2.2 Multi-layer \(\boldsymbol{k}\)-Cores [16].

Let \(r\) be a positive integer and \(G_i=(V,E_i)\), \(i\in[1,r]\) be graphs such that \(V\) is the common vertex set. For \(r\)-dimensional vectors \(\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^r\), we write \(\boldsymbol{x}\leqslant\boldsymbol{y}\) if \(x_i\le y_i\) holds for each \(i\in[1,r]\), where we denote \(\boldsymbol{x}=(x_1,x_2,\dots,x_r)\) and \(\boldsymbol{y}=(y_1,y_2,\dots,y_r)\). Obviously \(\leqslant\) is a partial order on \(\mathbb{R}^r\). We define a function \(\omega:2^V\times V\to\mathbb{R}^r\) to be \(\omega_S(v)\mathrel{\vcenter{:}}=(\deg_{G_1[S]}(v),\deg_{G_2[S]}(v),\dots,\deg_{G_r[S]}(v))\), \(S\subseteq V\), \(v\in V\). For \(\boldsymbol{k}\in\mathbb{R}^r\), a subset \(S\subseteq V\) is the multi-layer \(\boldsymbol{k}\)-core (of \(\mathcal{G}=\{G_1,G_2,\dots,G_r\}\)) if it is the maximal subset such that \(\omega_S(v)\geqslant\boldsymbol{k}\) holds for every \(v\in S\). The definition of a multi-layer \(\boldsymbol{k}\)-core graph is analogous.

Let \(\mathcal{Z}=(\mathbb{R}^r,\leqslant)\) denote a poset. The set system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,\boldsymbol{k};\mathcal{G})\) is local monotone since the function \(\omega\) is local monotone. A subset \(S\subseteq V\) is a \(\boldsymbol{k}\)-solution if and only if it induces a multi-layer \(\boldsymbol{k}\)-core graph. It is easy to show that the arc set of the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\) is the union of those of the analogous propagation digraphs for \(G_1,G_2,\dots,G_r\). By Theorem [thm:main_local_system], we can enumerate MinRSs of \(V\) in \(O((n+M)n)\) time and \(O(n+M)\) space, where we denote \(M=|E_1|+|E_2|+\dots+|E_r|\).

We cannot utilize Theorem 2 to improve the time bound since the in-dominating seed property does not hold in general; See Figure [fig:multi-layer_counterexample]. In this example, we use \(V=\{v_1,v_2,\dots,v_{11}\}\), \(r=2\) and \(\boldsymbol{k}=(2,2)\). The two underlying graphs \(G_1\) and \(G_2\) are shown in (i) and (ii), respectively. For the local monotone system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,\boldsymbol{k};\mathcal{G}=\{G_1,G_2\})\), the propagation digraph \(H^{\mathrm{pr}}_\mathcal{S}\) is shown in (iii). Observe that the arc set of \(H^{\mathrm{pr}}_\mathcal{S}\) is the union of the arc sets of the propagation graphs that are constructed independently for \(G_1\) and \(G_2\). The seed set of \(H^{\mathrm{pr}}_\mathcal{S}\) is \(\mathcal{B}^{\mathrm{pr}}_\mathcal{S}=\{\{v_5\},\{v_6\},\{v_7\},\{v_8\},\{v_9,v_{10},v_{12}\}\}\), and \(v_4\) has no outgoing arc to any of them. Then \(\cup\mathcal{B}^{\mathrm{pr}}_\mathcal{S}=\{v_5,v_6,\dots,v_{10},v_{12}\}\) is not an in-dominating set in \(H^{\mathrm{pr}}_\mathcal{S}\).

Multi-layer \(\boldsymbol{k}\)-cores can be extended further; an underlying graph \(G_i\), \(i\in[1,r]\), can be directed. For a function \(\omega:2^V\times V\to\mathbb{R}^r\), write \(\omega_S(v)=(\omega^{(i)}_S(v))_{i=1}^r\) for \(S\subseteq V\) and \(v\in V\). Then any local monotone function \(\omega^{(i)}:2^V\times V\to\mathbb{R}\) can be utilized for each \(i\in[1,r]\).

4.3.2.3 \((k,\ell)\)-Cores [14].

We introduce \((k,\ell)\)-cores as an example of such extensions of multi-layer \(\boldsymbol{k}\)-cores. Let \(k,\ell\in\mathbb{Z}\) be constants. For a digraph \(D=(V,A)\), a subset \(S\subseteq V\) (or \(D[S]\)) is a \((k,\ell)\)-core of \(D\) if \(D[S]\) is the maximal subgraph such that the minimum out-degree is no less than \(k\) and the minimum in-degree is no less than \(\ell\). The definition of a \((k,\ell)\)-core graph is analogous.

Let \(\mathcal{Z}=(\mathbb{Z}^2,\leqslant)\) denote a poset. We define the function \(\omega:2^V\times V\) to be \(\omega_S(v)\mathrel{\vcenter{:}}=(\deg^+_S(v),\deg^-_S(v))\), \(S\subseteq V\), \(v\in V\). Let \(\boldsymbol{\theta}=(k,\ell)\) and \(\mathcal{G}=\{G,G\}\). The system \(\mathcal{S}=\mathcal{S}(V,\mathcal{Z},\omega,\boldsymbol{\theta};\mathcal{G})\) is local monotone, and a subset \(S\subseteq V\) is a \(\boldsymbol{\theta}\)-solution if and only if it induces a \((k,\ell)\)-core graph. By Theorem [thm:main_local_system], we can enumerate MinRSs of \(V\) in \(O((n+m)n)\) time and \(O(n+m)\) space.

4.3.3 Enumeration of All \(\theta\)-Solutions↩︎

Finally, we show how to enumerate all \(\theta\)-solutions in a monotone system, utilizing our framework.

For a ground set \(U\) and \(\mathcal{F}\subseteq 2^U\), a set system \((U,\mathcal{F})\) satisfies the subset-disjoint (SD) property [25] if, for any \(X,X'\in\mathcal{F}\) with \(X'\subsetneq X\) and any MinRS \(Y\) of \(X\), either \(Y\subseteq X'\) or \(Y\cap X'=\emptyset\) holds. We define a MinRS oracle to be an oracle that returns a MinRS \(Y\) of \(X\) such that \(Y\cap Z=\emptyset\) if one exists, where \(X\in\mathcal{F}\) and \(Z\subseteq X\) are given as a query to the oracle.

For an enumeration algorithm, the delay is a crucial performance measure [26], which refers to time taken (i) between the start of the algorithm and the output of the first solution; (ii) between the output of any two consecutive solutions; and (iii) between the output of the last solution and the termination of the algorithm. An algorithm is said to be polynomial delay if its delay is bounded by a polynomial function of the input size.

We can enumerate all \(\theta\)-solutions in a monotone system \(\mathcal{S}(V,\mathcal{Z},\omega,\theta)\) efficiently by Theorem [thm:TH.2025] and the following lemma.

For any monotone system \(\mathcal{S}(V,\mathcal{Z},\omega,\theta)\), let \(X_1,X_2\) be \(\theta\)-solutions such that \(X_1\supsetneq X_2\). For any MinRS \(Y\) of \(X_1\), we show that either \(Y\cap X_2=\emptyset\) or \(Y\subseteq X_2\) holds. Suppose that \(Y\cap X_2\ne\emptyset\). Let \(Y'\mathrel{\vcenter{:}}= Y\setminus X_2\), where \(Y'\subsetneq Y\). We see \(X_2\subsetneq X_1\setminus Y'\), and for \(v\in Y\cap X_2\), we have \(\theta\leqslant\omega_{X_2}(v)\leqslant\omega_{X_1\setminus Y'}(v)\). For \(u\in X_1\setminus Y\), we have \(\theta\leqslant\omega_{X_1\setminus Y}(u)\leqslant\omega_{X_1\setminus Y'}(u)\). If \(Y'\ne\emptyset\) (i.e., \(Y\not\subseteq X_2\)), then \(Y'\) would be an RS of \(X_1\), contradicting the minimality of \(Y\). \(\Box\)

For our purpose, it suffices to design an algorithm to generate MinRSs of any \(\theta\)-solution. We can utilize Algorithm [alg:local_minrs] although it is designed to enumerate MinRSs of the ground set \(V\); for \(S\subseteq V\), the restriction of the monotone system to \(S\) is also a monotone system.

For local monotone systems, we have the following corollary to Theorems 1 and 2.

We also have the following corollary to Theorem 3.

4.3.3.1 Comparison with Boley et al.’s Work [24].

A set system \((U,\mathcal{F})\) is strongly accessible if it is accessible (i.e., for all \(X\in\mathcal{F}\), there is \(e\in X\) such that \(X\setminus\{e\}\in\mathcal{F}\)); and for any \(X,Y\in\mathcal{F}\) such that \(X\subsetneq Y\), there is \(e\in Y\setminus X\) such that \(X\cup\{e\}\in\mathcal{F}\). Given a strongly accessible system \((U,\mathcal{F})\) and a closure operator \(\rho:\mathcal{F}\to\mathcal{F}\), Boley et al. [24] developed an algorithm that enumerates all fixed points with respect to \(\rho\) (i.e., all sets \(C\in\mathcal{F}\) that satisfy \(\rho(C)=C\)) in \(O(n(\tau_{\mathrm{mem}}+\tau_{\mathrm{clo}}+n))\) delay, where \(n=|U|\) and \(\tau_{\mathrm{mem}}\) and \(\tau_{\mathrm{clo}}\) denote the computation time for a membership oracle and for computing the closure \(\rho(S)\) of any subset \(S\subseteq U\), respectively.

Their framework on a strongly accessible system \((U,\mathcal{F})\) can be used to find all \(\theta\)-solutions in a monotone system \(\mathcal{S}(V,\mathcal{Z},\omega,\theta)\) by setting \(U=V\), \(\mathcal{F}=2^V\) and \(\rho\) to the closure operator that we defined in Section [sec:mmw_prop]. For example, for a given undirected graph \(G=(V,E)\), let us consider the problem of enumerating all \(S\subseteq V\) such that \(G[S]\) is a \(k\)-core graph. We can implement their algorithm so that \(\tau_{\mathrm{mem}}=O(1)\) and \(\tau_{\mathrm{clo}}=O(n+m)\) hold, and hence the delay is \(O((n+m)n)\). It is notable that Corollary 2 achieves a better delay bound than this straightforward application of Boley et al.’s framework.

5 Concluding Remarks↩︎

In this paper, we proposed a general framework based on monotone systems to systematically study the enumeration of MinRSs and \(\theta\)-solutions, generalizing \(k\)-cores and their various extensions. By introducing the propagation digraph and the SR digraph, we characterized the structural properties of MinRSs. Under this framework, we developed efficient algorithms for local monotone systems, achieving a time complexity of \(O((n+m)\log n \cdot \tau_{\omega})\) for systems satisfying the in-dominating seed property. For undirected \(k\)-cores, we proved that this property holds, leading to an \(O((n+m)\log n)\) time algorithm for MinRS enumeration and an \(O((n+m)\log n)\) delay algorithm for \(\theta\)-solution enumeration. The latter delay bound is a significant improvement over the \(O((n+m)n)\) delay achieved by Boley et al.’s strong accessibility-based framework [24].

We conclude this paper by highlighting several directions for future work. (1) Our algorithm still has much room for further investigation. In particular, although we introduced two auxiliary digraphs and tailored them for our purpose, a deeper theoretical understanding of their properties is required. It would be interesting to explore the applicability of the algorithm to problems of finding minimal closures. (2) Characterization of the in-dominating seed property. We showed that the in-dominating seed property enables a more efficient algorithm. However, within the scope of this study, the standard \(k\)-core is the only model for which this property holds; it fails to hold for many of its extensions. Clarifying the underlying factors that cause this difference remains a key open question. We are also interested in investigating weaker versions of the property that still guarantee computational efficiency. (3) Empirical evaluations on large-scale real-world networks are needed to demonstrate the practical performance and scalability of our proposed algorithms compared to baseline approaches.

References↩︎

---

1. Graduate School of Informatics, Kyoto University, shota.kan@amp.i.kyoto-u.ac.jp↩︎

2. Department of Logistics and Information Engineering, Tokyo University of Marine Science and Technology, haraguchi@kaiyodai.ac.jp↩︎

3. This work is partially supported by JSPS KAKENHI 25K14993.↩︎