A Refined Upper Bound and Inprocessing for the Maximum K-plex Problem

1 Introduction

Let G = (V, E) be an undirected graph, where V is the set of vertices and E is the set of edges. Two vertices are neighbors if they are adjacent in G. Given an integer k, a subgraph G′ of G is a k-plex if every vertex in G′ has at most k - 1 nonneighbors. The decision of existence of a k-plex of a given size in graphs is NP-complete [Balasundaram et al., 2011].

Given a graph G and an integer k, the Maximum k-plex Problem (MKP) consists in finding a k-plex with the largest number of vertices. MKP is a generalization of the Maximum Clique Problem (MCP), the latter is a special case of MKP (k is 1) and is a well-known NP-hard combinatorial optimization problem [Garey and Johnson, 1979].

The k-plex model finds many practical applications, such as social network analysis [Seidman and Foster, 1978] and scalable community detection[Conte et al., 2018]. Due to the flexibility of the k-plex model, it is more suitable for the analysis of the graphs encoding from real-world applications, where noise and defective data are inevitable and the classic clique model is too rigorous to be practical.

∗Corresponding author

Since MKP is relevant to practical applications, a lot of work has devoted to seeking for efficient algorithms, including exact and heuristic algorithms, for MKP in recent years [Gujjula et al., 2014; Zhou and Hao, 2017; Xiao et al., 2017; Miao and Balasundaram, 2017; Gao et al., 2018; Zhou et al., 2020; Zhou et al., 2021; Jiang et al., 2021].

In the aspect of heuristics, Krishna et al. [2014] proposed a greedy randomized adaptive search and tabu search meta-heuristic for MKP. Zhou and Hao [2017] proposed a frequency-driven multi-neighborhood tabu search for MKP on large networks. Chen et al. [2020] implemented an efficient local search which is based on a double-attributes incremental neighborhood updating and dynamic configuration checking strategies. Pullan presented a local search for MKP [Pullan, 2021]. These heuristics focus on obtaining a suboptimal solution within a reasonable solving time.

Exact search algorithms seek for the optimal solutions by exploring the search space systematically. Balasundaram et al. [2011] designed an integer programming formulation and a branch-and-cut algorithm for MKP. McClosky and Hicks [2012] presented a BnB algorithm with a co-k-plexcoloring upper bound. Xiao et al. [2017] proposed an exact algorithm with time complexity in O(cnnO(1) ) for a constant c < 2 and each k ≥ 3. Gao et al. [2018] proposed several reduction rules and a BnB algorithm with a dynamic vertex selection mechanism. Zhou et al. [2021] proposed a BnB algorithm with a second-order reduction and a graph coloring upper bound to reduce the search space. Jiang et al. [2021] gave a partition-based upper bound and designed an efficient BnB algorithm for MKP. Moreover, algorithms for enumerating all maximal k-plexes were studied in [Conte et al., 2017; Zhou et al., 2020] .

We note that exact algorithms for MKP, especially BnB algorithms, have achieved a significant advance in recent years and the advance mainly comes from improvements in two aspects: effective reduction rules and upper bounds [Xiao et al., 2017; Gao et al., 2018; Zhou et al., 2021; Jiang et al., 2021]. The reduction rules reduce graphs by exploiting the structural features of graphs and the upper bounds speed up the search of BnB algorithms by pruning the search space efficiently at every search tree node.

In this paper, we propose a refined upper bound and an efficient inprocessing strategy for MKP. We analyze the defects of existing methods for the partition-based upper bound and then propose a novel notion and a sophisticated algorithm to improve the upper bound. We present an inprocessing strategy that employs a graph reduction procedure to reduce graphs incrementally. Based on the two essential components, we implement a new BnB algorithm for MKP. Extensive experiments were performed to evaluate the performance of the algorithm and the effectiveness of the two components. Results show that both the refined upper bound and the inprocessing strategy are very efficient in the reduction of search space. The new algorithm outperforms the state-of-the-art exact algorithms significantly on the tested benchmarks .

The paper is organized as follows: Section 2 gives the notations and graph definitions used in this paper. Section 3 reviews previous upper bounds and presents a refined upper bound for MKP. Section 4 describes the inprocessing. Section 5 presents a new BnB algorithm. Section 6 reports on the empirical results. Section 7 concludes the paper.

2 Preliminaries

Let G = (V, E) be an undirected graph with n vertices and m edges. Two vertices u and v are adjacent or neighbors, if there is an edge between u and v, i.e., (u, v) ∈ E. The set of neighbors of a vertex v is denoted as N(v). The degree of vertex v in G, denoted by deg(v), is the number of neighbors of v and the maximum degree in G is denoted as deg(G). The density of G is computed as 2m/(n(n - 1)).

If V ′ is a subset of V , the induced subgraph G[V ′ ] by V ′ is defined as G[V ′ ] = (V ′ , E′ ), where E′ = {(u, v)|u, v ∈ V ′ and (u, v) ∈ E}. Given a positive integer k, G[V ′ ] is a k-plex if the degree of v in the induced subgraph is greater than or equal to |V ′ | - k for each v ∈ V ′ . The size of a k-plex is the number of vertices in it. The size of the maximum k-plex in G is denoted by κ(G) in this paper.

An Independent Set (IS) of G is a subset of V in which every two vertices are nonadjacent in G. Graph coloring is to assign a color to every vertex such that every two adjacent vertices receive different colors. In a feasible coloring, the vertices that receive the same color form an IS.

3 ARefined Upper Bound

Bounding strategies are crucial to the performance of BnB algorithms. In this section, we review previous upper bounds for MKP and present a refined upper bound.

Given a graph G = (V,E) and an integer k, let S = {v1, v2, . . . , vq} be a partial solution for MKP in G and let C be the set of candidate vertices that could join in S. In BnB algorithms for MKP, a partial solution S corresponds to a node in the search tree. In this paper, we mainly discuss the upper bound of the maximum k-plex of containing the current partial solution S. Existing BnB algorithms for MKP usually estimate the upper bound by partitioning the candidate set C of the current search tree node into subsets.

The graph coloring upper bound (COL for short), presented in [Zhou et al., 2021], partitions the vertices of C into ISs I1, I2, . . . , Ip and then computes the upper bound as |S|+ ∑pi=1 min{k, |Ii|}, because each IS Ii can contribute at most k vertices to a k-plex. COL derives an upper bound by considering the solution constraints within an IS.

The partition-based upper bound (PUB for short), proposed in [Jiang et al., 2021], partitions the vertices of C into subsets Π = {π0, π1, . . . , πq} w.r.t. the current partial solution S = {v1, v2, . . . , vq}, where each πi (i ≥ 1) is a subset of non-neighbors of vertex vi and π0 is the set of vertices in C that are adjacent to every vertex vi ∈ S. Moreover, PUB maintains an array ∆ = {δ1, δ2, . . . , δq} for S, where each δi is the number of vertices in S that are nonadjacent to vi. PUB is computed as |S|+|π0|+ ∑qi=1 min{k-1-δi, |πi|}, because each πi ∈ Π (i ≥ 1) can contribute at most k-1-δi vertices to S. PUB derives an upper bound by considering the solution constraints of the current partial solution.

The experimental results show that PUB is more effective for pruning the search space than COL and other upper bounds [Jiang et al., 2021]. However, as the authors point out, the quality of PUB is relevant to the partition Π of C. Since a vertex in C could be a non-neighbor of many vertices in S. The total number of eligible partitions of C could be a power of |C|. Different partitions of C derive different computational results of PUB. We use Figure 1, which is originally presented in [Jiang et al., 2021], to illustrate the difference.

Example 1. Let k be 3 and the partial solution S of G in Figure 1 be {v1, v2, v3}. Then, the ∆ array of S is {0, 1, 1} and the candidate set C is {v4, v5, v6, v7, v8}. The following two partitions Π1 and Π2 are eligible. Π1 is {π0 = {v4}, π1 = ∅, π2 = {v7, v8}, π3 = {v5, v6}} and its PUB is computed as: |S|+|π0|+∑3i=1 min{k-1-δi, |πi|} = 3+1+0+1+1 = 6. Π2 is {π0 = {v4}, π1 = {v6, v8}, π2 = {v7}, π3 = {v5}} and its PUB is computed as: 3 + 1 + 2 + 1 + 1 = 8.

Note that the PUB bound of Π2 is 2 bigger than that of Π1 in Example 1. In fact, using the ordering v1 > v2 > v3, the sequential construction algorithm proposed in [Jiang et al., 2021] produces Π2 rather than Π1. We first analyze the reason why Π1 computes a better upper bound than Π2 does and then present a new algorithm that can derive a tighter upper bound than the one presented in [Jiang et al., 2021].

Note that if a set πi already contains k - 1 - δi vertices, inserting more vertices into it doesn't increase the value of min{k - 1 - δi, πi}, but could decrease the value of other πj because the number of vertices in πj could be reduced. In the partition Π2 in Example 1, π2 and π3 must contain one vertex (v7 must be in π2 and v5 must be in π3) and they have the maximum value of min{k - 1 - δi, πi}. Therefore, the insertion of v8 into π2 and v6 into π3 does not increase the computational results of PUB for π2 and π3, but can decrease the computational result of PUB for π1 by 2, because π1 becomes an empty set after v8 and v6 are moved into π2 and π3, respectively. Obviously, to obtain a better upper bound, the vertex v8 and v6 should be inserted into π2 and π3 instead of π1. However, we don't have any prior knowledge to determine which π a vertex should be inserted into.

Inspired by the above observation, we propose a refined upper bound, which can improve the quality of PUB. Recall that the PUB bound of each πi is computed as min{k - 1 - δi, |πi|}. We call it the cost for the construction of πi, denoted by cost(πi), which is formulated as follows.

To obtain a tighter upper bound, we take the construction of the partition Π as a process of distributing every vertex u of C into a proper πi with an objective to minimize the total cost. We propose a notion called distribution efficiency, denoted by dise(πi), for each πi ∈ Π (i > 0), which is the ratio of the cardinality of πi to its cost(πi) and is formulated as follows.

Especially, if πi is empty, dise(πi) is defined as 0. We evaluate every π ∈ Π w.r.t. its distribution efficiency, i.e., we say πi is better than πj if dise(πi) is greater than dise(πj).

Now we present a new algorithm to derive a better partition of Π, which is called DisePUB and is depicted in Algorithm 1. DisePUB constructs Π with two steps. At the first step, it constructs an overlapped partition Π′ of C, i.e., a vertex u ∈ C is distributed into every πi ∈ Π′ if u is nonadjacent to vi of S. The initial upper bound ub is computed as |S| + |π0|. At the second step, it picks a πi in Π′ with the largest distribution efficiency dise(πi) iteratively. Each time a πi is picked, its cost(πi) is accumulated to ub, πi is removed from Π′ and is inserted into Π and all of the vertices in πi are removed from the remaining π ∈ Π′ . The process repeats till Π′ becomes an empty set, i.e., every π ∈ Π has been determined. The accumulated ub is an upper bound of the maximum k-plex of containing S.

We illustrate how DisePUB constructs the partition and computes the upper bound with Example 2.

Example 2. Let k and S be the same as in Example 1. At the first step, DisePUB constructs the Π′ as {π1 = {v6, v8}, π2 = {v7, v8}, π3 = {v5, v6}}, π0 = {v4} and the initial upper bound ub is 3+1 = 4. Then, at the second step, DisePUB picks π one by one. At first, dise(π1), dise(π2) and dise(π3) are computed as 1, 2 and 2, respectively. Without loss of generality, suppose DisePUB picks π2 at first and then v7 and v8 are removed from π1 and π3, ub is increased by cost(π2) = 1. Next, DisePUB picks π3 because dise(π3) is 2 and dise(π1) is 1 after removing vertices of π2 and increases ub by cost(π3) = 1. Finally, DisePUB picks π1 which is an empty set after removing vertices of π3 from π1. DisePUB obtains a partition that is the same as Π1 in Example 1, the upper bound is computed as 6. Note that the same partition can be obtained if π3 is picked at first.

DisePUB is quite different from the algorithm described in [Jiang et al., 2021], wherein the algorithm generates every Algorithm 1 DisePUB(S, C, k), a partition algorithm based on distribution efficiency.

Input: The partial solution S = {v1, v2, . . . , vq}, the candidate set C, the k value

Output: An upper bound of maximum k-plex containing S

• 1: Let Π = ∅, Π′ = ∅, S = {v1, v2, . . . , vq};
• 2: Let π0 = C ∩N(v1) ∩ · · · ∩N(vq), ub = |S| + |π0|;
• 3: Π←Π∪ {π0};
• 4: for i=1 to q do
• 5: create a πi = C \N(vi);
• 6: Π′ = Π′ ∪ {πi};
• 7: end for
• 8: repeat
• 9: select a πi ∈ Π′ with the largest dise(πi);
• 10: Π←Π∪ {πi}, Π′ ←Π′ \ {πi}, ub ← ub+cost(πi);
• 11: remove all vertices in πi from each π ∈ Π′ ;
• 12: until Π′ = ∅
• 13: return ub;

πi sequentially and the computed upper bound depends on the ordering of vertices of S. DisePUB generates the partition with two steps that is guided by the novel notion of distribution efficiency. The computed upper bound of DisePUB is not related to the ordering of vertices being inserted into Π.

In Algorithm 1, lines 2-7 implement the first step, constructing an overlapped partition Π′ , which has a time complexity of O(|S| × |C|). Lines 8-12 implement the second step, picking a πi with the largest dise(πi) iteratively. Each time a πi is determined, the dise(π) of the remaining π ∈ Π′ needs to be recomputed. The time complexity of the second step is O(|S|2 ×|C|). Therefore, the total time complexity of Algorithm 1 is O(|S|2 × |C|).

In section 5, we will explain how to adapt Algorithm 1 to reduce the number of branches in a BnB algorithm.

4 Inprocessing for MKP

Previous work has proven that graph reduction is very effective for solving MKP in real-world graphs. In this section, we present an efficient reduction procedure, which is based on a lower bound of κ(G) and can be used as an inprocessing strategy in a BnB algorithm to reduce graphs incrementally.

BnB algorithms usually begin their search with an initial solution S0. We use lb = |S0| to denote the initial lower bound of κ(G). Existing graph reduction rules for MKP are mainly based on the following property.

Property 1. Given a graph G and a vertex v, the maximum k-plex of containing v is smaller than or equal to deg(v)+k.

According to Property 1, if we are searching for a k-plex S of size greater than lb, then those vertices with degree smaller than or equal to lb-k are redundant and can be removed from G iteratively in the preprocessing stage. [Gao et al., 2018; Zhou et al., 2021; Jiang et al., 2021].

According to the number of common neighbors of two vertices u and v, enhanced reduction rules are proposed in [Zhou et al., 2021; Jiang et al., 2021], which are based on the following property.

Algorithm 2 Reduce(G, k, lb), a reduction algorithm for MKP.

Input: A graph G, k value and the lower bound lb of κ(G). Output: A reduced graph G′

• 1: repeat
• 2: remove every vertex v if deg(v) ≤ lb - k;
• 3: remove every edge (u, v) if cone(u, v) ≤ lb - 2k;
• 4: until there is no vertex and edge be removed fromG
• 5: return the reduced graph G′ ;

Property 2. Let cone(u, v) be the number of common neighbors of vertex u and v in G. The maximum k-plex of containing u and v is smaller than or equal to cone(u, v) + 2k - γ, where γ is 0 if (u, v) ∈ E; Otherwise, γ is 2.

Zhou et al. [2021] use Property 2 to remove an edge (u, v) if cone(u, v) ≤ lb - 2k in the preprocessing. Jiang et al. [2021] use the property to reduce graphs in the preprocessing and to reduce the number of candidate vertices when the search tree level is less than 3.

We note that the efficiency of reduction rules based on Property 1 and 2 is relevant to the quality of the lower bound lb. The higher the lower bound lb is, the more vertices could be removed from G. However, because of the NP-hardness of MKP, there could be a big gap between the initial lower bound lb and κ(G), making the application of reduction rules inadequate if they are just applied in the preprocessing stage.

Based on the above observation, we propose a new approach to perform graph reduction, i.e., performing reduction as an inprocessing. The graph reduction procedure is depicted in Algorithm 2, which performs reduction rules based on Property 1 and 2 iteratively w.r.t. a given lower bound lb of κ(G). The procedure is designed to be integrated into a BnB algorithm as an inprocessing, which is triggered once the lower bound lb is updated during the search.

The time complexity of removing a vertex (an edge) is O(deg(G)) and the computation of common neighbors for edges is O(|E|1.5 )[Latapy, 2008]. Therefore, the total time complexity of inprocessing is O(|E|1.5+(|V |+|E|) · deg(G)).

5 ANew BnB Algorithm for MKP

We present a new BnB algorithm for MKP, called DiseMKP, which is depicted in Algorithm 3. The algorithm first generates an initial solution S0 and then calls Algorithm 2 to reduce the input graph G to G′ . The initial solution S0 is generated with the heuristic presented in [Jiang et al., 2021]. Let v1 < v2 < · · · < vn be the degeneracy ordering. If vi is the smallest vertex with degree of greater than or equal to n - i + 1 - k, then G[{vi, vi+1, . . . , vn}] is a k-plex. After reducing the graph, DiseMKP calls a BnB search procedure to search for an optimal solution in the reduced graph G′ .

The BnB search procedure is described in Algorithm 4, which implements the BnB search approach proposed in [Li et al., 2017]. Let S be the partial solution and C be the set of candidate vertices. Instead of exploring the whole search space formed by the set C, Algorithm 4 calls a function, called PartitionDise, to identify a minimal set B of branching

Algorithm 3 DiseMKP(G, k), a BnB algorithm for MKP

Input: A graph G = (V, E) and an integer k

Output: a maximum k-plex S∗ in G.

• 1: generate an initial solution S0;
• 2: G′ = (V ′ , E′ ) ← Reduce(G, k, |S0|);
• 3: return BnBSearchMKP(G′ , ∅, V ′ , S0, k);

vertices and only branches on vertices in B w.r.t. the degeneracy ordering of vertices of B. Each time the search procedure finds a better solution S∗ , it calls the reduction procedure (Algorithm 2) to perform graph reduction, which implements an inprocessing. After the reduction, Algorithm 4 backtracks to the root node of the search tree, clears the removed vertices from B and C and then the search proceeds from the first unbranched branching vertex.

The function PartitionDise is described in Algorithm 5, which partitions the candidate set C into B and P subject to κ(G[S ∪ P]) ≤ |S∗ |. At the beginning, B is set to C. The goal of PartitionDise is to minimize B. Let β = |S∗ | - |S|. We call β the total budget for the minimization of B. Algorithm 5 first constructs an overlapped partition Π and then select a π∗ with the highest distribution efficiency dise(π∗ ) and cost(π∗ ) ≤ β. Each time a π∗ is determined, the vertices in π∗ are removed from B and from the remaining π in Π, and the budget is reduced by cost(π∗ ). The process repeats till the budget β is depleted or no π can be selected. If β > 0 and B is not empty, Algorithm 5 removes min{β, |B|} more vertices from B. Obviously, those vertices that are removed from B form the set P and κ(G[S ∪ P]) ≤ |S∗ | holds. Finally, Algorithm 5 returns the reduced B as the branching set.

The time complexity of Algorithm 5 is the same with the time complexity of Algorithm 1. Experimental results of the new algorithm, the effects of the refined upper bound and the inprocessing will be given in the next section.

Algorithm 4 BnBSearchMKP(G, S, C, S∗ , k)

Input: A graph G=(V ,E), a partial solution S, the candidate

set C and the incumbent solution S∗ and the k value.

Output: the best solution S∗ in G.

• 1: remove every v ∈ C, if |S \N(v)| ≥ k;
• 2: if C is empty then return S;
• 3: B ←PartitionDise(C, k, S, S∗ );
• 4: if B is empty then return S∗ ;
• 5: Let u1 < u2 < · · · < u|B| be the degeneracy ordering of vertices of B and C ′ = C \ B.
• 6: for i = |B| to 1 do
• 7: S′ ←BnBSearchMKP(G, S ∪ {ui}, C ′ , S∗ , k);
• 8: if |S′ | > |S∗ | then
• 9: S∗ ← S′ ;
• 10: G←Reduce(G, k, |S∗ |);
• 11: backtrack to the root node and proceed the search from the first unbranched branching vertex;
• 12: end if
• 13: C ′ ←C ′ ∪ {ui};
• 14: end for
• 15: return S∗ ;

Algorithm 5 PartitionDise(C, k, S, S∗ ), generates the branching set B with the upper bound DisePUB

Input: The candidate set C, the k value, the partial solution S and the best solution S∗ found so far

Output: A branching set B

1: Let S = {v1, v2, . . . , vq}, B = C, Π = ∅; 2: for i = 1 to q do 3: create a πi = C \N(vi); 4: Π = Π∪ {πi}; 5: end for 6: Let β = |S∗ | - |S|; 7: repeat 8: π∗ ← ∅, max dise ← 0; 9: for each non-empty π ∈ Π do 10: if cost(π) <= β and dise(π) > max dise then 11: π∗ ← π, max dise ← dise(π); 12: end if 13: end for 14: if π∗ ̸= ∅ then 15: B ←B \ π∗ , Π←Π \ {π∗ }, β ← β - cost(π∗ ); 16: π ← π \ π∗ for each π ∈ Π; 17: end if 18: until π∗ = ∅ or β = 0 19: if β > 0 and B ̸= ∅ then 20: remove min{β, |B|} vertices from B; 21: end if 22: return B;

6 Experimental Results

We empirically evaluated the new algorithm DiseMKP and its two essential components: the refined upper bound and the inprocessing strategy. DiseMKP was compared with the following three state-of-the-art BnB algorithms:

• BnBK 1 : It is the BnB algorithm proposed in [Gao et al., 2018]. BnBK employs several sophisticated reduction rules and a dynamic vertex selection branching heuristic.
• Maplex 2 : It is the BnB algorithm proposed in [Zhou et al., 2021]. Maplex implements a second-order reduction in the preprocessing and employs the graph coloring upper bound to reduce the search space.
• KpLeX 3 : It is the BnB algorithm proposed in [Jiang et al., 2021]. KpLeX integrates the graph reduction rules in the preprocessing and the partitioning-based upper bound PUB to reduce the number of branches.

DiseMKP 4 and the three compared algorithms were implemented in C++ and compiled using GNU g++ -O3. Experiments were performed on AMD EPYC CPUs 7702 @2.0GHz under Linux with 128GB of memory. We tested a total of 675 graphs from three different datasets to evaluate DiseMKP and the compared algorithms.

1 https://github.com/JimNenu/codekplex

2 https://github.com/ini111/Maplex

3 https://github.com/huajiang-ynu/kplex

4 Published at https://github.com/huajiang-ynu/ijcai23-kpx

• DIMACS graphs 5 : The dataset contains 80 graphs with the number of vertices up to 4000 and densities ranging from 0.03 to 0.99. The dataset has been widely used to evaluate algorithms for MCP and MKP.
• DIMACS10 graphs 6 : The dataset contains 84 graphs with the number of vertices up to 2 × 107 . The dataset has been widely used to evaluate graph algorithms like MCP and MKP.
• Real-world graphs from Network Repository 7 : The dataset contains 511 representative real-world graphs which we select from Network Data Repository [Rossi and Ahmed, 2015], including: biological networks (36), dynamic networks (88), interaction networks (29), labeled networks (104), recommendation networks (12), road networks (15), scientific computing (11), social networks (72), facebook (114) and web networks (30).

We use four different k values: 2, 4, 6 and 8 to evaluate the algorithms. In general, the difficulty of solving MKP increases dramatically as the k value increases.

6.1 Performance Profiles

The first experiment we conducted is to evaluate the total performance of DiseMKP and the three compared algorithms. Algorithms were tested over the 675 instances with a cutoff time of 1800s for each instance. The total numbers of instances solved by each algorithm are reported in Table 1.

From Table 1, we can see that our new algorithm DiseMKP can solve more instances than the compared algorithms for every tested k value. The performance superiority of DiseMKP over the three compared algorithms increases steadily as the increase of k value. Especially, DiseMKP can solve 499 instances at k = 8, which is 11.9%, 38.6% and 19% more than the number of instances solved by KpLeX, Maplex and BnBK, respectively.

We plotted the cumulative numbers of solved instances of the four algorithms for each k value. The results are detailed in Figure 2. From Figure 2, we can see that the biggest gaps of cumulative numbers of solved instances between DiseMKP and the compared algorithms almost always occur within the first 200s for each tested k, showing that DiseMKP is steadily faster than the compared algorithms. Moreover, we can see that Maplex and BnBK have a comparable performance with KpLeX at k = 2, but their performance declines dramatically when k increases to 4. KpLeX also shows an obvious decline in performance when k increases to 8. Whereas, the performance of DiseMKP declines tardily as k increases. DiseMKP is the most robust among the four tested algorithms.

5 http://archive.dimacs.rutgers.edu/pub/challenge/graph/

6 https://www.cc.gatech.edu/dimacs10/downloads.shtml

7 http://networkrepository.com/networks.php

In general, DiseMKP outperforms the three state-of-the-art algorithms KpLeX, BnBK and Maplex on the tested datasets significantly.

6.2 Effect of the NewUpper Bound

To evaluate the effect of the new upper bound DisePUB for pruning the search space, we implemented three variants of DiseMKP, in which the inprocessing procedure (line 10 and 11 in Algorithm 4) is disabled and the Partition function is implemented with the three different upper bounds.

• BnBcol: It generates the branching set B with graph coloring bound. Let lb = |S∗ | - |S|. BnBcol constructs IS I1, I2, . . . , Ip one by one and computes an upper bound ub as ∑pi=1 min{k, |Ii|} subject to ub ≤ lb. BnBcol takes the candidate vertices that are not inserted into the constructed ISs as the vertices of the set B.
• BnBpub: It generates the branching set B with the partition function presented in [Jiang et al., 2021], i.e., constructing each πi of Π one by one w.r.t. the vertex ordering in the partial solution S subject to the computed upper bound of Π is not greater than lb. BnBpub takes vertices that are not in Π as the vertices of the set B.
• BnBdise: It is DiseMKP but the inprocessing procedure is disabled (line 10 and 11 in Algorithm 4 are removed).

BnBdise generates the branching set B with our new upper bound DisePUB that is depicted in Algorithm 5.

We conducted an experiment to compare BnBcol, BnBpub and BnBdise using 40 representative instances with a cutoff time of 3600s and k = 4 . We report the search tree size in 105 and the running time in seconds of each instance of the three algorithms. Table 2 shows the results of the comparison.

In total, BnBdise solves all of the 40 instances, BnBpub solves 33 instances and BnBcol solves only 7 instances within the cutoff time. It is easy to see that the search tree sizes of BnBdise are significantly smaller than that of BnBcol and BnBpub, especially on hard instances. For example, the search tree sizes of BnBdise for hamming6-2 and socfbUGA50 are 305.9 and 76.4, which are only 3.1% and 2.1% of the search tree sizes of BnBpub for the two instances, respectively. Consequently, BnBdise are almost always several times faster than BnBpub on hard instances in Table 2.

The comparison shows that our new upper bound DisePUB is more efficient in reducing search space than the COL and PUB upper bounds for BnB algorithms for MKP.

6.3 Effect of the Inprocessing Procedure

To investigate the effect of the inprocessing procedure in DiseMKP, we compared DiseMKP with a variant DiseMKPNOIP, which is DiseMKP but the inprocessing procedure (line 10 and 11 in Algorithm 4) is disabled. We tested DiseMKP and DiseMKP-NOIP over the 675 instances with k = 2 and 4 using a cutoff time of 1800s.

Figure 3 shows the cumulative numbers of instances solved by DiseMKP and DiseMKP-NOIP. The results for k = 2 and 4 are plotted in dashed and solid lines, respectively. DiseMKP solves 580 and 545 instances and DiseMKP-NOIP solves 558 and 516 instances for k = 2 and 4, respectively. It is easy to see that without the inprocessing procedure, the performance of DiseMKP declines significantly.

To illustrate the effectiveness of the inprocessing, we selected two representative instances, sc-pkustk13 and recepinions, to present their graph reduction processes in inprocessing as the increase of the lower bound lb. With k = 4, DiseMKP solves sc-pkustk13 and rec-epinions in 26.9s and 418s, respectively. But DiseMKP-NOIP solves sc-pkustk13 using 402s and cannot solve rec-epinions within 1800s.

The reduction processes are presented in Table 3. The first row of each instance shows the original numbers of vertices and edges and the second row shows the initial lower bound and the initial reduction result of the graph. The last row is the optimal solution. From Table 3, we can see that the two graphs are reduced dramatically as the increase of the lower bound lb, which can speed up the search of DiseMKP in turn.

In general, the inprocessing procedure can exploit graph reduction rules more efficiently and is essential to the performance of the new algorithm DiseMKP.

7 Conclusions

We proposed two efficient strategies for BnB algorithms for MKP, a refined upper bound and an inprocessing procedure. The upper bound is based on a novel notion of distribution efficiency and can compute a tighter bound than existing upper bounds for MKP. The inprocessing procedure implements incremental graph reduction, which can help BnB algorithms to reduce more search space. Based on the two components, we implemented a new BnB algorithm for MKP. Extensive experiments show that the two components are very efficient in the reduction of the search space in BnB algorithms. The new algorithm outperforms the state-of-the-art exact algorithms significantly on the tested benchmarks.

Acknowledgments

This work is funded by the National Natural Science Foundation of China (Grant NO. 62162066, 62162067 and 62162064), and in part supported by the project of Research and Application of Object Detection Based on Artificial Intelligence, by the project of Research on Data Driven Intelligent Logistics System Construction and Key Technologies (Grant NO. 202302AD080006), Science and Technology Department of Yunnan Province. The experiments were performed on Hefei advanced computing center.