Two New Upper Bounds for the Maximum $k$-plex Problem

Given an undirected graph $G=(V,E)$, where $V$ is the vertex set and $E$ the edge set, the density of $G$ is $2|E|/(|V|(|V|-1))$, we denote $N(v)$ as the set of vertices adjacent to $v$, which are also called the neighbors of $v$. Given a vertex set $S\subseteq V$, we denote $G[S]$ as the subgraph induced by $S$. Given an integer $k$, $S\subseteq V$ is a $k$-plex if each vertex $v\in S$ satisfies that $|S\backslash N(v)|\leq k$.

For a growing partial $k$-plex $S$, we define $\omega_{k}(G,S)$ as the size of the maximum $k$-plex that includes all vertices in $S$, and $\delta(S,v)=|S\backslash N(v)|$ as the number of non-neighbors of vertex $v$ in $S$. Given an integer $k$, we further define $\delta_{k}^{-}(S,v)=k-\delta(S,v)$ to facilitate our algorithm description. If $v\in S$, $\delta_{k}^{-}(S,v)$ indicates the maximum number of non-adjacent vertices of $v$ that can be added to $S$. Otherwise, it indicates that, including $v$ itself, the maximum number of its non-adjacent vertices that can be added to $S$.

During the course of a general BnB MKP algorithm, a lower bound $lb$ on the size of the maximum $k$-plex is maintained, which is usually initialized by some heuristic algorithms Zhou et al. (2021); Jiang et al. (2021); Chang et al. (2022), and is updated once a larger $k$-plex is found.

A general BnB MKP algorithm usually contains a preprocessing stage and a BnB search stage. During the preprocessing, the algorithm uses some reduction rules Gao et al. (2018); Zhou et al. (2021); Chang et al. (2022) to remove vertices that are impossible to belong to a $k$-plex of size larger than $lb$. In the BnB search stage, the algorithm traverses the search tree to find the optimal solution. During the search, the algorithm always maintains two vertex sets, the current growing partial $k$-plex $S$, and its corresponding candidate set $C$ containing vertices that might be added to $S$. Once the algorithm selects a branching vertex $v$ to be added to $S$ from $C$, it calculates an upper bound $ub$ on the size of the maximum $k$-plex that can be extended from $S\cup\{v\}$, and the branch of adding $v$ to $S$ will be pruned if $ub\leq lb$.

Since vertices in the candidate set $C$ might be non-adjacent to some vertices in the growing partial $k$-plex $S$, an independent set $I\subseteq C$ actually cannot provide $k$ vertices for $S$ sometimes even when $|I|>k$. We introduce a Tighter Independent Set Upper Bound (TISUB) on the number of vertices that an independent set $I\subseteq C$ can provide for $S$.

For convenience, in the rest of this paper, we regard the vertices in any independent set $I\subseteq C$, i.e., $\{v_{1},v_{2},\cdots,v_{|I|}\}$, as sorted in non-ascending order of their $\delta_{k}^{-}(S,v)$ values. We further define TISUB$(I,S)=\mathop{\max}\{i|\delta_{k}^{-}(S,v_{i})\geq i\}$ as the upper bound calculated by TISUB on the number of vertices that $I$ can provide for $S$. Note that the value of TISUB$(I,S)$ is obviously bounded by $|I|$ since $i\leq|I|$, which eliminates the need for term $|I|$ in TISUB. Moreover, since $\delta(S,v)\geq 0$, $\delta_{k}^{-}(S,v)\leq k$ holds, and TISUB$(I,S)$ is also bounded by $k$. Therefore, TISUB is strictly never worse than GCB (i.e., $\min\{|I|,k\}$).

Since the relaxation property of $k$-plex over clique, an independent set $I$ in the candidate set $C$ can usually provide more than one vertices for the growing the partial $k$-plex $S$, and the restriction of independent sets can also be relaxed to contain more vertices.

In the following, we define two kinds of vertices and then introduce two different rules for relaxing the restriction of independent sets and making maximal independent sets contain extra vertices without increasing their TISUB.

Given a maximal independent set $I\subseteq C$, both Rule 1 and Rule 2 can add extra vertices to $I$ without increasing its TISUB. Actually, Rule 1 allows us to add finite (at most TISUB$(I,S)$ - 1) conflict vertices to $I$, and Rule 2 can be repeatedly used to add any vertex satisfying the rule to $I$.

We provide an example in Figure 1 to show how the upper bounds, including GCB, TISUB, and RelaxGCB, are calculated and how the two rules are used. Figure 1 illustrates a subgraph of $G$ induced by the candidate set $C=\{v_{1},v_{2},\cdots,v_{8}\}$, i.e., $G[C]$, of a 4-plex $S$. To simplify the figure, we hide the 4-plex $S$ and only depict the candidate vertices. Vertex $v_{i}|t$ in Figure 1 identifies a vertex $v_{i}\in C$ with $\delta_{k}^{-}(S,v_{i})=t$.

Suppose we sequentially color vertices $v_{1},v_{2},\cdots,v_{8}$ under the constraint that adjacent vertices cannot be in the same color, $C$ can be partitioned into 3 independent sets, $I_{1}=\{v_{1},v_{2},v_{3}\}$, $I_{2}=\{v_{4},v_{5},v_{6},v_{8}\}$ and $I_{3}=\{v_{7}\}$, as indicated by the colors of the vertices. The GCB of $\omega_{4}(G,S)$ is $|S|+\sum_{i=1}^{3}{\min\{|I_{i}|,4\}}=|S|+3+4+1=|S|+8$. The TISUB of $\omega_{4}(G,S)$ is $|S|+\sum_{i=1}^{3}{\textit{TISUB}(I_{i},S)}=|S|+3+2+1=|S|+6$.

Then, let us use Rule 1 to make independent set $I_{1}$ contain more vertices. For $I_{1}$, since $\textit{TISUB}(I_{1},S)=3$, there is only one loose vertex $v_{1}$ in $I_{1}$. By applying Rule 1, we can add vertices $v_{6}$ and $v_{7}$ to $I_{1}$ without increasing the upper bound of $\omega_{4}(G[S\cup I_{1}],S)$, since there are only 3 loose or conflict vertices, i.e., $v_{1},v_{6},v_{7}$, in $I_{1}\cup\{v_{6},v_{7}\}$. After the operation, $C$ is partitioned into two sets, $I_{5}=I_{1}\cup\{v_{6},v_{7}\}$ and $I_{6}=\{v_{4},v_{5},v_{8}\}$. The new upper bound of $\omega_{4}(G,S)$ is $|S|+\textit{TISUB}(I_{5},S)+\textit{TISUB}(I_{6},S)=|S|+3+1=|S|+4$.

Finally, let us use Rule 2 to further make set $I_{5}$ contain more vertices. According to Rule 2, all vertices in $I_{6}$ can be added to $I_{5}$ without increasing the upper bound of $\omega_{4}(G[S\cup I_{5}],S)$. After the operation, the final RelaxGCB of $\omega_{4}(G,S)$ is $|S|+\textit{TISUB}(I_{5},S)=|S|+3$.

This subsection introduces our proposed RelaxColoring algorithm for calculating the proposed RelaxGCB, as summarized in Algorithm 1. The algorithm first uses $|S|$ to initialize the upper bound $UB$ (line 1), and then repeatedly uses the TryColor() function to extract a subset $I\subseteq C$ and calculate the upper bound on the number of vertices that $I$ can provide for $S$, i.e., $ub$ (line 3) until $C=\emptyset$ (line 2). After each execution of function TryColor(), the candidate set $C$ and upper bound $UB$ are both updated (line 4).

Function TryColor() is summarized in Algorithm 2, which first finds a maximal independent set $I\subseteq C$ (lines 1-3) and calculates its TISUB (line 4). Then, the algorithm initializes the set of loose or conflict vertices $LC$ (line 5) and tries to add as many vertices as possible to $I$ according to Rule 1 (lines 6-12). Once trying to add each vertex $v$, the algorithm uses $CV$ to denote the extra conflict vertices caused by adding $v$ to $I$ (line 8). Since $I$ is a maximal independent set in $C$, adding any vertex $v$ to $I$ increases at least one conflict vertices, i.e., $v$ itself (line 8). Thus, the utilization of Rule 1 can be terminated when $|LC|\geq ub$ (lines 6 and 12). Finally, the algorithm applies Rule 2 to further add vertices to $I$ (lines 13-15). Since for each vertex $v\in C\backslash I$, $|N(v)\cap I|>0$ holds, only vertex $v\in C\backslash I$ with $\delta_{k}^{-}(S,v)<ub$ can be added to $I$ according to Rule 2 (line 13).

The time complexities of RelaxColoring algorithm and TryColor function are $O(|C|^{2}\times T)$ and $O(|C|\times T)$, respectively, where $O(T)$ is the time complexity of the intersection operation between $N(v)$ and $I$ (or $I\backslash LC$) used in lines 3, 8, and 14 in Algorithm 2. Actually, $O(T)$ is bounded by $O(|V|)$ and much smaller than $O(|V|)$ by applying the bitset encoding method Segundo et al. (2011).

Given a growing partial $k$-plex $S$ and the corresponding candidate set $C$, for each vertex $v\in S$, DisePUB claims that a subset $I\subseteq C$ can provide at most $\min\{|I|,\delta_{k}^{-}(S,v)\}$ vertices for $S$ if $N(v)\cap I=\emptyset$. Given a vertex $v\in S$, let $I=C\backslash N(v)$ and $ub=\min\{|I|,\delta_{k}^{-}(S,v)\}$, DisePUB defines a metric for $I$, i.e., $dise(I)=|I|/ub$, to evaluate the extraction of vertex set $I$. The larger the value of $dise(I)$, the more vertices that can be extracted from $C$ and the fewer increments on the upper bound of $\omega_{k}(G,S)$.

In each step, DisePUB traverses each vertex $v\in S$ with $\delta_{k}^{-}(S,v)>0$ and selects the corresponding set $I=C\backslash N(v)$ with the largest value of $dise(I)$. Ties are broken by preferring larger extractions. We use function SelectPartition() to describe the selection, which is shown in Algorithm 3. Then, DisePUB extracts $C\backslash N(v)$ from $C$ and increases the upper bound of $\omega_{k}(G,S)$ by $\min\{|C\backslash N(v)|,\delta_{k}^{-}(S,v)\}$.

DisePUB repeats the above process until vertices remaining in $C$ are adjacent to all vertices in $S$. DisePUB denotes the set of remaining vertices in $C$ as $\pi_{0}$ and finally increases the upper bound of $\omega_{k}(G,S)$ by $|\pi_{0}|$.

To better illustrate the complementarity of the coloring-based and partition-based upper bounds (i.e., GCB and PUB), we provide two examples in Figure 2, where the growing 2-plex $S$ contains only one vertex $v_{0}$ and its corresponding candidate set $C=\{v_{1},v_{2},v_{3},v_{4},v_{5}\}$.

In Figure 2(a), the GCB is tighter than the PUB. The vertices in $C$ are all adjacent to $v_{0}$, which means the vertices in $C$ are all in $\pi_{0}$. Thus, the PUB is $|S|+|\pi_{0}|=6$. While by coloring the vertices in $C$, it can be partitioned into 2 independent sets $I_{1}=\{v_{1},v_{2},v_{3},v_{5}\}$ and $I_{2}=\{v_{4}\}$, and the GCB is $|S|+\sum_{i=1}^{2}{\min\{|I_{i}|,2\}}=4$. In contrast, the PUB is tighter than the GCB in Figure 2(b), where $C$ can be partitioned into 3 independent sets $I_{1}=\{v_{1},v_{5}\}$, $I_{2}=\{v_{2},v_{3}\}$, and $I_{3}=\{v_{4}\}$. Thus, the GCB is $|S|+\sum_{i=1}^{3}{\min\{|I_{i}|,2\}}=6$. While vertices in $C$ except $v_{1}$ are non-adjacent to $v_{0}$, $\pi_{0}=\{v_{1}\}$, thus the PUB is $|S|+|\pi_{0}|+\delta_{2}^{-}(S,v_{0})=3$.

Both RelaxGCB and DisePUB extract a subset from $C$ and accumulate the upper bound of $\omega_{k}(G,S)$. The $dise$ metric in DisePUB can also be used for the vertex set returned by TryColor(). RelaxPUB combines RelaxGCB and DisePUB by using them to select a promising extraction in each step.

We propose an algorithm called SelectUB for calculating the RelaxPUB of $\omega_{k}(G,S)$, which is presented in Algorithm 4. The algorithm calls TryColor() and SelectPartition() in each step and figures out whose returned vertex set is better according to the $dise$ metric. Ties are broken by preferring larger extraction. Once a better extraction is selected, The algorithm updates the candidate set $C$ and accumulates the upper bound of $\omega_{k}(G,S)$.

The time complexities of functions TryColor() and SelectPartition() are $O(|C|\times T)$ and $O(|C|\times|S|)$ Jiang et al. (2023), respectively, where $O(T)$ is much smaller than $O(|V|)$ as referred to Section 3.4. The time complexity of the SelectUB algorithm is $O(|C|^{2}\times(|S|+T))$.

All the algorithms were implemented in C++ and run on a server using an AMD EPYC 7H12 CPU, running Ubuntu 18.04 Linux operation system. We test the algorithms on two public benchmarks that are widely used in the literature of the baselines, the 2nd DIMACS benchmark⁵⁵5http://archive.dimacs.rutgers.edu/pub/challenge/graph/
benchmarks/clique/ that contains 80 (almost dense) graphs with up to 4,000 vertices and densities ranging from 0.03 to 0.99, and the Real-world benchmark⁶⁶6http://lcs.ios.ac.cn/%7Ecaisw/Resource/realworld%20
graphs.tar.gz that contains 139 real-world sparse graphs from the Network Data Repository Rossi and Ahmed (2015).

We choose the two sets of benchmarks because the 2nd DIMACS benchmark is also widely used to evaluate MCP, one of the most closely related problems to MKP, and the Real-world benchmark is widely used for analyzing various complex networks, one of the most important application areas of MKP. Moreover, the structures of the two benchmarks are distinct, helping evaluate the robustness of the algorithms.

For each graph, we generate 8 MKP instances with $k\in\{2,3,4,5,6,7,10,15\}$, and set the cut-off time to 1,800 seconds per instance, following the settings of the baselines.

The comparison results between the algorithms with our RelaxGCB and RelaxPUB bounds and the baselines in dense 2nd DIMACS and sparse Real-world benchmarks are summarized in Figures 3 and 4, respectively. The results are expressed by the number of MKP instances solved by each algorithm within the cut-off time for different $k$ values. Note that Maplex only contains the GCB, and the other three baselines only contain the PUB. 1) From (a) of the two figures, one can observe that our RelaxGCB significantly outperforms GCB. 2) From (b) to (d) of the two figures, one can observe that RelaxGCB is complementary to PUB. 3) From all the figures, one can observe that our RelaxPUB makes full use of the complementarity of RelaxGCB and PUB, and significantly improves all the baselines in solving both dense and massive sparse graphs over diverse $k$ values, indicating its dominant performance over the state-of-the-art baselines, excellent generalization over different graphs, and strong robustness over diverse $k$ values.

With the increment of the $k$ values, the number of solved instances usually decays, because the number of vertices removed by graph reduction decreases accordingly, making the follow-up BnB calculation more complicated with a larger number of required branches. However, we notice that the number of solved instances increases for larger $k$ values (e.g., 10 and 15) on DIMACS2. This is because a $k$-plex with larger $k$-values can contain more vertices, and the DIMACS2 graphs are generally small and dense, making the most vertices in a graph contained.

Following the convention of the baselines, we also present detailed results of the baselines and their improvements with RelaxPUB in solving 30 representative 2nd DIAMCS and Real-world instances with $k=2,3,6,10,15$ in Table 1. We report their running times in seconds (column Time), the sizes of their entire search trees in $10^{5}$ (column Tree) to solve the instances, and the percentage of the number of times RelaxGCB is selected and outperforms the DisePUB in RelaxPUB (column Percent). Better results are highlighted in bold, and symbol ‘-’ means the algorithm cannot solve the instance within the cut-off time.

The results show that for each pair of tested algorithms, our new upper bounds can help the baseline algorithm prune significantly more branches, reducing its search tree sizes by several orders of magnitude for instances that both can solve within the cut-off time. There are also many instances that the baseline algorithms cannot solve within the cut-off time, while the algorithms with our upper bounds can solve with few branches and much less calculation time. Moreover, we can observe that RelaxGCB contributes a lot in solving these instances, indicating again the complementarity of RelaxGCB and DisePUB.

In this subsection, we perform ablation studies to evaluate the effectiveness of the proposed TISUB and the two rules (see Lemmas 1, 2, and 3) in our proposed upper bounds. For the kPlexS, DiseMKP, and KPLEX baselines having the PUB, we generate a “Norules” variant, which uses our RelaxPUB without Rules 1 and 2, and a “GCBPUB” variant, which uses our RelaxPUB and replaces its RelaxGCB with the GCB in Maplex. Moreover, since the kPlexS and KPLEX algorithms use the previous PUB proposed in Jiang et al. (2021), we apply the newest DisePUB to them and obtain two variants: Dise-kPlexS and Dise-KPLEX. For the Maplex baseline that is only based on GCB, we generate a “Norules” variant, which uses our RelaxGCB without Rules 1 and 2.

We perform four groups of ablation studies based on each baseline over all the 1,752 instances, as summarized in Figure 5. The results are expressed by the variation in the number of solved instances for each algorithm over the running time (in seconds). The results show that the “GCBPUB” variants are better than the baselines, indicating that combining coloring-based and partition-based upper bounds by the mechanism in RelaxPUB can make use of their complementarity. The “Norules” variants are better than the “GCBPUB” variants, indicating that TISUB is a significant improvement over GCB. The new algorithms with RelaxPUB are better than the “Norules” variants, indicating that our proposed two rules can further improve TISUB. Moreover, DisePUB can hardly improve kPlexS and KPLEX, indicating that the improvements of the RelaxPUB series over the baselines originate from RelaxGCB rather than using the newest DisePUB.