arXiv CSopen access

Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound

arXiv:2605.16948v1 [cs.DB] 16 May 2026

Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound Kewu Yang

Kaiqiang Yu∗

Harbin Institute of Technology, Shenzhen [email protected]

State Key Laboratory of Novel Software Technology, Nanjing University [email protected]

Shengxin Liu∗

Zhaoquan Gu∗

Harbin Institute of Technology, Shenzhen [email protected]

Harbin Institute of Technology, Shenzhen PengCheng Laboratory [email protected]

ABSTRACT The 𝑘-defective clique model relaxes the strict completeness constraint of the traditional clique by allowing up to 𝑘 missing edges, providing a robust formulation for detecting cohesive structures in noisy graphs. Consequently, the maximum 𝑘-defective clique problem has attracted significant attention. State-of-the-art exact algorithms predominantly adopt the branch-and-bound framework, which recursively partitions the current problem instance (or branch) into two sub-problems via a branching procedure, until each sub-problem becomes trivially solvable. However, this strategy often leads to excessive branching by overlooking intermediate subproblems that are non-trivial yet efficiently solvable. While recent studies have attempted to refine branching procedures, they fail to address this structural redundancy. To address this, we propose BBRes, a framework that incorporates a novel early termination strategy into the recursive branching process. By employing a specialized polynomial-time solver to identify and resolve tractable sub-instances, BBRes effectively avoids redundant branching steps. Additionally, we design a tailored branching strategy that synergizes with this termination mechanism. As a result, BBRes achieves an improved theoretical worst-case time complexity. To enhance practical performance, we propose a tighter upper bound based on a novel double graph coloring method integrated with max-flow techniques, which is orthogonal to the branching framework. Extensive experiments show that BBRes achieves at least 2X speedup over state-of-the-art methods on a substantial fraction of the datasets. PVLDB Reference Format: Kewu Yang, Kaiqiang Yu, Shengxin Liu, and Zhaoquan Gu. Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: ∗ Corresponding authors.

This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX

The source code, data, and/or other artifacts have been made available at https://github.com/Thaumaturge2020/BBRes/.

1

INTRODUCTION

Graphs are widely used to model relationships between entities in various applications, such as social media, biological science, and e-commerce. Extracting cohesive/dense subgraphs from large realworld graphs is a fundamental problem in graph analytics. Such cohesive subgraphs often carry interesting information, which can facilitate various tasks across different domains. Examples include finding communities in social networks [7, 23], detecting anomalies in financial networks or social media [2, 8, 34, 53], and discovering biologically relevant functional groups in biological networks [46]. One notable cohesive subgraph model is the clique, which requires that every pair of vertices is connected by an edge [11, 17, 22, 37, 38, 41, 43, 44]. However, the strict completeness requirement of cliques is often too restrictive for real-world applications due to data quality issues caused by noise and missing values. To solve this issue, recent studies have relaxed the clique model and proposed various clique relaxation models, including quasiclique [32, 40, 49, 54, 55], 𝑘-plex [15, 26, 42, 48, 50, 56], 𝑘-club [9], and 𝑘-defective clique [13, 14, 16, 19, 25, 31, 36, 52]. In this paper, we focus on the 𝑘-defective clique model, which relaxes the clique model by allowing up to 𝑘 missing edges, where 𝑘 is a positive integer. Conceptually, a 𝑘-defective clique is a subgraph induced
by a set of vertices 𝑆 that contains at least |𝑆2 | − 𝑘 edges. We study the problem of finding the maximum 𝑘-defective clique, i.e., the one with the largest number of vertices, which has been used for various applications such as interaction prediction in biological networks [52], cluster detection [20], and social network analysis [28]. State-of-the-art methods. Recently, a number of exact algorithms have been proposed in the literature for finding the maximum 𝑘defective clique [13, 14, 16, 19, 25, 30, 31, 36]. The majority of them follow a similar branch-and-bound (BB) framework [13, 14, 19]. Specifically, this framework recursively partitions the problem into two sub-problems on smaller subgraphs via a branching method, continuing until each sub-problem can be solved trivially (i.e., the corresponding subgraph is already a 𝑘-defective clique). Each subproblem corresponds to a branch. To improve efficiency, reduction rules are developed to prune unpromising branches that cannot contain the largest 𝑘-defective clique. Among these reductions,

upper-bound-based pruning is often the most powerful in practice. The rationale is that the algorithm computes an upper bound on the size of any 𝑘-defective clique derivable from the current branch, and it safely prunes the branch if this upper bound is not larger than the size of the largest 𝑘-defective clique found so far. Therefore, tight upper bounds are preferred to enhance practical performance. In terms of theoretical complexity, we note that recent works focus on sharpening the branching method to improve the worst-case time complexity. The best known complexity is 𝑂 ∗ (𝛾𝑘𝑛 ) [19], where 𝑂 ∗ suppresses polynomial factors, 𝑛 is the number of vertices, and 𝛾𝑘 is the largest real root of the equation 𝑥 𝑘+3 − 2𝑥 𝑘+2 + 𝑥 2 − 𝑥 + 1 = 0. While some recent approaches, such as DnBK [36] and WODC [30], attempt to depart from the standard BB framework to reduce the exponential base of the time complexity, these theoretical improvements come at a prohibitive cost. Specifically, they introduce a substantial overhead factor scaled by (𝛿Δ) Θ(𝑘 ) , where 𝛿 and Δ denote the degeneracy and maximum degree of the graph, respectively. In real-world graphs where Δ is typically large, this overhead explodes as 𝑘 increases, rendering such methods computationally impractical for difficult instances. Consequently, existing state-of-the-art algorithms, whether adhering to the standard BB framework or alternative paradigms, still suffer from significant efficiency bottlenecks in both theory and practice.

in a branch, by leveraging double graph coloring and max-flow techniques. Specifically, we perform graph coloring twice, assigning each vertex a pair of colors. Then, based on the double-coloring information, we construct a constrained max-flow problem to compute the upper bound. Compared to existing color-based upper bounds [14, 16, 19] that also utilize graph coloring, our upper bound UB-Double is practically tighter, as it leverages more topological information by applying graph coloring twice and incorporating the max-flow technique. We remark that this upper bound is orthogonal to the branch-and-bound framework and can also be applied to existing methods [13, 14, 16, 19, 25, 31]. Contributions. We summarize our main contributions as follows. • We propose a new branch-and-bound algorithm called BBRes which is based on our newly developed early termination strategy and branching strategy. BBRes has the worst-case time complexity of 𝑂 ∗ (𝜆𝑘𝑛 ), improving upon the state-of-the-art method [19] since 𝜆𝑘 is strictly smaller than 𝛾𝑘 for 𝑘 ≥ 1. (Section 4) • We further propose a new upper bound of the size of 𝑘-defective cliques to be found in a branch based on the double graph coloring technique and the max-flow technique. Our upper bound is tighter than the existing ones in practice. (Section 5) • Finally, we conduct extensive experiments on a collection of 139 real-world graphs. The results show that our BBRes outperforms other baselines, including kDC2 [14], MDC [19], DnBK [36], and WODC [30], by solving more problem instances. (Section 6) For the rest of the paper, we define the problem in Section 2, present state-of-the-art methods in Section 3, review related work in Section 7, and conclude the paper in Section 8.

Our method. In this paper, instead of solely refining the branching strategies as existing methods do, we focus on both the termination strategy and the branching strategy. Specifically, we observe that existing methods terminate the recursive branching procedure of generating new branches only when the current sub-problem can be solved trivially, which incurs an excessive number of recursive calls to reach such a trivial branch. As a result, they generate an excessive number of branches. Motivated by this, we propose to terminate the recursive branching procedure once the current sub-problem can be solved efficiently (e.g., in polynomial time) via a non-recursive solver, thereby generating fewer branches. We call this strategy the early termination strategy. To implement this strategy, we first formulate non-trivial input-restricted problems (of finding the largest 𝑘-defective clique) called MissingTwoDeg, which corresponds to a collection of non-trivial branches. Then, we develop a greedy method called IRSolver to solve MissingTwoDeg instances in polynomial time. Based on IRSolver, our early termination strategy halts the recursive branching and invokes IRSolver when the current branch corresponds to an input-restricted problem. Furthermore, to fully exploit the potential of our early termination strategy, we design a new branching strategy called BS-three. Compared to existing strategies, BS-three better complements the early termination strategy as it tends to generate fewer branches. With the early termination strategy and new branching strategy, our branch-and-bound algorithm called BBRes achieves the worstcase time complexity of 𝑂 ∗ (𝜆𝑘𝑛 ), where 𝜆𝑘 is the largest real root of the equation 𝑥 𝑘+4 − 2𝑥 𝑘+3 + 𝑥 3 − 𝑥 + 1 = 0. For example, 𝜆𝑘 = 1.381, 1.705, 1.867 when 𝑘 = 1, 2, 3, respectively. We remark that, compared to the state-of-the-art method MDC [19], our BBRes further improves the worst-case time complexity from 𝑂 ∗ (𝛾𝑘𝑛 ) to 𝑂 ∗ (𝜆𝑘𝑛 ), where 𝜆𝑘 is strictly smaller than 𝛾𝑘 for 𝑘 ≥ 1. In addition, to further boost practical performance, we propose a new upper bound on the size of the 𝑘-defective clique to be found

2

PRELIMINARIES

We consider an unweighted and undirected graph 𝐺 = (𝑉 , 𝐸), where 𝑉 is the vertex set and 𝐸 is the edge set. Let 𝑛 = |𝑉 | and 𝑚 = |𝐸| denote the number of vertices and edges, respectively. We define 𝐸 as the set of edges that are missing in 𝐺 (referred to as non-edges), i.e., 𝐸 = {(𝑢, 𝑣) ∈ 𝑉 × 𝑉 | 𝑢 ≠ 𝑣 and (𝑢, 𝑣) ∉ 𝐸}. Given a vertex 𝑣 in 𝑉 , let 𝑁𝐺 (𝑣) (resp. 𝑁 𝐺 (𝑣)) be the set of neighbors (resp. non-neighbors) of 𝑣 in 𝐺; formally, 𝑁𝐺 (𝑣) = {𝑢 ∈ 𝑉 | (𝑢, 𝑣) ∈ 𝐸} (resp. 𝑁 𝐺 (𝑣) = {𝑢 ∈ 𝑉 | (𝑢, 𝑣) ∈ 𝐸}). Accordingly, we define the degree of 𝑣 in 𝐺 as 𝑑𝐺 (𝑣) = |𝑁𝐺 (𝑣)|, and its nondegree as 𝑑 𝐺 (𝑣) = |𝑁 𝐺 (𝑣)|. We note that a vertex is neither a neighbor nor a non-neighbor of itself. Given a vertex subset 𝑆 ⊆ 𝑉 , we use 𝐺 [𝑆] to denote the subgraph of 𝐺 induced by 𝑆, i.e., 𝐺 [𝑆] consists of the set of vertices 𝑆 and the set of edges {(𝑢, 𝑣) ∈ 𝐸 | 𝑢, 𝑣 ∈ 𝑆 }. All subgraphs considered in this paper are induced subgraphs. Given a subgraph 𝑔 of 𝐺, we use 𝑉 (𝑔), 𝐸 (𝑔), and 𝐸 (𝑔) to denote its sets of vertices, edges, and non-edges, respectively. Abbreviations. For simplicity, we omit the subscript 𝐺 from the notation when the context is clear. Furthermore, for 𝑆 ⊆ 𝑉 , we abbreviate 𝑁𝐺 [𝑆 ] (·) as 𝑁𝑆 (·), 𝑑𝐺 [𝑆 ] (·) as 𝑑𝑆 (·), and 𝐸 (𝐺 [𝑆]) as 𝐸 (𝑆). Similarly, we abbreviate 𝑁 𝐺 [𝑆 ] (·), 𝑑 𝐺 [𝑆 ] (·), and 𝐸 (𝐺 [𝑆]) as 𝑁 𝑆 (·), 𝑑 𝑆 (·), and 𝐸 (𝑆), respectively. In this paper, we focus on the concept of 𝑘-defective clique. Definition 2.1 (𝑘-Defective Clique [52]). A graph 𝑔 is said to be a 𝑘-defective clique if it contains at most 𝑘 non-edges, i.e., |𝐸 (𝑔)| ≤ 𝑘 |𝑉 (𝑔) | ( |𝑉 (𝑔) | −1) or equivalently, |𝐸 (𝑔)| ≥ − 𝑘. 2 2

Algorithm 1: The state-of-the-art branch-and-bound (BB) framework [13, 14, 19]

Clearly, a 0-defective clique is simply a clique, in which every pair of vertices is adjacent. In addition, we note that the 𝑘-defective clique satisfies the hereditary property, i.e., any subgraph of a 𝑘defective clique is also a 𝑘-defective clique [39]. We now formally state the problem studied in this paper.

Input: A graph 𝐺 = (𝑉 , 𝐸 ) and a positive integer 𝑘 Output: The maximum 𝑘-defective clique 𝑔∗ /* Stage-I: With the diameter-two property */ ∗ 1 Let 𝑔 ← ∅ be the largest 𝑘-defective clique seen so far; 2 Let 𝑉 = {𝑣1 , 𝑣2 , . . . , 𝑣𝑛 } be a degeneracy ordering of vertices in 𝐺; 3 foreach 𝑣𝑖 ∈ {𝑣1 , 𝑣2 , · · · , 𝑣𝑛 } do 4 𝐺 𝑣𝑖 ← the subgraph of 𝐺 induced by 𝑁 ≤2 (𝑣𝑖 ) ∩ {𝑣𝑖 , 𝑣𝑖+1 , . . . , 𝑣𝑛 } ; 5 BB_Rec(𝐺 𝑣𝑖 , {𝑣𝑖 }, 𝑉 (𝐺 𝑣𝑖 ) \ {𝑣𝑖 } );

Problem Definition (Maximum 𝑘-Defective Cliqe [13, 14, 16, 19, 25, 36]). Given a graph 𝐺 = (𝑉 , 𝐸) and a positive integer 𝑘, the maximum 𝑘-defective clique problem aims to find the maximum 𝑘-defective clique in 𝐺, i.e., the 𝑘-defective clique with the largest number of vertices. We note that the maximum 𝑘-defective clique in 𝐺 may not be unique, and the maximum 𝑘-defective clique problem is known to be NP-hard [35, 45]. Moreover, although a larger 𝑘 relaxes the feasibility constraint, it also enlarges the family of feasible solutions. In particular, the number of maximal 𝑘-defective cliques can grow exponentially with 𝑘 [13, 14, 19], resulting in a larger search space and making the problem harder in practice.

3

/* Stage-II: Without the diameter-two property if |𝑉 (𝑔∗ ) | < 𝑘 + 1 then BB_Rec(𝐺, ∅, 𝑉 ); ∗ 7 return 𝑔 ;

*/

6

Procedure BB_Rec(𝑔, 𝑆, 𝐶 ) /* Reduction 9 𝑈 𝐵 ← an upper bound of the branch; 10 if 𝑈 𝐵 ≤ |𝑉 (𝑔∗ ) | then return; 11 Refine 𝐶 (and 𝑔) by applying reduction rules; /* Termination 12 if 𝑔 is a 𝑘-defective clique then 13 if |𝑉 (𝑔) | > |𝑉 (𝑔∗ ) | then 𝑔∗ ← 𝑔; 14 return; 8

STATE-OF-THE-ART ALGORITHMS

The state-of-the-art algorithms for the maximum 𝑘-defective clique predominantly adopt the branch-and-bound (BB) framework [13, 14, 19]. The core idea is to recursively partition the current problem instance (i.e., search space), which aims to find the largest 𝑘-defective clique, into two smaller sub-problems via branching until each of them can be solved trivially. Specifically, a problem instance (or branch) is represented as a triple (𝑔, 𝑆, 𝐶), where: • Graph 𝑔 is a subgraph of the input graph 𝐺 induced by the vertex set 𝑆 ∪ 𝐶, i.e., 𝑔 = 𝐺 [𝑆 ∪ 𝐶]; • Partial set 𝑆 is a set of vertices that induces a 𝑘-defective clique and must be contained in the largest 𝑘-defective clique found within this branch; • Candidate set 𝐶 is a set of vertices that will be considered to be included in 𝑆. Solving a branch (𝑔, 𝑆, 𝐶) means finding in this branch the largest 𝑘-defective clique 𝑔∗ that (1) includes all vertices in 𝑆 and (2) is a subgraph of 𝑔, i.e., 𝑆 ⊆ 𝑉 (𝑔∗ ) and 𝑉 (𝑔∗ ) ⊆ 𝐶 ∪ 𝑆. Clearly, solving the branch (𝐺, ∅, 𝑉 ) finds the maximum 𝑘-defective clique in 𝐺. To solve a branch (𝑔, 𝑆, 𝐶), the framework recursively partitions the branch into two sub-branches via branching. In particular, it selects a vertex 𝑣 ∗ called pivot from the candidate set 𝐶, and generates two sub-branches. The first one (𝑔1, 𝑆 ∪ {𝑣 𝑝 }, 𝐶 \ {𝑣 𝑝 }) removes the pivot 𝑣 𝑝 from 𝐶 to 𝑆 (which aims to explore the largest 𝑘-defective clique that includes 𝑣 𝑝 ); the second one (𝑔2, 𝑆, 𝐶 \ {𝑣 𝑝 }) discards the pivot 𝑣 𝑝 from 𝐶 (which aims to explore the largest 𝑘-defective clique that excludes 𝑣 𝑝 ). Here, 𝑔1 and 𝑔2 are the subgraphs induced by the updated partial and candidate sets in each sub-branch. By recursively solving both sub-branches, the framework ensures that all possibilities are explored and thus solves the original branch. Summary. We summarize the BB framework in Algorithm 1. Specifically, the algorithm maintains the largest 𝑘-defective clique 𝑔∗ seen so far during the recursion (Line 1). To boost the practical performance, it utilizes the diameter-two property ([16]) of large 𝑘-defective cliques (i.e., any 𝑘-defective clique with at least 𝑘 + 2 vertices has diameter at most 2) and involves the following stages. • Stage-I adopts the diameter-two property for pruning by assuming that the largest 𝑘-defective clique is of size at least

15 16 17 18

/* Branching 𝑣𝑝 ← a pivot selected from 𝐶; Construct 𝑔1 and 𝑔2 based on 𝑣𝑝 , 𝑆, and 𝐶; BB_Rec(𝑔1 , 𝑆 ∪ {𝑣𝑝 }, 𝐶 \ {𝑣𝑝 } ); BB_Rec(𝑔2 , 𝑆, 𝐶 \ {𝑣𝑝 } );

*/

*/

*/

𝑘 + 2 (Lines 2-5). Specifically, it first computes a degeneracy ordering of the vertices in 𝐺 (Line 2), which can be done efficiently in 𝑂 (𝑚) by the peeling algorithm [6]. Then, it divides the problem of finding the maximum 𝑘-defective clique into 𝑛 sub-problems (Lines 3-5). The 𝑖-th one aims to find the maximum 𝑘-defective clique that (1) includes 𝑣𝑖 and (2) is a subgraph of 𝐺 [{𝑣𝑖 , 𝑣𝑖+1, ..., 𝑣𝑛 }] by invoking the BB procedure with the branch (𝐺 𝑣𝑖 , {𝑣𝑖 }, 𝑉 (𝐺 𝑣𝑖 ) \ {𝑣𝑖 }) (Lines 3-5). In particular, 𝐺 𝑣𝑖 is the subgraph of 𝐺 induced by 𝑣𝑖 ’s two-hop neighbors in {𝑣𝑖 , 𝑣𝑖+1, ..., 𝑣𝑛 }, i.e., 𝑁 ≤2 (𝑣𝑖 ) ∩ {𝑣𝑖 , 𝑣𝑖+1, . . . , 𝑣𝑛 } (note that a 𝑘-defective clique with at least 𝑘 + 2 vertices has diameter of at most 2 and thus the largest one containing 𝑣𝑖 is a subset of 𝑁 ≤2 (𝑣𝑖 )). Clearly, if the found largest 𝑘-defective clique 𝑔∗ is of at least 𝑘 + 1 vertices, 𝑔∗ is guaranteed to be a maximum 𝑘-defective clique of 𝐺. • Stage-II continues the search for the maximum 𝑘-defective clique when Stage-I does not succeed, i.e., when 𝑔∗ obtained in Stage-I has fewer than 𝑘 + 1 vertices (Line 6). To this end, it invokes the BB procedure with the branch (𝐺, ∅, 𝑉 ). In addition, the BB procedure called BB_Rec is summarized in Lines 8-18. We note that the recursive procedure terminates when 𝑔 becomes a 𝑘-defective clique since 𝑔 is the largest 𝑘-defective clique in the branch (Lines 12-14). To reduce the search space, the framework employs two techniques as follows. • Upper-bound-based reductions (Lines 9-10). It first computes an upper bound of the size of the largest 𝑘-defective clique in the 3

Algorithm 2: Our framework BBRes

branch. Then, the branch can be terminated if the upper bound is no larger than the largest 𝑘-defective clique seen so far. • Pivot-based branching (Lines 15-18). The number of branches generated by the pivot-based branching depends on the pivot selection strategy (Line 15). We note that recent studies have explored various strategies for pivot selection to reduce the number of branches [13, 14, 19]. For brevity, we do not review the detailed implementation of these techniques in state-of-the-art algorithms.

Input: A graph 𝐺 = (𝑉 , 𝐸 ) and a positive integer 𝑘 Output: The maximum 𝑘-defective clique 𝑔∗ /* Stage-I: With the diameter-two property */ ∗ 1 Let 𝑔 ← ∅ be the largest 𝑘-defective clique seen so far; 2 Let 𝑉 = {𝑣1 , 𝑣2 , . . . , 𝑣𝑛 } be a degeneracy ordering of vertices in 𝐺; 3 foreach 𝑣𝑖 ∈ {𝑣1 , 𝑣2 , · · · , 𝑣𝑛 } do 4 𝐺 𝑣𝑖 ← the subgraph of 𝐺 induced by 𝑁 ≤2 (𝑣𝑖 ) ∩ {𝑣𝑖 , 𝑣𝑖+1 , . . . , 𝑣𝑛 } ; 5 BBRes_Rec(𝐺 𝑣𝑖 , {𝑣𝑖 }, 𝑉 (𝐺 𝑣𝑖 ) \ {𝑣𝑖 } );

Time complexity. Following Algorithm 1, the state-of-the-art studies have focused on improving the worst-case time complexity by sharpening the pivot selection strategy [13, 14, 19]. As a result, the latest algorithm has the time complexity of 𝑂 ∗ (𝛾𝑘𝑛 ) [19], where 𝑂 ∗ ignores the polynomial factors and 𝛾𝑖 is the largest real root of the equation 𝑥 𝑖+3 − 2𝑥 𝑖+2 + 𝑥 2 − 𝑥 + 1 = 0.

/* Stage-II: Without the diameter-two property if |𝑉 (𝑔∗ ) | < 𝑘 + 1 then BBRes_Rec(𝐺, ∅, 𝑉 ); ∗ 7 return 𝑔 ;

*/

6

Procedure BBRes_Rec(𝑔, 𝑆, 𝐶 ) /* Reductions (Section 5) */ 9 𝑈 𝐵 ← an upper bound of the branch; 10 if 𝑈 𝐵 ≤ |𝑉 (𝑔∗ ) | then return; 11 Refining 𝐶 (and 𝑔) by applying reduction rules; /* Early Termination Strategy (Section 4.2) */ 12 if 𝑔 satisfies the early termination conditions, i.e., Condition 1 or Condition 2 in Section 4.2 then 13 𝑔𝑜𝑝𝑡 ←IRSolver(𝑔, 𝑆, 𝐶 ); 14 if |𝑉 (𝑔𝑜𝑝𝑡 ) | > |𝑉 (𝑔∗ ) | then 𝑔∗ ← 𝑔𝑜𝑝𝑡 ; 15 return; 8

Remark. It is worth noting that two recent algorithms, DnBK [36] and WODC [30], employ frameworks distinct from the above BB framework to successfully reduce the exponential base in time complexity. However, this improvement comes at the cost of introducing a substantial overhead factor scaled by (𝛿Δ) Θ(𝑘 ) , where 𝛿 is the degeneracy of the input graph 𝐺 and Δ is the maximum degree of 𝐺. This factor becomes prohibitively large when 𝑘 is not a constant, severely limiting scalability. As demonstrated in our experiments (Section 6), both methods are less competitive compared to our proposed algorithm. We defer the detailed complexity analysis of both algorithms to the related work section (Section 7).

16 17 18

4

A NEW BRANCH-AND-BOUND FRAMEWORK: BBRES 4.1 BBRes: Motivation and Overview

/* Branching (Section 4.3) 𝑣𝑝 ← a pivot selected from 𝐶 based on our new strategy; BBRes_Rec(𝑔1 , 𝑆 ∪ {𝑣𝑝 }, 𝐶 \ {𝑣𝑝 } ); BBRes_Rec(𝑔2 , 𝑆, 𝐶 \ {𝑣𝑝 } );

*/

uses IRSolver to solve the branch. Furthermore, we observe that the existing branching strategies are not suitable for our BBRes since they are designed based on the framework of recursively branching to trivial branches. To boost the performance of BBRes, we further propose a new branching strategy in Section 4.3. With this newlydesigned branching strategy, BBRes achieves better worst-case time complexity. In addition, we remark that we propose a novel upper bound (Lines 9-11) based on graph coloring and max-flow techniques (details will be discussed in Section 5), which is orthogonal to the framework and further enhances practical performance. We remark that our BBRes also employs those existing techniques, including reductions and pre-processing techniques for reducing the input graph [14, 19, 30], that are orthogonal to the framework.

Motivation. The existing BB framework recursively partitions the current problem instance (𝑔, 𝑆, 𝐶) into two sub-problems via branching until each of them can be solved trivially, i.e., 𝑔 becomes a 𝑘-defective clique. As a result, the branching procedure, which is biased towards generating trivial instances, produces an exponentially large number of branches in the worst case (e.g., 𝑂 (𝛾𝑘𝑛 ) [19]), thereby dominating the time complexity. To reduce the number of branches, we propose to guide the branching procedure towards non-trivial yet solvable problem instances. The rationale is to terminate the recursive branching procedure early whenever the current problem instance can be solved efficiently (e.g., in polynomial time) by a dedicated solver, thus generating fewer branches. Overview. Motivated by the above, we develop a new BB framework called BBRes, as summarized in Algorithm 2. BBRes differs from Algorithm 1 mainly in the early termination strategy (Lines 12-15) and the branching strategy (Lines 16-18). Specifically, we first formulate an input-restricted problem instance (i.e., a branch (𝑔, 𝑆, 𝐶) satisfying certain constraints), which is non-trivial (i.e., 𝑔 can be a non-𝑘-defective clique). Note that such input-restricted instances will be solved recursively via branching in Algorithm 1. However, we observe that these instances can be solved efficiently in polynomial time by a non-recursive method called IRSolver in Section 4.2. Based on this observation, our BBRes can terminate the recursive branching procedure once it reaches an inputrestricted instance, i.e., satisfying the termination conditions, and

4.2

BBRes: Early Termination Strategy

Consider a problem instance (𝑔, 𝑆, 𝐶). Note that a problem instance (𝑔, 𝑆, 𝐶) is said to be trivial if 𝑔 is a 𝑘-defective clique. Our early termination strategy is motivated by the observation that certain non-trivial instances admit a particularly simple structure. Specifically, if every vertex in the candidate set 𝐶 has at most two nonneighbors within 𝐶, then in the complement graph of 𝐺 [𝐶], every vertex has degree at most 2. Hence, each connected component of the complement graph is a path, a cycle, or an isolated vertex. This structural property enables an efficient algorithm for the remaining subproblem. Thus, we define the input-restricted problem instances, namely MissingTwoDeg, as follows. 4

number of non-neighbors in 𝐶𝑡𝑒𝑚𝑝 as 𝑣 ∗ , formally,

Algorithm 3: Our greedy method IRSolver Input: A MissingTwoDeg problem instance (𝑔, 𝑆, 𝐶 ) and a positive integer 𝑘 Output: The maximum 𝑘-defective clique 𝑔𝑜𝑝𝑡 that is a subgraph of 𝑔 and contains 𝑆 1 if 𝑔 is a 𝑘-defective clique then return 𝑔 as 𝑔𝑜𝑝𝑡 directly; 2 𝑆𝑜𝑝𝑡 ← 𝑆, 𝐶𝑡𝑒𝑚𝑝 ← 𝐶; 3 while true do 4 Γ𝑚𝑖𝑛 ← {𝑣 ∈ 𝐶𝑡𝑒𝑚𝑝 | ∀𝑤 ∈ 𝐶𝑡𝑒𝑚𝑝 , 𝑑 𝑆𝑜𝑝𝑡 (𝑣) ≤ 𝑑 𝑆𝑜𝑝𝑡 (𝑤 ) }; 5 6 7 8 9 10 11

Greedy strategy 1: 𝑣 ∗ ← arg min 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣).

• Case 2: min𝑣 ∈Γ𝑚𝑖𝑛 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣) = 2, i.e., each vertex in Γ𝑚𝑖𝑛 has two non-neighbors in 𝐶𝑡𝑒𝑚𝑝 . Then, we select from Γ𝑚𝑖𝑛 the vertex with the smallest number of non-neighbors in Γ𝑚𝑖𝑛 , formally, Greedy strategy 2: 𝑣 ∗ ← arg min 𝑑 Γ𝑚𝑖𝑛 (𝑣).

(3)

𝑣 ∈Γ𝑚𝑖𝑛

if Case 1: min𝑣 ∈Γ𝑚𝑖𝑛 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣) ≤ 1 then 𝑣 ∗ ← arg min𝑣 ∈Γ𝑚𝑖𝑛 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣);

We note that every vertex in 𝐶𝑡𝑒𝑚𝑝 has at most two non-neighbors in 𝐶𝑡𝑒𝑚𝑝 based on the definition of the MissingTwoDeg problem. Thus, the above strategy covers all possible cases. In addition, we remark that if there are multiple choices when selecting 𝑣 ∗ in Equation (2) or Equation (3), e.g., more than one vertex in Γ𝑚𝑖𝑛 has the smallest number of non-neighbors in 𝐶𝑡𝑒𝑚𝑝 or Γ𝑚𝑖𝑛 , 𝑣 ∗ can be chosen arbitrarily from among them. We also provide an example of IRSolver in Section B of our technical report [1].

else if Case 2: min𝑣 ∈Γ𝑚𝑖𝑛 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣) = 2 then 𝑣 ∗ ← arg min𝑣 ∈Γ𝑚𝑖𝑛 𝑑 Γ𝑚𝑖𝑛 (𝑣); if 𝐺 [𝑆𝑜𝑝𝑡 ∪ {𝑣 ∗ } ] is not a 𝑘-defective clique then break; 𝐶𝑡𝑒𝑚𝑝 ← 𝐶𝑡𝑒𝑚𝑝 \ {𝑣 ∗ }; 𝑆𝑜𝑝𝑡 ← 𝑆𝑜𝑝𝑡 ∪ {𝑣 ∗ }; return 𝐺 [𝑆𝑜𝑝𝑡 ] as the solution 𝑔𝑜𝑝𝑡 ;

Correctness of IRSolver. The correctness of IRSolver can be guaranteed by the following lemma.

Definition 4.1 (MissingTwoDeg problem instance). A problem instance (𝑔, 𝑆, 𝐶) is said to be a MissingTwoDeg problem if it satisfies one of the following conditions: • Condition 1. 𝑔 is a 𝑘-defective clique, i.e., |𝐸 (𝑔)| ≤ 𝑘; • Condition 2. 𝑔 is not a 𝑘-defective clique, and for any vertex 𝑣 in 𝐶, 𝑣 has at most 2 non-neighbors in 𝐶, i.e., |𝐸 (𝑔)| > 𝑘 and ∀𝑣 ∈ 𝐶, 𝑑 𝐶 (𝑣) ≤ 2.

Lemma 4.2. Given a MissingTwoDeg problem instance (𝑔, 𝑆, 𝐶), IRSolver finds the largest 𝑘-defective clique 𝑔𝑜𝑝𝑡 that is a subgraph of 𝑔 and contains all vertices in 𝑆. Proof. Note that if 𝑔 is a 𝑘-defective clique, the problem can be directly solved by returning 𝑔 (Line 1). In the following, we assume that 𝑔 is not a 𝑘-defective clique. Clearly, IRSolver can terminate at Line 9 since 𝑆 ∪ 𝐶 is a superset of 𝑆𝑜𝑝𝑡 and is not a 𝑘-defective clique. Thus, assume that IRSolver runs in 𝜏 + 1 rounds (𝜏 ≥ 1). At the 𝑖-th (1 ≤ 𝑖 ≤ 𝜏) round, it adds 𝑣𝑖∗ to 𝑆𝑜𝑝𝑡 . Finally, it terminates at ∗ } is no longer a 𝑘-defective the (𝜏 + 1)-st round since 𝑆 ∪ {𝑣 1∗, ..., 𝑣𝜏+1 clique. In addition, for 0 ≤ 𝑖 ≤ 𝜏 + 1, we let

Condition 1 corresponds to the trivial termination case, whereas instances satisfying Condition 2 are non-trivial but remain tractable due to the special structure of the complement graph induced by 𝐶. Thus, terminating the branching procedure once a MissingTwoDeg instance is reached can reduce the number of generated branches while still allowing the remaining subproblem to be solved efficiently. One remaining question is how to solve a MissingTwoDeg problem efficiently in polynomial time. To this end, we introduce a greedy method called IRSolver. Overview of IRSolver. If 𝑔 is a 𝑘-defective clique, we can solve the problem by returning 𝑔 directly. Otherwise, IRSolver solves the problem in a greedy manner, which runs in multiple rounds, as summarized in Algorithm 3. Specifically, it maintains two sets 𝑆𝑜𝑝𝑡 (initially as 𝑆) and 𝐶𝑡𝑒𝑚𝑝 (initially as 𝐶). The key idea is to iteratively select a vertex 𝑣 ∗ from 𝐶𝑡𝑒𝑚𝑝 and move it from 𝐶𝑡𝑒𝑚𝑝 to 𝑆𝑜𝑝𝑡 while maintaining that 𝐺 [𝑆𝑜𝑝𝑡 ] is a 𝑘-defective clique until this is no longer possible (Lines 3-10, details will be discussed later). Finally, it returns 𝐺 [𝑆𝑜𝑝𝑡 ] as the solution (Line 11). We then elaborate on the details regarding the greedy strategy of selecting 𝑣 ∗ , the correctness, and the time complexity analysis. Greedy strategy of IRSolver. At each round (Lines 3-10), IRSolver selects a vertex 𝑣 ∗ from 𝐶𝑡𝑒𝑚𝑝 based on the following greedy strategy. Specifically, let Γ𝑚𝑖𝑛 be the set of vertices each of which has the smallest number of non-neighbors in 𝑆𝑜𝑝𝑡 , formally, Γ𝑚𝑖𝑛 = {𝑣 ∈ 𝐶𝑡𝑒𝑚𝑝 | ∀𝑤 ∈ 𝐶𝑡𝑒𝑚𝑝 , 𝑑 𝑆𝑜𝑝𝑡 (𝑣) ≤ 𝑑 𝑆𝑜𝑝𝑡 (𝑤)}.

(2)

𝑣 ∈Γ𝑚𝑖𝑛

𝑖 𝑖 𝑆𝑜𝑝𝑡 = 𝑆 ∪ {𝑣 1∗, ..., 𝑣𝑖∗ } and 𝐶𝑡𝑒𝑚𝑝 = 𝐶 \ {𝑣 1∗, ..., 𝑣𝑖∗ }.

(4)

𝑖 𝑖 𝑖 Γ𝑚𝑖𝑛 = {𝑣 ∈ 𝐶𝑡𝑒𝑚𝑝 | ∀𝑤 ∈ 𝐶𝑡𝑒𝑚𝑝 , 𝑑 𝑆 𝑖 (𝑣) ≤ 𝑑 𝑆 𝑖 (𝑤)}

(5)

𝑜𝑝𝑡

𝑜𝑝𝑡

0 and 𝐶 0 Note that 𝑆𝑜𝑝𝑡 𝑡𝑒𝑚𝑝 are 𝑆 and 𝐶, respectively. 𝜏 ] We first show that, when IRSolver terminates, 𝑔𝑜𝑝𝑡 = 𝐺 [𝑆𝑜𝑝𝑡 is a maximal 𝑘-defective clique in 𝑔, i.e., any vertex in 𝐶 \ 𝑉 (𝑔𝑜𝑝𝑡 ) cannot be added to 𝑔𝑜𝑝𝑡 to form a larger 𝑘-defective clique. The reasons are as follows. Consider the last round of IRSolver where 𝜏 ∗ }] is no longer a 𝑘-defective clique. We note that 𝐺 [𝑆𝑜𝑝𝑡 ∪ {𝑣𝜏+1 ∗ has the smallest number of non-neighbors in 𝑆 𝜏 among other 𝑣𝜏+1 𝑜𝑝𝑡 𝜏 vertices in 𝐶𝑡𝑒𝑚𝑝 (since it is selected from Γ𝑚𝑖𝑛 ). Therefore, for any 𝜏 𝜏 ∪ {𝑣 }] is not a 𝑘-defective clique since vertex 𝑣 in 𝐶𝑡𝑒𝑚𝑝 , 𝐺 [𝑆𝑜𝑝𝑡 𝜏 ∪ {𝑣 })| = |𝐸 (𝑆 𝜏 )| +𝑑 𝜏 (𝑣) ≥ |𝐸 (𝑆 𝜏 )| +𝑑 𝜏 (𝑣 ∗ ) > 𝑘. |𝐸 (𝑆𝑜𝑝𝑡 𝑆𝑜𝑝𝑡 𝑆𝑜𝑝𝑡 𝜏+1 𝑜𝑝𝑡 𝑜𝑝𝑡 We then show that 𝑔𝑜𝑝𝑡 is the largest 𝑘-defective clique in 𝑔 that contains 𝑆 by contradiction. Note that 𝑔𝑜𝑝𝑡 contains 𝑆 clearly since 𝑆𝑜𝑝𝑡 is a superset of 𝑆. Let 𝑔𝑠𝑜𝑙 be the largest 𝑘-defective clique in 𝑔 that contains 𝑆. Assume that 𝑔𝑜𝑝𝑡 is not the largest 𝑘-defective clique that contains 𝑆, i.e., |𝑉 (𝑔𝑠𝑜𝑙 )| > |𝑉 (𝑔𝑜𝑝𝑡 )|. Then, we will show that, by the following construction process starting with 𝑔𝑠𝑜𝑙 , there exists a largest 𝑘-defective clique 𝑔′ containing 𝑆 such that 𝑔𝑜𝑝𝑡 is a subgraph of 𝑔′ , i.e., 𝑉 (𝑔𝑜𝑝𝑡 ) ⊂ 𝑉 (𝑔′ ), which contradicts to the fact that 𝑔𝑜𝑝𝑡 is a maximal 𝑘-defective clique in 𝑔.

(1)

Then, we select vertex 𝑣 ∗ from Γ𝑚𝑖𝑛 . In general, there are two cases. • Case 1: min𝑣 ∈Γ𝑚𝑖𝑛 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣) ≤ 1, i.e., there exists a vertex 𝑣 in Γ𝑚𝑖𝑛 that has the number of non-neighbors in 𝐶𝑡𝑒𝑚𝑝 smaller than 2. In this case, we select from Γ𝑚𝑖𝑛 the vertex with the smallest 5

Finally, to complete the proof, we introduce an iterative process to construct 𝑔′ based on 𝑔𝑜𝑝𝑡 and 𝑔𝑠𝑜𝑙 . Let ⟨𝑣 1∗, 𝑣 2∗, ..., 𝑣𝜏∗ ⟩ be the ordering of vertices in 𝑉 (𝑔𝑜𝑝𝑡 ) \ 𝑆. The procedure has four steps. • Step 1: Initialization. Initialize 𝑔0′ to be 𝑔𝑠𝑜𝑙 and 𝑖 to be 0; • Step 2: Termination checking. If 𝑔𝑖′ contains all vertices in 𝑔𝑜𝑝𝑡 , i.e., 𝑉 (𝑔𝑖′ ) ⊇ 𝑉 (𝑔𝑜𝑝𝑡 ), set 𝑔′ = 𝑔𝑖′ and stop the process. • Step 3: Construction. Find the vertex 𝑣𝑜∗𝑖 with the smallest index 𝑜𝑖 (1 ≤ 𝑜𝑖 ≤ 𝜏) that is in 𝑉 (𝑔𝑜𝑝𝑡 ) \ 𝑆 but not in 𝑔𝑖′ . We can easily 𝑜𝑖 −1 𝑜𝑖 −1 deduce that 𝑔𝑖′ contains all vertices in 𝑆𝑜𝑝𝑡 and 𝑉 (𝑔𝑖′ ) \ 𝑆𝑜𝑝𝑡 is 𝑜𝑖 −1 a subset of 𝐶𝑡𝑒𝑚𝑝 , formally, 𝑜𝑖 −1 𝑜𝑖 −1 𝑜𝑖 −1 𝑆𝑜𝑝𝑡 ⊆ 𝑉 (𝑔𝑖′ ) and 𝑉 (𝑔𝑖′ ) \ 𝑆𝑜𝑝𝑡 ⊆ 𝐶𝑡𝑒𝑚𝑝 .

𝑤𝑤1

𝑤𝑤5

𝑤𝑤2

𝑤𝑤3

𝑤𝑤4

(b) Illustrating {𝑤𝑥 1 +1 , ..., 𝑤𝑥𝑡 +1 }

set of vertices {𝑤 𝑥 1 , 𝑤 𝑥 2 , ..., 𝑤 𝑥𝑡 } with {𝑤 𝑥 1 +1, 𝑤 𝑥 2 +1, ..., 𝑤 𝑥𝑡 +1 }, ′ i.e., 𝑔𝑖+1 = 𝑔[𝑉 (𝑔𝑖′ )\{𝑤 𝑥 1 , 𝑤 𝑥 2 , ..., 𝑤 𝑥𝑡 }∪{𝑤 𝑥 1 +1, 𝑤 𝑥 2 +1, ..., 𝑤 𝑥𝑡 +1 }. We can deduce that 𝑤 0 is in {𝑤 𝑥 1 +1, ..., 𝑤 𝑥𝑡 +1 } since 𝑤 0 ’s nonneighbors 𝑤 1 and 𝑤𝑐 −1 are both in Ψ𝑖 in this case. There′ fore, 𝑔𝑖+1 contains 𝑣𝑜∗𝑖 and is a 𝑘-defective clique, since (1) 𝑜𝑖 −1 every vertex in {𝑤 0, 𝑤 1, . . . , 𝑤𝑐 } belongs to Γ𝑚𝑖𝑛 , and hence all these vertices have the same number of non-neighbors in 𝑜𝑖 −1 ; and (2) we know that 𝑔1 = 𝑔[{𝑤 𝑥 1 , 𝑤 𝑥 2 , . . . , 𝑤 𝑥𝑡 }] and 𝑆𝑜𝑝𝑡 𝑔2 = 𝑔[{𝑤 𝑥 1 +1, 𝑤 𝑥 2 +1, . . . , 𝑤 𝑥𝑡 +1 }] are isomorphic under the mapping 𝑓 : 𝑉 (𝑔1 ) → 𝑉 (𝑔2 ) defined by 𝑓 (𝑤 𝑗 ) = 𝑤 𝑗+1 . Indeed, for any (𝑤 𝑥 , 𝑤 𝑦 ) ∈ 𝐸 (𝑔1 ), we have 𝑥 −𝑦 ≡ 1 (mod 𝑡), and thus (𝑥 +1) − (𝑦 +1) ≡ 1 (mod 𝑡), which implies (𝑓 (𝑤 𝑥 ), 𝑓 (𝑤 𝑦 )) = (𝑤 𝑥+1, 𝑤 𝑦+1 ) ∈ 𝐸 (𝑔2 ). Thus, the corresponding vertices have the same number of non-neighbors within the induced subgraph. • Step 4: Repetition. Increase 𝑖 by one and go to Step 2. Clearly, the invariants 𝑜𝑖 < 𝑜𝑖+1 and |𝑉 (𝑔𝑖′ )| = |𝑉 (𝑔𝑖+1 ) ′ | = |𝑉 (𝑔𝑠𝑜𝑙 )| are kept during the above construction. Therefore, it can terminate and find the largest 𝑘-defective clique 𝑔′ in 𝑔 that contains 𝑔𝑜𝑝𝑡 and has more vertices than 𝑔𝑜𝑝𝑡 , i.e., 𝑉 (𝑔𝑜𝑝𝑡 ) ⊂ 𝑉 (𝑔′ ). □

(7)

𝑜𝑝𝑡

𝑘 (note that 𝑑 Ψ𝑖 \{𝑣 } (𝑣𝑜∗𝑖 ) is clearly equal to 0 and 𝑣𝑜∗𝑖 has the 𝑜𝑖 −1 smallest number of non-neighbors in 𝑆𝑜𝑝𝑡 among other ver𝑜𝑖 −1 tices in 𝐶𝑡𝑒𝑚𝑝 based on our greedy strategy). – Case 2: 𝑑 Ψ𝑖 (𝑣𝑜∗𝑖 ) = 2 and 𝑑 Γ𝑜𝑖 −1 (𝑣𝑜∗𝑖 ) ≤ 1. In this case, all 𝑚𝑖𝑛

𝑜𝑖 −1 𝑣𝑜∗𝑖 ’s non-neighbors in 𝐶𝑡𝑒𝑚𝑝 are in Ψ𝑖 (note that both Ψ𝑖 and 𝑜𝑖 −1 𝑜𝑖 −1 Γ𝑚𝑖𝑛 are subsets of 𝐶𝑡𝑒𝑚𝑝 ). Let 𝑢 be a 𝑣𝑜∗𝑖 ’s non-neighbor in Ψ𝑖 𝑜𝑖 −1 but not in Γ𝑚𝑖𝑛 (note that such a vertex 𝑢 exits based on the ′ by swapping vertex 𝑢 condition of this case). We construct 𝑔𝑖+1 ∗ ′ ′ with 𝑣𝑜𝑖 , formally, 𝑔𝑖+1 = 𝑔[𝑉 (𝑔𝑖 )\{𝑢}∪{𝑣𝑜∗𝑖 }]. We can deduce ′ that 𝑔𝑖+1 is a 𝑘-defective clique since (1) 𝑑 𝑆 𝑜𝑖 −1 (𝑢) is strictly

Time complexity of IRSolver. The time complexity of IRSolver is bounded by 𝑂 (|𝑆 ||𝐶 | + |𝐶 | 2 ). To support the greedy selection efficiently, we employ bucket queues (a form of linear heap) to dynamically maintain, for each vertex 𝑣 in the current candidate set, the key 𝑘 (𝑣) = 3 · 𝑑 𝑆𝑜𝑝𝑡 (𝑣) + 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣). This key exactly encodes the lexicographic order first by 𝑑 𝑆𝑜𝑝𝑡 (𝑣) and then by 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣), since 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣) ≤ 2. Moreover, since 𝑑 𝑆𝑜𝑝𝑡 (𝑣) ≤ |𝑆 | + |𝐶 |, we have 𝑘 (𝑣) ∈ [0, 3(|𝑆 | + |𝐶 |)]. Accordingly, we use an array of size 3(|𝑆 | + |𝐶 |) + 1, where the 𝑖-th bucket stores a linked list of vertices whose key equals 𝑖. The initialization of IRSolver requires computing 𝑑 𝑆𝑜𝑝𝑡 (𝑣) and 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣) for all vertices in 𝐶, which takes 𝑂 (|𝑆 ||𝐶 | + |𝐶 | 2 ) time. During the greedy process, the arg min operation for selecting 𝑣 ∗ over Γ𝑚𝑖𝑛 is supported directly by the bucket structure, rather than by recomputing the minimum from scratch in each iteration. In particular, the minimum non-empty bucket exactly contains the vertices in Γ𝑚𝑖𝑛 that are minimal under the above lexicographic order. Since the maintained key is non-decreasing during the process, the pointer to the minimum non-empty bucket moves forward at most 𝑂 (|𝑆 | + |𝐶 |) times in total. In addition, deleting the selected vertex 𝑣 ∗ takes 𝑂 (1) time, and updating all affected vertices also takes 𝑂 (1) time per iteration, since each vertex in 𝐶 has at most two non-neighbors within 𝐶. Hence, after initialization,

𝑜𝑝𝑡

𝑜𝑖 −1 larger than 𝑑 𝑆 𝑜𝑖 −1 (𝑣𝑜∗𝑖 ) (note that vertices in Γ𝑚𝑖𝑛 has the 𝑜𝑝𝑡

𝑜𝑖 −1 smallest number of non-neighbors in 𝑆𝑜𝑝𝑡 and 𝑣𝑜∗𝑖 is selected 𝑜𝑖 −1 from Γ𝑚𝑖𝑛 based on our greedy strategy while 𝑢 is not in 𝑜𝑖 −1 ′ )| = |𝐸 (𝑔 ′ )| − 𝑑 ′ (𝑢) + 𝑑 ∗ Γ𝑚𝑖𝑛 ) and (2) |𝐸 (𝑔𝑖+1 𝑔𝑖 𝑉 (𝑔𝑖′ )\{𝑢 } (𝑣 𝑜𝑖 ) ≤ 𝑖

|𝐸 (𝑔𝑖′ )| − 𝑑 𝑆 𝑜𝑖 −1 (𝑢) + 𝑑 𝑆 𝑜𝑖 −1 (𝑣𝑜∗𝑖 ) + 𝑑 Ψ𝑖 \{𝑢 } (𝑣𝑜∗𝑖 ) = |𝐸 (𝑔𝑖′ )| − 𝑜𝑝𝑡

𝑑 𝑆 𝑜𝑖 −1 (𝑢) + 𝑑 𝑆 𝑜𝑖 −1 (𝑣𝑜∗𝑖 ) + 1 ≤ 𝑘. 𝑜𝑝𝑡

𝑤𝑤3

𝑤𝑤1

𝑤𝑤0

(6)

𝑑𝑉 (𝑔𝑖′ )\{𝑣 } (𝑣𝑜∗𝑖 ) ≤ |𝐸 (𝑔𝑖′ )|−𝑑 𝑆 𝑜𝑖 −1 (𝑣)+𝑑 𝑆 𝑜𝑖 −1 (𝑣𝑜∗𝑖 )+𝑑 Ψ𝑖 \{𝑣 } (𝑣𝑜∗𝑖 ) ≤

𝑜𝑝𝑡

𝑤𝑤2

𝑤𝑤4

(a) Illustrating {𝑤𝑥 1 , ..., 𝑤𝑥𝑡 }

′ (note that 𝑑 (𝑣 ∗ ) ≤ We then have three cases to construct 𝑔𝑖+1 Ψ𝑖 𝑜𝑖 𝑑 𝐶 (𝑣𝑜∗𝑖 ) ≤ 2 based on Definition 4.1). – Case 1: 𝑑 Ψ𝑖 (𝑣𝑜∗𝑖 ) ≤ 1. Let 𝑣 be an arbitrary vertex in Ψ𝑖 if 𝑑 Ψ𝑖 (𝑣𝑜∗𝑖 ) = 0; otherwise if 𝑑 Ψ𝑖 (𝑣𝑜∗𝑖 ) = 1, let 𝑣 be 𝑣𝑜∗𝑖 ’s non′ by swapping vertex 𝑣 with neighbor in Ψ𝑖 . We construct 𝑔𝑖+1 ′ ′ 𝑣𝑜∗𝑖 , formally, 𝑔𝑖+1 = 𝑔[𝑉 (𝑔𝑖′ ) \ {𝑣 } ∪ {𝑣𝑜∗𝑖 }]. Clearly, 𝑔𝑖+1 ′ ′ ′ is a 𝑘-defective clique since |𝐸 (𝑔𝑖+1 )| = |𝐸 (𝑔𝑖 )| − 𝑑 𝑔𝑖 (𝑣) + 𝑜𝑝𝑡

𝑤𝑤5

Figure 1: An example to illustrate Case 3 in the proof of Lemma 4.2 with 𝑐 = 6 and {𝑤 𝑥 1 , ..., 𝑤 𝑥𝑡 } = {𝑤 1, 𝑤 2, 𝑤 5 } (indicated in blue); we have {𝑤 𝑥 1 +1, ..., 𝑤 𝑥𝑡 +1 } = {𝑤 2, 𝑤 3, 𝑤 6 = 𝑤 0 } (indicated in green).

Based on the above, we have 𝑜𝑖 −1 𝑜𝑖 −1 𝑉 (𝑔𝑖′ ) = 𝑆𝑜𝑝𝑡 ∪ Ψ𝑖 where Ψ𝑖 = 𝑉 (𝑔𝑖′ ) \ 𝑆𝑜𝑝𝑡 .

𝑤𝑤0

𝑜𝑝𝑡

– Case 3: 𝑑 Ψ𝑖 (𝑣𝑜∗𝑖 ) = 2 and 𝑑 Γ𝑜𝑖 −1 (𝑣𝑜∗𝑖 ) = 2. In this case, any 𝑚𝑖𝑛

𝑜𝑖 −1 𝑜𝑖 −1 vertex 𝑣 in Γ𝑚𝑖𝑛 has two non-neighbors in Γ𝑚𝑖𝑛 based on our greedy strategy 2 and is adjacent to all vertices in 𝐶 \ 𝑜𝑖 −1 Γ𝑚𝑖𝑛 based on Definition 4.1. Clearly, there exists a circle 𝑜𝑖 −1 in the complementary graph of 𝑔[Γ𝑚𝑖𝑛 ] that contains 𝑣𝑜∗𝑖 . W.l.o.g., let ⟨𝑤 0, 𝑤 1, ..., 𝑤𝑐 = 𝑤 0 ⟩ (𝑐 ≥ 2) be the circle where vertex 𝑤 𝑗 is not adjacent to 𝑤 𝑗+1 (0 ≤ 𝑗 ≤ 𝑐 − 1) in 𝑔, and let 𝑤 0 = 𝑣𝑜∗𝑖 . Let {𝑤 𝑥 1 , 𝑤 𝑥 2 , ..., 𝑤 𝑥𝑡 } be the vertices in {𝑤 0, ..., 𝑤𝑐 } ∩ Ψ𝑖 , as illustrated in Figure 1. Clearly, 𝑤 0 = 𝑤𝑐 ′ by swapping the is not in {𝑤 𝑥 1 , 𝑤 𝑥 2 , ..., 𝑤 𝑥𝑡 }. We construct 𝑔𝑖+1 6

the total maintenance cost of the bucket structure is 𝑂 (|𝑆 | + |𝐶 |). Therefore, the overall time complexity of IRSolver is dominated by the initialization step and remains 𝑂 (|𝑆 ||𝐶 | + |𝐶 | 2 ).

4.3

Proof. We note that each recursion of BBRes runs in polynomial time 𝑂 (|𝑆 ||𝐶 | + |𝐶 | 2 ), which is dominated by IRSolver (details are discussed in Section 4.2). When |𝑉 (𝑔∗ )| ≥ 𝑘 + 2, we can utilize the diameter-two property, then the size of 𝐺 𝑣𝑖 can be bounded by Δ𝛿 [14] and thus |𝐶 | ≤ Δ𝛿; otherwise, we have |𝐶 | ≤ 𝑛. We then analyze the number of recursions (or branches) and put the details in Appendix A of our technical report [1]. □

BBRes: New Branching Strategy

Motivation. Consider the branching procedure at a branch (𝑔, 𝑆, 𝐶). Recent studies have shown that the performance of the proposed method depends on the pivot selection strategy used during branching. We first briefly revisit the existing pivot selection strategy [14]. Specifically, it selects from 𝐶 the vertex that has at least one nonneighbor in 𝑆 as the pivot 𝑣 𝑝 ; if no such vertex exists, it selects from 𝐶 an arbitrary vertex as the pivot 𝑣 𝑝 . We observe that the existing branching strategy [14] could select those vertices that have at most two non-neighbors in 𝐶 as the pivot. We note that those vertices can be skipped when selecting the pivot, and if no pivot can be chosen from 𝐶, the branch (𝑔, 𝑆, 𝐶) falls in the MissingTwoDeg problem instances and can be solved by IRSolver. Therefore, the existing branching strategy is not suitable for our framework as it will create some redundant branches. Our branching strategy. Motivated by the above, we propose the following branching strategy called BS-three. • BS-three. Given a branch (𝑔, 𝑆, 𝐶), the pivot 𝑣 𝑝 is selected as the vertex in 𝐶 that (1) has at least three non-neighbors in 𝐶 and (2) has at least one non-neighbor in 𝑆; if no such vertex exists, the pivot 𝑣 𝑝 is chosen as an arbitrary vertex in 𝐶 that has at least three non-neighbors in 𝐶. We remark that if BS-three cannot find a pivot in 𝐶, the branch becomes a MissingTwoDeg problem and can be solved by IRSolver. In addition, BS-three cannot be applied to the previous BB framework [13, 14, 19] since they cannot handle the MissingTwoDeg problems (when no pivot can be found in 𝐶).

5

DOUBLE-COLORING UPPER BOUND

The upper bound estimation is a crucial component in algorithms for the maximum 𝑘-defective problem, as it directly impacts the efficiency and effectiveness of the BB search process. Existing stateof-the-art methods typically rely on graph coloring techniques [13, 14, 19]. By assigning colors to vertices in the candidate set, these methods partition the candidate set into several independent sets, thereby facilitating the computation of upper bounds. However, this classic approach makes a simplifying assumption: it treats every pair of vertices in different color classes as if they must be connected by an edge. While this assumption simplifies the analysis, it often leads to loose upper bounds, especially in graphs where the connectivity between color classes is sparse. Recognizing this limitation, we propose to advance upper bound computation by introducing a novel double-coloring strategy in this section. Rather than relying on a single coloring, we assign each vertex a pair of colors, derived from two independent coloring processes. This dual perspective enables us to capture more refined relationships between vertices. For example, if two vertices fall into different color classes in the first coloring but share the same color in the second, we gain additional insight: despite what the first coloring suggests, these vertices actually belong to an independent set under the second coloring. To illustrate, consider the example in Figure 2, which contrasts the granularity of structural information captured by the two schemes. As shown in Figure 2(a), single coloring assigns identical colors to non-adjacent vertices (e.g., the blue nodes), implicitly treating them as a clique and thus identifying only 2 missing edges. In contrast, Figure 2(b) demonstrates that double coloring distinguishes these vertices via unique color pairs, successfully exposing all 4 missing edges (indicated by dashed lines). In the following, we first present the computation of the double-coloring upper bound (Section 5.1) and then prove its correctness (Section 5.2).

Time complexity of BBRes. With the proposed BS-three, our BBRes will generate 𝑂 (𝜆𝑘𝛿Δ ) branches when |𝑉 (𝑔∗ )| ≥ 𝑘 + 1, and generate 𝑂 (𝜆𝑘𝑛 ) branches otherwise in the worst case. Here, 𝛿 is the degeneracy of 𝐺, Δ is the maximum degree of 𝐺, and 𝜆𝑘 is the largest real root of the equation 𝑥 𝑘+4 −2𝑥 𝑘+3 +𝑥 3 −𝑥 +1 = 0 (based on the analytical method in [24]). For example, 𝜆𝑘 = 1.381, 1.705, 1.867 when 𝑘 = 1, 2, 3. Thus, BBRes has the worst-case time complexity of 𝑂 ∗ (𝜆𝑘𝛿Δ ) when |𝑉 (𝑔∗ )| ≥ 𝑘 + 1, and of 𝑂 (𝜆𝑘𝑛 ) otherwise, where 𝑂 ∗ suppresses the polynomials, as summarized in Lemma 4.3. Recall that the state-of-the-art method following Algorithm 1 has the time complexity of 𝑂 ∗ (𝛾𝑘𝑛 ) where 𝛾𝑘 is the largest real root of 𝑥 𝑘+3 − 2𝑥 𝑘+2 + 𝑥 2 − 𝑥 + 1 = 0, e.g., 𝛾𝑘 = 1.466, 1.755, 1.889 for 𝑘 = 1, 2, 3. We remark that 𝜆𝑘 is strictly smaller than 𝛾𝑘 for 𝑘 ≥ 1. A formal proof is provided in Appendix A of our technical report [1]; see the proof of Lemma 4.3. Moreover, for 𝑘 = 1, 3, 5, 10, 15, 20, the corresponding values of 𝛾𝑘 are 1.465, 1.8885, 1.9750, 1.9993, 1.99998, and 1.9999993, while the corresponding values of 𝜆𝑘 are 1.3803, 1.8668, 1.9706, 1.9991, 1.99997, and 1.9999992.

5.1

Double-Coloring Upper Bound Computation

Additional notations. We now leverage the richer structural information revealed by double coloring. Specifically, for each vertex 𝑣 in the candidate set 𝐶, we assign a pair of colors, (𝑐𝑜𝑙 1 (𝑣), 𝑐𝑜𝑙 2 (𝑣)), where 𝑐𝑜𝑙 1 (·) and 𝑐𝑜𝑙 2 (·) are two different vertex colorings. Both colorings respect the graph’s edges: for any edge (𝑢, 𝑣) in 𝐺, we ensure 𝑐𝑜𝑙 1 (𝑢) ≠ 𝑐𝑜𝑙 1 (𝑣) and 𝑐𝑜𝑙 2 (𝑢) ≠ 𝑐𝑜𝑙 2 (𝑣). We refer to each ordered pair (𝑐𝑜𝑙 1 (𝑣), 𝑐𝑜𝑙 2 (𝑣)) as the color pair of 𝑣. The specific procedures for generating these colorings will be introduced later. We further introduce a double-coloring indicator function 𝐼𝐺 (𝑢, 𝑣), which is defined as 1 if two distinct vertices 𝑢 and 𝑣 share the same color in either of the two colorings, and 0 otherwise. In other words, 𝐼𝐺 (𝑢, 𝑣) indicates whether 𝑢 and 𝑣 are placed in the same color class in at least one of the two independently obtained colorings. It is

Lemma 4.3. Given a graph 𝐺 and a integer 𝑘, BBRes runs in 𝑂 (𝑛(Δ𝛿) 2 𝜆𝑘Δ𝛿 ) when the largest 𝑘-defective clique in 𝐺 is of size larger than 𝑘 + 1 (i.e., |𝑉 (𝑔∗ )| ≥ 𝑘 + 2), and runs in 𝑂 (𝑛 2 𝜆𝑘𝑛 ), where 𝛿 is the degeneracy of 𝐺, Δ is the maximum degree of 𝐺, and 𝜆𝑘 is the largest real root of the equation 𝑥 𝑘+4 − 2𝑥 𝑘+3 + 𝑥 3 − 𝑥 + 1 = 0. 7

𝑆

𝑆 𝐶

𝐶

(a) Single coloring

(b) Double coloring

1

1

1

0 0

s

1

1

1

0

t

0

0

0

0

0

t

0

0

0

0

0 s

the second coloring, 𝑐𝑜𝑙 2 (·), is assigned arbitrarily1 , with the additional constraint that no two vertices share the same color pair, i.e., (𝑐𝑜𝑙 1 (𝑢), 𝑐𝑜𝑙 2 (𝑢)) = (𝑐𝑜𝑙 1 (𝑣), 𝑐𝑜𝑙 2 (𝑣)) only if 𝑢 = 𝑣. Based on the assigned colorings, we construct the cost-flow (directed) graph 𝑔𝑐 = (𝑉 𝑐 , 𝐸𝑐 ). First, we define the vertex set 𝑉 𝑐 . Let 𝑉1′ = {𝑐𝑜𝑙 1 (𝑣) | 𝑣 ∈ 𝐶} and 𝑉2′ = {𝑐𝑜𝑙 2 (𝑣) | 𝑣 ∈ 𝐶} be the sets of colors derived from the two coloring processes. The vertex set is then defined as 𝑉 𝑐 = {𝑠} ∪ {𝑡 } ∪ 𝑉1′ ∪ 𝑉2′ . As in Figure 2(c) (with 𝑘 = 2), this vertex set forms a layered topology: 𝑉1′ and 𝑉2′ constitute two distinct layers bridging the source 𝑠 and the sink 𝑡. Next, we construct the edge set 𝐸𝑐 to encode the vertex selection and the 𝑘-defective constraint. The construction rules are as follows: • Source edges: For each vertex 𝑢 ∈ 𝑉1′ , we add 𝑘 +1 parallel edges from 𝑠 to 𝑢, denoted as (𝑠, 𝑢), with capacity 1 and costs 0, 1, . . . , 𝑘, respectively. These edges distribute the allowable missing-edge budget. • Sink edges: Similarly, for each vertex 𝑣 ∈ 𝑉2′ , we add 𝑘 + 1 parallel edges from 𝑣 to 𝑡, with capacity 1 and costs 0, 1, . . . , 𝑘, respectively. • Internal edges: For each vertex 𝑥 ∈ 𝐶 in the original graph, let 𝑢 = 𝑐𝑜𝑙 1 (𝑥) and 𝑣 = 𝑐𝑜𝑙 2 (𝑥). We add a directed edge (𝑢, 𝑣) connecting the two color layers, with capacity 1 and cost 𝑑 𝑆 (𝑥). This edge represents the potential selection of vertex 𝑥. • Reverse edges: For every edge constructed above, we add a corresponding reverse edge with capacity 0 and the negation of the original cost. Given the constructed cost-flow graph instance 𝑔𝑐 = (𝑉 𝑐 , 𝐸𝑐 ), we solve the constrained maximum flow problem [4, 21, 27], which aims to maximize the flow such that the total cost does not exceed 𝑘 − |𝐸 (𝑆)|. The value of the maximum flow obtained from this graph corresponds precisely to the size of the subset 𝐷 ⊆ 𝐶 that can be added to 𝑆 while satisfying the 𝑘-defective constraint. Our double-coloring upper bound, denoted as UB-Double, is then defined as |𝑆 | + |𝐷 |. As an illustration, Figure 2(d) presents the computation result for the running example (where 𝑘 = 2). The algorithm identifies a valid flow of value 3 with a total cost of 2. Since the cost is within the budget, this implies a valid subset size |𝐷 | = 3, yielding a refined upper bound of |𝑆 | + 3 = 4. Furthermore, there exists a direct mapping between flows in 𝑔𝑐 and the subset 𝐷. Specifically, if a unit of flow in the maximum flow solution passes through an edge (𝑢, 𝑣) with 𝑢 ∈ 𝑉1′ and 𝑣 ∈ 𝑉2′ , we include the corresponding vertex in the set 𝐷. To formalize this mapping, let 𝑝 : 𝑣 → (𝑐𝑜𝑙 1 (𝑣), 𝑐𝑜𝑙 2 (𝑣)) denote the correspondence from 𝑔 to 𝑔𝑐 , where 𝑣 ∈ 𝐶 and (𝑐𝑜𝑙 1 (𝑣), 𝑐𝑜𝑙 2 (𝑣)) ∈ 𝐸 (𝑔𝑐 ).

0

0

(c) Cost-flow graph with costs

(d) Calculated constrained max-flow

Figure 2: Comparison of coloring strategies and upper bound computation (𝑘 = 2). (a) Single coloring misses non-edges. (b) Double coloring reveals them via unique color pairs. (c) Cost-flow network with edge costs. (d) Max flow of 3 with cost 2 (flow shown on edges), yielding UB = |𝑆 | + 3.

easy to observe that, for any induced subgraph 𝑔, the quantity 1 Í 2 𝑢,𝑣 ∈𝑉 (𝑔) 𝐼𝑔 (𝑢, 𝑣) provides a lower bound on the number of missÍ ing edges in 𝑔, i.e., 12 𝑢,𝑣 ∈𝑉 (𝑔) 𝐼𝑔 (𝑢, 𝑣) ≤ |𝐸 (𝑔)|, where |𝐸 (𝑔)| is the number of non-edges in 𝑔. This is because 𝐼𝑔 (𝑢, 𝑣) = 1 implies that 𝑢 and 𝑣 are not adjacent in 𝑔, but the converse may not hold. Overview of double-coloring upper-bound computation. Given a branch (𝑔, 𝑆, 𝐶), our goal is to leverage the structural information provided by double coloring to select a subset 𝐷 of the candidate set 𝐶 such that the size of the maximum 𝑘-defective clique 𝑔′ in this branch (i.e., 𝑆 ⊆ 𝑉 (𝑔′ ) ⊆ 𝑆 ∪ 𝐶) is at most |𝐷 | + |𝑆 |. In other words, |𝐷 | + |𝑆 | serves as our double-coloring upper bound, denoted as UB-Double. However, this is a non-trivial task, as incorporating information from two colorings introduces additional dependencies that must be carefully managed. To compute UB-Double, we construct a corresponding cost-flow graph instance based on the current branch (𝑔, 𝑆, 𝐶) and employ the classic constrained maximum flow algorithm [3, 21, 27]. In this setting, the objective is to maximize the flow (which corresponds to the number of vertices added to 𝑆), while ensuring that the total cost (which corresponds to the number of non-edges) does not exceed a threshold, say 𝑘 − |𝐸 (𝑆)|. After obtaining the maximum flow in the cost-flow graph, we show that it corresponds to a subset 𝐷 of the candidate set 𝐶. Our UB-Double is then defined as |𝑆 | + |𝐷 |. In the following, we present our double-coloring upper bound method UB-Double based on the cost-flow graph and constrained maximum flow computation.

5.2

Correctness and Complexity of Our Double-Coloring Upper Bound

We now establish the correctness proof and analyze the time complexity of our double-coloring upper bound UB-Double. Correctness proof. We first establish the correctness of our proposed UB-Double. Specifically, given any branch (𝑔, 𝑆, 𝐶) and its corresponding cost-flow graph instance 𝑔𝑐 , our goal is to show that

Double-coloring upper bound via cost-flow graph. Given a branch (𝑔, 𝑆, 𝐶), we aim to compute a tight upper bound on the size of the maximum 𝑘-defective clique by leveraging the structural information provided by double coloring. To this end, we first assign two colorings to the vertices in 𝐶: the first coloring, 𝑐𝑜𝑙 1 (·), is assigned greedily according to the degeneracy ordering;

1 In our current implementation, the vertices in 𝐶 are processed according to their

current memory order. As shown in Section D of the technical report, this strategy achieves the best overall performance among the tested second-coloring orders. Designing more effective second-coloring orders remains an interesting future work. 8

Table 1: Number of solved instances by the algorithms with a 3-hour limit (best performers are highlighted in bold).

for any 𝑘-defective clique 𝑔′ in this branch (where 𝑆 ⊆ 𝑉 (𝑔′ ) ⊆ 𝑆 ∪ 𝐶), the size of 𝑔′ cannot exceed |𝑆 | + |𝐷 |, where 𝐷 ⊆ 𝐶 is the subset selected by our algorithm. The central idea of our proof is to relate the number of missing edges in the induced subgraph 𝐺 [𝑆 ∪ 𝐷] to the cost of the constrained maximum flow in the cost-flow graph. Specifically, we observe that the total number of missing edges in 𝐺 [𝑆 ∪ 𝐷] is equal Í to the sum of three terms: |𝐸 (𝑆 ∪𝐷)| = |𝐸 (𝑆)|+|𝐸 (𝐷)|+ 𝑢 ∈𝐷 𝑑 𝑆 (𝑢). Our proof proceeds in two main steps: • First, as shown in Lemma 5.1, for any subset 𝐷, the doublecoloring indicator provides a lower bound on the number of Í missing edges within 𝐷, i.e., 12 𝑢,𝑣 ∈𝐷 𝐼𝐺 (𝑢, 𝑣) ≤ |𝐸 (𝐷)|. • Second, as established in Lemma 5.2, the cost 𝑐𝑜𝑠𝑡 (𝑔𝑐 ) computed in the cost-flow graph 𝑔𝑐 exactly matches the sum of the doublecoloring indicator over 𝐷 and the number of missing edges beÍ Í tween 𝑆 and 𝐷, i.e., 𝑐𝑜𝑠𝑡 (𝑔𝑐 ) = 12 𝑢,𝑣 ∈𝐷 𝐼𝐺 (𝑢, 𝑣) + 𝑢 ∈𝐷 𝑑 𝑆 (𝑢). Putting these observations together, we see that if the total cost in the cost-flow graph does not exceed 𝑘 − 𝐸 (𝑆), then the total number of missing edges in any 𝑘-defective clique formed by 𝑆 and 𝐷 is at most 𝑘. This means that any 𝑘-defective clique can be represented as a feasible flow in our construction. Since our constrained maximum flow algorithm finds the largest possible 𝐷 under the cost constraint, the solution |𝑆 | + |𝐷 | serves as a valid upper bound on the size of any 𝑘-defective clique containing 𝑆 in this branch. Thus, our UB-Double produces a correct upper bound. We now provide the detailed proof. We begin by presenting a lemma that follows directly from the definition of the doublecoloring indicator.

𝑘 =1 𝑘 =3 𝑘 =5 𝑘 = 10 𝑘 = 15 𝑘 = 20

BBRes 139 139 139 135 132 129

Real-world graphs kDC2 MDC DnBk 137 138 135 136 136 135 136 131 134 128 127 124 126 121 119 114 113 111

WODC 138 139 139 134 130 127

takes 𝑂 (𝑐𝑘) = 𝑂 (|𝐶 |𝑘) time. Finally, we apply a classical maximum flow algorithm [5, 21, 27] to solve the problem, which runs in 𝑂 (𝑘 |𝐶 | log |𝐶 |) time. Thus, the overall time complexity of UBDouble is 𝑂 (𝑘 |𝐶 | log |𝐶 | + |𝐶 | 2 ). By comparison, computing UBSingle needs 𝑂 (|𝐶 | + |𝐸 (𝑔[𝐶])|) time [13, 14, 19], which is smaller. Nevertheless, in our setting, |𝐶 | is bounded by the graph degeneracy 𝛿, which is typically small on real-world graphs. Hence, computing UB-double remains practically efficient.

6

EXPERIMENTS

In this section, we conduct experiments to evaluate the performance of our proposed algorithm BBRes against four baselines. • kDC2 2 : the existing algorithm proposed in [14]. • MDC 3 : the existing method proposed in [19]. • DnBK 4 : the existing algorithm proposed in [36], augmented with the same Stage II techniques (Algorithm 1) as kDC2 and MDC, for solving the maximum 𝑘-defective clique problem without the size constraint. • WODC 5 : the state-of-the-art method proposed in [30]. We note that prior algorithms, including MADEC+ [16], KDBB [25], KD-Club [31], and kDC [13], run significantly slower than the above baselines proposed recently and thus are omitted for the comparison. All algorithms are implemented in C++, compiled with -O3, and run on a machine with an Intel CPU @ 2.60GHz and 256GB main memory. Following previous studies [14, 19, 36], we choose 𝑘 from {1, 3, 5, 10, 15, 20} and set the time limit as 3 hours (i.e., 10,800s) for a fair comparison. We evaluate the algorithms on a widely adopted collection 6 of 139 real-world graphs [14, 19, 36] containing a total of 5.87 × 107 vertices. Our source code can be found in [1].

Lemma 5.1. Given a graph 𝐺 = (𝑉 , 𝐸) and any subset 𝐷 ⊆ 𝑉 , we Í have 21 𝑢,𝑣 ∈𝐷 𝐼𝐺 (𝑢, 𝑣) ≤ |𝐸 (𝐷)|. We are ready to give the following result, where the complete derivation is provided in Appendix A of our technical report [1]. Lemma 5.2. Given a constructed cost-flow graph 𝑔𝑐 and its constrained maximum flow, there exists a corresponding vertex set 𝐷 in Í Í 𝐶 such that 𝑐𝑜𝑠𝑡 (𝑔𝑐 ) = 12 𝑢,𝑣 ∈𝐷 𝐼𝐺 (𝑢, 𝑣) + 𝑢 ∈𝐷 𝑑 𝑆 (𝑢). Effectiveness of UB-Double over UB-Single. We first briefly review the standard single-coloring-based upper bound, denoted by UB-Single [13, 14, 19]. Given a branch (𝑔, 𝑆, 𝐶), previous methods compute an upper bound by assigning a single coloring 𝑐𝑜𝑙 (·) to the vertices in the candidate set 𝐶 according to the degeneracy ordering. This is exactly the first coloring step used in our double-coloring method UB-Double. The resulting bound is denoted by UB-Single. We further show that our UB-Double is always no larger than the existing single-coloring-based upper bound UB-Single [13, 14, 19], and is therefore always at least as tight.

6.1

Comparison with Baselines

Number of solved instances. Table 1 summarizes the number of instances solved by each algorithm within the 3-hour cutoff. First, we observe a general downward trend in the number of solved instances as 𝑘 increases, confirming the exponential growth in computational complexity for larger 𝑘. Despite this challenge, BBRes consistently demonstrates superior performance, achieving the highest coverage across all settings. Significantly, the performance gap between BBRes and the competitors widens as 𝑘 increases. For example, at 𝑘 = 20, BBRes solves 129 instances, outperforming the runner-up (WODC) by 2 instances and significantly surpassing kDC2 by 15 instances. We attribute this advantage to the effective

Lemma 5.3. Given an instance (𝑔, 𝑆, 𝐶), UB-Double ≤ UB-Single. The proof is provided in Appendix A of our technical report [1]. Time complexity of UB-Double. Compared with the standard single-coloring-based upper bound UB-Single, computing UBDouble incurs additional overhead. Consider a branch (𝑔, 𝑆, 𝐶). UB-Double first colors the vertices in 𝐶 twice: the first coloring requires 𝑂 (|𝐸 (𝑔[𝐶])|) time [10], and the second coloring requires 𝑂 (|𝐶 | × 𝑐) = 𝑂 (|𝐶 | 2 ) time, where 𝑐 is the number of colors for 𝐶 and 𝑐 ≤ |𝐶 |. Constructing the corresponding cost-flow graph

2 https://lijunchang.github.io/kDC-two/ 3 https://github.com/dawhc/MaximumDefectiveClique/ 4 https://github.com/cy-Luo000/Maximum-k-Defective-Clique/ 5 https://github.com/SNUCSE-CTA/WODC/ 6 http://lcs.ios.ac.cn/~caisw/Resource/realworld%20graphs.tar.gz

9

(a) 𝑘 = 1

(b) 𝑘 = 3

(c) 𝑘 = 5

(d) 𝑘 = 10

(e) 𝑘 = 15

(f) 𝑘 = 20

Runtime efficiency on representative benchmarks. We evaluate the runtime performance of BBRes against four baselines, namely kDC2, MDC, DnBk, and WODC, on representative graphs with 𝑘 ∈ {5, 10, 15, 20}. The dataset consists of the 30 largest graphs from the real-world collection, excluding instances where all algorithms exceeded the 3-hour time limit at 𝑘 = 20. Table 2 reports the detailed running times. The results demonstrate that BBRes consistently delivers superior performance across all tested values of 𝑘, except for a few trivial instances. Notably, on the soc-flixster graph with 𝑘 = 20, BBRes achieves a remarkable 53× speedup over the best-performing baseline (WODC, 89.1s vs. 1.7s). In addition, we can observe that BBRes achieves at least a 2× speedup over the best competing method on 26.7%, 20.0%, 40.0%, and 53.3% of the test cases for 𝑘 = 5, 10, 15, and 20, respectively. Furthermore, BBRes exhibits significant scalability and robustness with respect to increasing 𝑘. In contrast to the baselines, whose runtimes often degrade exponentially as 𝑘 grows, BBRes remains highly efficient. For instance, on socfb-A-anon, as 𝑘 increases from 10 to 20, the runtime of BBRes grows moderately from 7.8s to 17.1s. In stark contrast, the competitors suffer from severe performance degradation at 𝑘 = 20: MDC, kDC2, and DnBk require 140.9s, 988.4s, and 1304.3s, respectively. Even the runner-up, WODC, is significantly slower, taking 57.3s, which is more than 3× that of BBRes. These results strongly validate the practical efficiency of our proposed algorithm in handling difficult constraints. Finally, we note that BBRes runs slightly slower than the baselines on some instances in Table 2. This mainly occurs on relatively easy instances where all methods terminate within a fraction of a second. In such cases, the computational overhead of BBRes’s advanced techniques (e.g., UB-Double) may outweigh their pruning benefits.

Figure 3: Number of solved instances with varying time limits

synergy between our diameter-2 partitioning and the proposed double-coloring upper bound. Real-world graphs typically exhibit a “globally sparse, locally dense” topology. While diameter-2 partitioning decomposes the globally sparse structure into smaller sub-instances, these sub-instances often retain high local density. It is in these dense regions that baseline methods falter, as their bounds (e.g., single-coloring) become loose, leading to redundant branches. In contrast, our double-coloring strategy captures finergrained structural conflicts, thereby tightening the bounds and effectively pruning the search space in these dense substructures. We extend our analysis to the time-efficiency trade-off by plotting the number of solved instances against the runtime budget (ranging from 1 second to 3 hours) in Figure 3. Across all tested values of 𝑘, BBRes maintains a dominant position, indicated by its curve consistently lying above those of the competitors (kDC2, MDC, DnBk, and WODC). Two key observations highlight the efficacy of BBRes: First, BBRes excels in rapid convergence. For hard instances where 𝑘 = 20, BBRes quickly solves approximately 90 instances in the first second, whereas the baselines struggle to solve 65. Even with a generous 3-hour limit, BBRes reaches a total of 129 solved instances, surpassing the best baseline (WODC, 127 instances). Second, our method demonstrates superior robustness to problem difficulty. While the performance of baseline algorithms drops sharply as 𝑘 increases (reflecting the exponential growth in search space), BBRes sustains a high completion rate. This suggests that our doublecoloring bound effectively prunes the search space, mitigating the impact of increasing 𝑘.

6.2

Ablation Studies

To rigorously assess the individual contributions of our proposed techniques, we conduct an ablation study by comparing BBRes against two distinct variants. Specifically, we define -FlowUB as the variant that replaces our double-coloring upper bound (Section 5) with a standard single-coloring bound, thereby isolating the impact of our novel bounding strategy. Meanwhile, we define -Branch as the variant that disables our specific branching and early termination strategies (Section 4). We note that -Branch adopts the state-of-the-art branching strategy proposed in [19] for fair comparison, and it differs with MDC mainly in the upper bound. This comparison allows us to quantify the performance gain attributed solely to our optimized branching and early termination strategies. Table 3 details the runtime performance of these methods across 30 representative benchmark graphs. The results consistently demonstrate that the full BBRes algorithm achieves superior performance compared to both variants in the vast majority of cases. To quantify the impact of the double-coloring upper bound, we observe that -FlowUB suffers from significant performance degradation, particularly on large, dense graphs with higher 𝑘. For instance, on soc-lastfm with 𝑘 = 20, the runtime surges from 527.9 seconds (BBRes) to 1441.6 seconds (-FlowUB), representing a nearly 2.7× slowdown. Similarly, on soc-orkut (𝑘 = 20), -FlowUB requires 314.8 seconds compared to 137.4 seconds for BBRes. These results indicate that our double-coloring strategy provides a significantly 10

Table 2: Running time (in seconds) on 30 representative real-world benchmark graphs. ‘-’ indicates timeout. The best performer is highlighted in bold; specifically, if the running time is within 10% of the fastest time, it is considered as the best. Graphs socfb-A-anon soc-orkut socfb-B-anon soc-flixster web-wikipedia2009 tech-as-skitter soc-pokec soc-lastfm soc-youtube-snap ca-hollywood-2009 sc-ldoor soc-digg ca-coauthors-dblp soc-delicious web-it-2004 soc-youtube sc-msdoor ca-MathSciNet ca-dblp-2012 ca-citeseer ca-dblp-2010 sc-pwtk soc-gowalla tech-RL-caida sc-shipsec5 web-arabic-2005 soc-douban sc-shipsec1 web-uk-2005 web-sk-2005

𝑛 3M 2M 2M 2M 1M 1M 1M 1M 1M 1M 952K 770K 540K 536K 509K 495K 415K 332K 317K 227K 226K 217K 196K 190K 179K 163K 154K 140K 129K 121K

𝑚 23M 106M 20M 7M 4M 11M 22M 4M 2M 56M 20M 5M 15M 1M 7M 1M 9M 820K 1M 814K 716K 5M 950K 607K 2M 1M 327K 1M 11M 334K

BBRes 6.513 104.263 10.165 0.521 0.84 0.707 5.996 3.392 0.677 0.856 21.676 25.555 0.24 0.075 0.163 0.418 10.726 0.044 0.061 0.034 0.023 1.679 0.182 0.14 0.176 0.02 0.03 0.14 0.252 0.01

kDC2 6.65 157.448 8.984 4.136 0.783 0.593 4.557 105.634 3.844 0.825 64.183 38.424 0.205 0.068 0.14 1.619 31.332 0.032 0.043 0.026 0.018 2.065 0.219 0.131 0.161 0.022 0.029 0.096 0.213 0.01

𝑘 =5 MDC 19.343 137.127 18.302 2.74 2.083 1.877 11.098 88.744 2.42 3.263 47.185 43.787 0.815 0.437 0.42 1.28 24.22 0.243 0.246 0.175 0.138 3.675 0.314 0.176 0.44 0.12 0.117 0.216 0.472 0.055

DnBk 21.89 390.314 21.135 2.461 1.289 0.982 16.999 104.585 3.009 0.795 1144.44 0.224 0.151 0.4 1.953 1343.813 0.036 0.043 0.029 0.021 420.808 0.241 0.178 0.693 0.023 0.109 0.13 0.65 0.011

WODC 6.645 405.808 6.883 1.189 1.872 1.288 7.88 2.992 1.247 3.36 494.426 47.122 0.839 0.169 6.159 1.123 241.336 0.103 0.108 0.07 0.067 72.627 0.176 0.17 1.665 0.088 0.09 0.337 17.792 0.132

BBRes 7.793 112.963 12.272 0.594 0.954 0.755 6.588 13.906 1.705 0.854 143.497 33.257 0.319 0.113 0.231 1.082 81.904 0.045 0.055 0.03 0.022 5.801 0.357 0.09 0.258 0.02 0.029 0.18 0.304 0.012

kDC2 37.453 576.496 58.884 38.122 0.846 0.702 5.188 2826.062 56.95 0.818 1669.188 177.117 0.245 0.135 0.202 31.709 874.654 0.032 0.045 0.021 0.019 18.982 1.409 0.179 0.307 0.023 0.029 0.169 0.268 0.011

𝑘 = 10 MDC 32.101 188.372 21.368 3.875 2.779 1.972 14.35 2098.176 28.339 3.315 894.263 395.428 0.845 0.417 0.579 16.115 647.598 0.283 0.244 0.156 0.136 12.244 0.406 0.188 0.68 0.119 4318.654 0.624 0.575 0.066

DnBk 48.902 523.604 66.563 8.435 2.551 2.173 17.144 31.979 0.774 1885.92 0.315 0.295 0.704 17.539 2487.434 0.049 0.047 0.027 0.02 589.325 0.489 0.361 1.826 0.024 0.14 0.927 0.839 0.014

WODC 8.919 455.723 7.622 1.871 2.542 1.26 7.634 14.784 3.735 3.35 2290.9 61.119 3.514 0.301 16.653 4.14 1164.13 0.117 0.096 0.07 0.058 136.318 0.352 0.339 2.867 0.088 0.234 1.812 25.944 0.208

BBRes 10.689 129.552 25.553 0.788 0.973 0.886 9.899 64.639 13.467 0.855 361.145 41.287 0.331 0.179 0.237 7.795 199.684 0.051 0.071 0.025 0.023 32.956 0.748 0.122 0.884 0.026 7.509 0.691 0.316 0.01

kDC2 289.987 8249.529 1737.898 1199.894 0.891 1.8 9.381 1341.397 0.814 3532.593 8896.453 0.258 0.391 0.214 758.326 1897.013 0.038 0.047 0.021 0.025 1544.762 67.38 1.873 6.494 0.027 39.523 0.721 0.285 0.011

𝑘 = 15 MDC 52.543 45.803 19.231 2.889 2.058 18.949 921.233 3.364 3093.435 852.619 0.874 0.587 0.603 2263.7 0.309 0.275 0.172 0.147 180.301 0.831 1.075 2.288 0.123 1.677 0.595 0.056

DnBk 305.076 1353.479 778.94 84.602 49.022 3.624 101.537 938.395 0.782 0.381 0.686 0.709 509.977 0.045 0.053 0.031 0.023 1010.477 1.937 1.282 15.372 0.028 7.028 3.125 1.002 0.015

WODC 18.556 573.453 22.41 10.753 2.726 1.6 9.261 70.443 37.626 3.174 4353.16 266.135 5.966 0.474 16.907 41.827 2211.78 0.148 0.185 0.084 0.103 787.769 0.793 0.833 10.85 0.145 15.019 5.079 26.144 0.213

BBRes 17.136 146.826 19.994 1.677 1.66 1.04 13.476 529.874 193.191 0.867 4114.424 64.569 0.334 0.232 0.243 102.463 2360.887 0.098 0.062 0.029 0.025 133.684 6.406 0.294 2.344 0.026 51.643 1.622 0.331 0.016

kDC2 988.404 8811.373 1.574 21.869 58.022 0.835 0.269 4.095 0.225 0.08 0.037 0.028 0.019 1655.622 2115.989 14.532 14.16 0.024 6.267 0.302 0.012

𝑘 = 20 MDC 140.895 378.424 294.896 3.085 2.804 23.248 3.401 9918.25 0.893 1.537 0.607 0.675 0.236 0.152 0.142 451.792 3.487 6.433 0.121 28.64 0.616 0.067

DnBk 1304.348 1785.488 16.88 10.765 430.095 0.795 0.453 2.157 0.736 0.444 0.054 0.035 0.028 1657.136 17.82 10.435 107.36 0.024 34.677 1.088 0.016

WODC 57.337 892.649 79.273 89.086 2.596 2.498 24.827 493.475 497.69 3.15 3046.37 5.978 1.037 16.821 674.757 0.772 0.215 0.125 0.133 1771.97 2.709 2.249 25.538 0.146 5.31 17.956 26.286 0.217

Table 3: Running time (in seconds) comparison of BBRes and its variants on 30 benchmark graphs. Graphs socfb-A-anon soc-orkut socfb-B-anon soc-flixster web-wikipedia2009 tech-as-skitter soc-pokec soc-lastfm soc-youtube-snap ca-hollywood-2009 sc-ldoor soc-digg ca-coauthors-dblp soc-delicious web-it-2004 soc-youtube sc-msdoor ca-MathSciNet ca-dblp-2012 ca-citeseer ca-dblp-2010 sc-pwtk soc-gowalla tech-RL-caida sc-shipsec5 web-arabic-2005 soc-douban sc-shipsec1 web-uk-2005 web-sk-2005

𝑛 3M 2M 2M 2M 1M 1M 1M 1M 1M 1M 952K 770K 540K 536K 509K 495K 415K 332K 317K 227K 226K 217K 196K 190K 179K 163K 154K 140K 129K 121K

𝑚 23M 106M 20M 7M 4M 11M 22M 4M 2M 56M 20M 5M 15M 1M 7M 1M 9M 820K 1M 814K 716K 5M 950K 607K 2M 1M 327K 1M 11M 334K

BBRes 6.510 104.263 10.165 0.521 0.840 0.707 5.996 3.392 0.677 0.856 21.676 25.555 0.240 0.075 0.163 0.418 10.726 0.044 0.061 0.034 0.023 1.679 0.182 0.140 0.176 0.020 0.030 0.140 0.252 0.010

𝑘 =5 -FlowUB -Branch 6.570 5.990 105.429 97.701 10.030 10.589 0.990 0.538 0.842 0.837 0.618 0.719 6.228 5.890 13.851 3.475 1.588 0.671 0.860 0.849 23.890 21.619 29.010 25.245 0.228 0.234 0.087 0.083 0.158 0.166 0.795 0.404 11.456 11.095 0.047 0.042 0.051 0.051 0.027 0.032 0.022 0.025 1.684 1.593 0.231 0.178 0.132 0.109 0.177 0.174 0.019 0.024 0.031 0.032 0.110 0.134 0.246 0.255 0.010 0.013

Color 3.170 184.354 10.925 5.636 0.905 0.562 5.457 117.415 4.083 0.912 46.003 39.611 0.236 0.088 0.356 1.678 22.242 0.046 0.059 0.034 0.028 4.598 0.304 0.168 0.186 0.021 0.043 0.070 0.679 0.014

BBRes 7.790 112.963 12.272 0.594 0.954 0.755 6.588 13.906 1.705 0.854 143.497 33.257 0.319 0.113 0.231 1.082 81.904 0.045 0.055 0.030 0.022 5.801 0.357 0.090 0.258 0.020 0.029 0.180 0.304 0.012

𝑘 = 10 -FlowUB -Branch 7.960 7.170 122.661 105.647 12.914 13.226 1.670 0.616 0.985 0.971 0.660 0.802 6.962 6.500 63.229 17.442 6.757 1.699 0.849 0.846 125.057 173.210 41.776 33.006 0.303 0.314 0.098 0.091 0.220 0.227 3.806 1.069 66.695 103.154 0.058 0.064 0.050 0.054 0.032 0.037 0.022 0.027 4.756 7.262 0.312 0.273 0.103 0.087 0.245 0.257 0.026 0.019 0.030 0.038 0.180 0.222 0.296 0.306 0.012 0.011

Color 32.120 867.689 61.008 52.162 1.187 0.639 6.650 2923.227 60.676 0.888 1869.012 210.258 0.398 0.107 0.731 33.877 988.826 0.058 0.070 0.043 0.026 14.455 1.709 0.199 0.275 0.020 0.045 0.262 0.872 0.016

BBRes 10.689 129.552 25.553 0.788 0.973 0.886 9.899 64.639 13.467 0.855 361.145 41.287 0.331 0.179 0.237 7.795 199.684 0.051 0.071 0.025 0.023 32.956 0.748 0.122 0.884 0.026 7.509 0.691 0.316 0.010

𝑘 = 15 -FlowUB -Branch 11.151 9.888 175.951 119.789 22.276 22.370 4.255 1.056 0.972 1.013 0.797 0.901 10.418 9.763 237.258 145.164 50.892 15.248 0.856 0.851 377.997 1573.838 65.069 41.346 0.322 0.327 0.149 0.148 0.229 0.238 30.482 8.435 198.704 985.887 0.052 0.063 0.058 0.056 0.027 0.036 0.025 0.028 56.107 37.546 1.821 0.755 0.199 0.150 1.134 0.886 0.025 0.025 7.214 7.268 0.533 0.682 0.310 0.320 0.010 0.014

Color 261.946 1680.934 1393.552 1.217 1.395 12.063 1407.650 0.879 4111.127 9546.118 0.460 0.365 0.571 781.582 2179.247 0.060 0.079 0.033 0.028 1462.455 71.508 1.866 6.599 0.025 27.132 0.628 0.888 0.016

BBRes 17.136 146.826 19.994 1.677 1.660 1.040 13.476 529.874 193.191 0.867 4114.424 64.569 0.334 0.232 0.243 102.463 2360.887 0.098 0.062 0.029 0.025 133.684 6.406 0.294 2.344 0.026 51.643 1.622 0.331 0.016

𝑘 = 20 -FlowUB -Branch 18.292 16.070 314.638 153.571 22.902 20.760 24.123 11.537 1.564 1.685 1.132 1.069 14.673 12.953 1439.551 834.218 464.716 222.509 0.845 0.866 3976.471 287.370 107.880 0.325 0.326 0.283 0.227 0.238 0.248 258.912 114.663 2094.814 0.118 0.107 0.055 0.055 0.036 0.040 0.024 0.032 176.029 119.104 19.199 8.889 0.499 0.294 2.583 2.514 0.031 0.030 49.694 50.022 1.325 1.293 0.322 0.332 0.011 0.012

Color 921.318 8305.512 1.831 19.536 63.050 0.882 0.477 3.991 0.587 0.143 0.086 0.036 0.024 1619.158 2162.518 15.755 14.227 0.040 6.719 0.876 0.014

early, it still lags behind the full BBRes. For example, on sc-msdoor at 𝑘 = 15, -Branch is approximately 1.5× slower than BBRes (292.3 seconds vs. 197.8 seconds). On the other hand, on more challenging instances such as sc-msdoor and sc-ldoor, -FlowUB often outperforms -Branch, suggesting that the improved branching strategy is particularly effective in reducing the search complexity. This confirms that our tailored branching strategy effectively reduces the search effort and facilitates faster convergence. We also note that the efficiency of BBRes is closely related to the value of 𝜆𝑘 . As shown in Table 2, the running time of BBRes generally increases with 𝑘, which is consistent with the complexity 𝑂 ∗ (𝜆𝑘𝑛 ) and the fact that 𝜆𝑘 increases as 𝑘 grows. At the same time, the theoretical gap

tighter bound than the single-coloring approach, effectively pruning massive branches of the search tree that standard bounds fail to detect. Regarding the impact of the branching strategy, the comparison between BBRes and -Branch highlights the efficiency of our branching and termination rules. Although -Branch is often competitive with BBRes, this does not imply that the performance gain of BBRes mainly comes from the tighter upper bound alone. Indeed, -FlowUB is also competitive with BBRes on several challenging instances, indicating that the branching strategy also makes a substantial contribution. While -Branch often performs better than -FlowUB on many easier instances, suggesting that the tighter upper bound is particularly effective at pruning unpromising branches 11

𝑛 ) time, while kDC further reduces the comMADEC+ runs in 𝑂 ∗ (𝛽 2𝑘 ∗ 𝑛 plexity to 𝑂 (𝛽𝑘 ), where 𝛽𝑖 is the largest real root of the equation 𝑥 𝑖+3 − 2𝑥 𝑖+2 + 1 = 0. The kDC2 algorithm, proposed by Chang [14], runs in 𝑂 ∗ (𝛽𝑘𝑛−1 ) time, and the MDC algorithm, proposed by Dai et al. [19], runs in 𝑂 ∗ (𝛾𝑘𝑛 ) time, where 𝛾𝑖 is the largest real root of the equation 𝑥 𝑖+3 − 2𝑥 𝑖+2 + 𝑥 2 − 𝑥 + 1 = 0. Importantly, we note that 𝛾𝑘 < 𝛽𝑘 −1 for 𝑘 ≥ 2. Distinct from the above BB frameworks, DnBK and WODC employ alternative frameworks to reduce the exponential base. DnBK reduces the problem of finding the largest 𝑘-defective clique to 𝑂 (𝑛(Δ𝛿) 2𝑘 ) instances of finding the maximum clique and runs in 𝑂 (𝑛(Δ𝛿) 2𝑘 𝛼𝑐𝑛 ) time, where 𝛼𝑐 is the base factor in the time complexity of the maximum clique algorithm. While theoretical bounds suggest 𝛼𝑐 = 1.2 [51], practical implementations rely on solvers like those in [12], where 𝛼𝑐 ≈ 1.33 7 . Similarly, Jang et al. [30] introduced WODC, which decomposes the branching process into a maximal clique enumeration stage and a 𝑘-defective clique constraint verification stage. Consequently, WODC has the worstcase time complexity of 𝑂 (𝑛(Δ𝛿)𝑘 𝛼𝑒𝛿 ), where 𝛼𝑒 = 31/3 ≈ 1.44 represents the optimal base for maximal clique enumeration. While DnBK and WODC achieve smaller exponential bases, they introduce significant overhead factors of (Δ𝛿) Θ(𝑘 ) . These factors become prohibitive when 𝑘 is not a small constant, limiting their scalability in general settings. In this paper, our BBRes achieves the time complexity of 𝑂 ∗ (𝜆𝑘𝑛 ), where 𝜆𝑘 is the largest real root of the equation 𝑥 𝑘+4 − 2𝑥 𝑘+3 + 𝑥 3 − 𝑥 + 1 = 0 and 𝜆𝑘 is strictly smaller than 𝛾𝑘 for 𝑘 ≥ 1. Thus, our proposed BBRes achieves better theoretical complexity for general 𝑘 (noting that the complexity of DnBK and WODC depends exponentially on 𝑘), and empirically outperforms the SOTA methods, namely, kDC2, MDC, DnBK, and WODC, in Section 6. In addition, the problem of enumerating all maximal 𝑘-defective cliques has been investigated. The Pivot+ algorithm [20] achieves 𝑂 ∗ (𝛾𝑘𝑛 ) time. However, Pivot+ is typically less effective for identifying the maximum 𝑘-defective clique in practice due to limited pruning techniques. Furthermore, the concept of defective cliques has been extended to bipartite graphs [18, 47].

2−𝜆𝑘 (or 𝛾𝑘 −𝜆𝑘 ) becomes smaller as 𝑘 increases, indicating that the advantage over the naive 𝑂 ∗ (2𝑛 ) bound and the previous 𝑂 ∗ (𝛾𝑘𝑛 ) bound gradually narrows. Nevertheless, even when 𝜆𝑘 is very close to 2 (e.g., at 𝑘 = 20), the improvement can still be meaningful on very large graphs. For example, for a graph with 107 vertices, we 7 107 ≈ 54 and 𝛾 107 /𝜆 107 ≈ 2. In summary, BBRes consishave 210 /𝜆20 20 20 tently achieves the best overall performance by combining tight bounding with effective branching, suggesting that the two techniques are complementary in practice even though their relative contributions vary across instances.

6.3

Tests on Dense and Synthetic Graphs

While the previous sections focused on sparse real-world graphs, the maximum 𝑘-defective clique problem is theoretically most challenging on dense graphs. To stress-test BBRes under these extreme conditions, we extended our evaluation to the DIMACS benchmark (notoriously hard dense instances) and LFR synthetic graphs [33] (controlled density analysis). Due to space constraints, the detailed DIMACS results and the complete density sensitivity analysis on LFR graphs are deferred to Appendix C of the technical report [1]. The results on DIMACS graphs show that BBRes remains highly competitive on dense benchmark instances and continues to outperform the baselines on most tested values of 𝑘. On the LFR graphs, we examine how graph density affects the relative behavior of -Branch and -FlowUB. We observe that as the graph density increases, the runtime gap between these two variants gradually narrows. This suggests that on denser graphs, the proposed branching strategy becomes increasingly relevant, and its contribution becomes more comparable to that of the flow-based upper bound. At the same time, BBRes, which combines both components, consistently achieves the best overall performance, with a maximum speedup of up to 174× over the ablation variants. These results indicate that neither component alone is sufficient to fully capture the benefit on dense graphs; instead, their combination is important for maintaining strong performance in such challenging settings.

8 7

CONCLUSION

In this paper, we proposed a new branch-and-bound method BBRes for finding the maximum 𝑘-defective clique. BBRes has the worstcase time complexity of 𝑂 ∗ (𝜆𝑘𝑛 ), which improves upon the stateof-the-art time complexity of 𝑂 ∗ (𝛾𝑘𝑛 ), where 𝜆𝑘 < 𝛾𝑘 . To boost the practical efficiency, we also proposed a tighter upper bound. Finally, extensive experiments demonstrate that BBRes outperforms stateof-the-art algorithms by several orders of magnitude in practice. In the future, we intend to investigate parallelization strategies for BBRes to handle massive graphs.

RELATED WORK

The concept of the 𝑘-defective clique was originally formalized by [52]. Early exact methods for the maximum 𝑘-defective clique problem, such as those in [28, 29, 45], suffered from limited scalability and were practical only on small graphs. The first algorithm capable of handling large graphs was MADEC+ [16]. Building on this foundation, KDBB [25] and KD-Club [31] improved empirical performance by combining preprocessing with several (upperbound-based) pruning rules. Recently, several algorithms, including kDC [13], MDC [19], kDC2 [14], DnBK [36], and WODC [30], have introduced new branching strategies, thereby improving the theoretical time complexity of the problem. Furthermore, these methods introduce novel reduction rules and upper bound-based pruning rules to effectively eliminate unnecessary branches and vertices during the branch-and-bound search phase. In addition, they incorporate new heuristics to efficiently compute an initial solution in the preprocessing phase. We note that the most recent methods, namely kDC2 [14], MDC [19], DnBK [36], and WODC [30] are included in our experiments for comparison. From a theoretical perspective,

7 As [12] omits the time complexity analysis for the maximum clique algorithm MC-BRB, we provide it here. MC-BRB recursively removes vertices with at most three nonneighbors in the candidate set. Thus, MC-BRB only branches on vertices with at least four non-neighbors in the candidate set. This leads to the characteristic equation 𝑥 5 − 𝑥 4 − 1 = 0, yielding a branching factor of 𝛼𝑐 ≈ 1.33.

12

REFERENCES

[30] Jihoon Jang, Yehyun Nam, Kunsoo Park, and Hyunjoon Kim. 2025. Efficient defective clique enumeration and search with worst-case optimal search space. Proc. ACM SIGMOD Int. Conf. Manage. Data (SIGMOD) 3, 6 (2025), 1–28. [31] Mingming Jin, Jiongzhi Zheng, and Kun He. 2024. KD-Club: An efficient exact algorithm with new coloring-based upper bound for the maximum 𝑘 -defective clique problem. In Proceedings of AAAI. 20735–20742. [32] Jalal Khalil, Da Yan, Guimu Guo, and Lyuheng Yuan. 2022. Parallel mining of large maximal quasi-cliques. The VLDB Journal 31, 4 (2022), 649–674. [33] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 78, 4 (2008), 046110. [34] Kingsly Leung and Christopher Leckie. 2005. Unsupervised anomaly detection in network intrusion detection using clusters. In Proceedings of the Australasian Conference on Computer Science. 333–342. [35] John M. Lewis and Mihalis Yannakakis. 1980. The node-deletion problem for hereditary properties is NP-complete. J. Comput. System Sci. 20, 2 (1980), 219– 230. [36] Chunyu Luo, Yi Zhou, Zhengren Wang, and Mingyu Xiao. 2024. A faster branching algorithm for the maximum 𝑘 -defective clique problem. In Proceedings of the European Conference on Artificial Intelligence (ECAI). 4132–4139. [37] Panos M Pardalos and Jue Xue. 1994. The maximum clique problem. Journal of global Optimization 4, 3 (1994), 301–328. [38] Bharath Pattabiraman, Md Mostofa Ali Patwary, Assefaw H Gebremedhin, Weikeng Liao, and Alok Choudhary. 2015. Fast algorithms for the maximum clique problem on massive graphs with applications to overlapping community detection. Internet Mathematics 11, 4-5 (2015), 421–448. [39] Jeffrey Pattillo, Nataly Youssef, and Sergiy Butenko. 2013. On clique relaxation models in network analysis. European Journal of Operational Research 226, 1 (2013), 9–18. [40] Jian Pei, Daxin Jiang, and Aidong Zhang. 2005. On mining cross-graph quasicliques. In Proceedings of KDD. 228–238. [41] Pablo San Segundo, Alvaro Lopez, and Panos M Pardalos. 2016. A new exact maximum clique algorithm for large and massive sparse graphs. Computers & Operations Research 66 (2016), 81–94. [42] Stephen B. Seidman and Brian L Foster. 1978. A graph-theoretic generalization of the clique concept. Journal of Mathematical Sociology 6, 1 (1978), 139–154. [43] Etsuji Tomita. 2017. Efficient algorithms for finding maximum and maximal cliques and their applications. In International workshop on algorithms and computation. Springer, 3–15. [44] Etsuji Tomita, Yoichi Sutani, Takanori Higashi, Shinya Takahashi, and Mitsuo Wakatsuki. 2010. A simple and faster branch-and-bound algorithm for finding a maximum clique. In International Workshop on Algorithms and Computation. Springer, 191–203. [45] Svyatoslav Trukhanov, Chitra Balasubramaniam, Balabhaskar Balasundaram, and Sergiy Butenko. 2013. Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Computational Optimization and Applications 56, 1 (2013), 113–130. [46] Jianxin Wang, Min Li, Youping Deng, and Yi Pan. 2010. Recent advances in clustering methods for protein interaction networks. BMC Genomics 11, Suppl 3 (2010), S10. [47] Zhiyi Wang, Lijun Chang, and Jeffrey Xu Yu. 2025. Identifying maximum defective bicliques in large bipartite graphs. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 3710–3723. [48] Zhengren Wang, Yi Zhou, Chunyu Luo, and Mingyu Xiao. 2023. A fast maximum 𝑘 -plex algorithm parameterized by the degeneracy gap. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 5648–5656. [49] Hongbo Xia, Kaiqiang Yu, Shengxin Liu, Cheng Long, and Xun Zhou. 2025. Maximum degree-based quasi-clique search via an iterative framework. In Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining (SIGKDD). 3285–3296. [50] Mingyu Xiao, Weibo Lin, Yuanshun Dai, and Yifeng Zeng. 2017. A fast algorithm to compute maximum 𝑘 -plexes in social network analysis. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 919–925. [51] Mingyu Xiao and Hiroshi Nagamochi. 2017. Exact algorithms for maximum independent set. Information and Computation 255 (2017), 126–146. [52] Haiyuan Yu, Alberto Paccanaro, Valery Trifonov, and Mark Gerstein. 2006. Predicting interactions in protein networks by completing defective cliques. Bioinformatics 22, 7 (2006), 823–829. [53] Kaiqiang Yu and Cheng Long. 2021. Graph mining meets fake news detection. In Data Science for Fake News: Surveys and Perspectives. Springer, 169–189. [54] Kaiqiang Yu and Cheng Long. 2023. Fast maximal quasi-clique enumeration: A pruning and branching co-design approach. Proc. ACM SIGMOD Int. Conf. Manage. Data (SIGMOD) 1, 3 (2023), 1–26. [55] Zhiping Zeng, Jianyong Wang, Lizhu Zhou, and George Karypis. 2006. Coherent closed quasi-clique discovery from large dense graph databases. In Proc. of KDD (SIGKDD). 797–802. [56] Yi Zhou, Shan Hu, Mingyu Xiao, and Zhang-Hua Fu. 2021. Improving maximum 𝑘 -plex solver via second-order reduction and graph color bounding. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 12453–12460.

[1] Technical Report and Source Code. https://github.com/Thaumaturge2020/ BBRes/. [2] Mohiuddin Ahmed, Abdun Naser Mahmood, and Md Rafiqul Islam. 2016. A survey of anomaly detection techniques in financial domain. Future Generation Computer Systems 55 (2016), 278–288. [3] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall. [4] Ravindra K Ahuja and James B Orlin. 1995. A capacity scaling algorithm for the constrained maximum flow problem. Networks 25, 2 (1995), 89–98. [5] Ravindra K Ahujia, Thomas L Magnanti, and James B Orlin. 1993. Network flows: Theory, algorithms and applications. New Jersey: Rentice-Hall 3 (1993). [6] Vladimir Batagelj and Matjaž Zaveršnik. 2003. An 𝑂 (𝑚) algorithm for cores decomposition of networks. CoRR cs.DS/0310049 (2003). [7] Punam Bedi and Chhavi Sharma. 2016. Community detection in social networks. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 6, 3 (2016), 115–135. [8] Nina Berry, Teresa Ko, Tim Moy, Julienne Smrcka, Jessica Turnley, and Ben Wu. 2004. Emergent clique formation in terrorist recruitment. In Proceedings of the AAAI Workshop on Agent Organizations: Theory and Practice. 1198–1208. [9] Jean-Marie Bourjolly, Gilbert Laporte, and Gilles Pesant. 2002. An exact algorithm for the maximum 𝑘 -club problem in an undirected graph. European Journal of Operational Research 138, 1 (2002), 21–28. [10] Daniel Brélaz. 1979. New methods to color the vertices of a graph. Commun. ACM 22, 4 (1979), 251–256. [11] Randy Carraghan and Panos M Pardalos. 1990. An exact algorithm for the maximum clique problem. Operations Research Letters 9, 6 (1990), 375–382. [12] Lijun Chang. 2020. Efficient maximum clique computation an enumeration over large sparse graphs. The VLDB Journal 29, 5 (2020), 999–1022. [13] Lijun Chang. 2023. Efficient maximum 𝑘 -defective clique computation with improved time complexity. Proceedings of the ACM on Management of Data (SIGMOD) 1, 3 (2023), 1–26. [14] Lijun Chang. 2024. Maximum defective clique computation: Improved time complexities and practical performance. Proceedings of the VLDB Endowment 18, 2 (2024), 200–212. [15] Lijun Chang, Mouyi Xu, and Darren Strash. 2022. Efficient maximum 𝑘 -plex computation over large sparse graphs. Proceedings of the VLDB Endowment 16, 2 (2022), 127–139. [16] Xiaoyu Chen, Yi Zhou, Jin-Kao Hao, and Mingyu Xiao. 2021. Computing maximum 𝑘 -defective cliques in massive graphs. Computers & Operations Research 127 (2021), 105131. [17] James Cheng, Yiping Ke, Ada Wai-Chee Fu, Jeffrey Xu Yu, and Linhong Zhu. 2011. Finding maximal cliques in massive networks. ACM Transactions on Database Systems (TODS) 36, 4 (2011), 1–34. [18] Donghang Cui, Ronghua Li, Qiangqiang Dai, Hongchao Qin, and Guoren Wang. 2025. On the efficient discovery of maximum 𝑘 -defective biclique. arXiv preprint arXiv:2506.16121 (2025). [19] Qiangqiang Dai, Ronghua Li, Donghang Cui, and Guoren Wang. 2024. Theoretically and practically efficient maximum defective clique search. Proceedings of the ACM on Management of Data (SIGMOD) 2, 4 (2024), 1–27. [20] Qiangqiang Dai, Rong-Hua Li, Meihao Liao, and Guoren Wang. 2023. Maximal defective clique enumeration. Proc. ACM SIGMOD Int. Conf. Manage. Data (SIGMOD) 1, 1 (2023), 1–26. [21] Efim A Dinic. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Doklady 11 (1970), 1277–1280. [22] David Eppstein, Maarten Löffler, and Darren Strash. 2013. Listing all maximal cliques in large sparse real-world graphs. Journal of Experimental Algorithmics (JEA) 18 (2013), 3–1. [23] Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, and Xuemin Lin. 2020. A survey of community search over big graphs. The VLDB Journal 29 (2020), 353–392. [24] Fedor V Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer Science & Business Media. [25] Jian Gao, Zhenghang Xu, Ruizhi Li, and Minghao Yin. 2022. An exact algorithm with new upper bounds for the maximum 𝑘 -defective clique problem in massive sparse graphs. In Proceedings of AAAI. 10174–10183. [26] Shuohao Gao, Kaiqiang Yu, Shengxin Liu, and Cheng Long. 2024. Maximum 𝑘 -plex search: An alternated reduction-and-bound method. Proceedings of the VLDB Endowment 18, 2 (2024), 363–376. [27] Andrew Goldberg and Robert Tarjan. 1987. Solving minimum-cost flow problems by successive approximation. In Proceedings of STOC. 7–18. [28] Timo Gschwind, Stefan Irnich, Fabio Furini, and Roberto Wolfler Calvo. 2021. A branch-and-price framework for decomposing graphs into relaxed cliques. INFORMS Journal on Computing 33, 3 (2021), 1070–1090. [29] Timo Gschwind, Stefan Irnich, and Isabel Podlinski. 2018. Maximum weight relaxed cliques and Russian Doll Search revisited. Discrete Applied Mathematics 234 (2018), 131–138. 13

A OMITTED PROOFS A.1 Proof of Lemma 4.3

exists. This implies that every pivot 𝑝𝑖 (0 ≤ 𝑖 < 𝑞) along the path contributes at least one non-edge to 𝑆𝑖+1 . Therefore, the number of missing edges grows monotonically: |𝐸 (𝑆𝑖+1 )| ≥ |𝐸 (𝑆𝑖 )| + 1. Summing over the path, we obtain |𝐸 (𝑆𝑞 )| ≥ |𝐸 (𝑆 0 )| + 𝑞. Given the feasibility constraint that 𝑆𝑞 is a 𝑘-defective clique (otherwise 𝐵𝑞 would not be a valid branch), i.e., |𝐸 (𝑆𝑞 )| ≤ 𝑘, it follows that 𝑞 ≤ 𝑘 − |𝐸 (𝑆 0 )| ≤ 𝑘. Next, we assume that such a node 𝐵𝑥 exists. We claim that the accumulated number of missing edges in 𝑆𝑥 satisfies |𝐸 (𝑆𝑥 )| > 𝑥. Recall that 𝐵𝑞 is defined as the first node where pruning occurs (i.e., |𝐶𝑞 | ≤ |𝐶𝑞−1 | − 2). This implies that for any node 𝐵𝑖 prior to 𝐵𝑞 (specifically 0 ≤ 𝑖 < 𝑥), no pruning occurred. Consequently, for each pivot 𝑝𝑖 ∈ {𝑝 0, . . . , 𝑝𝑥 −1 }, its nonneighbors from 𝐶𝑖 (at least three) must have been added to 𝑆𝑥 . Since 𝐵𝑥 is a node where 𝑝𝑥 is fully connected to 𝑆𝑥 , the candidate set 𝐶𝑥 is cleared of any non-neighbors of 𝑆𝑥 . Therefore, all non-neighbors of the set {𝑝 0, . . . , 𝑝𝑥 −1 } must reside within 𝑆𝑥 . In the complement graph of 𝑆𝑥 , every vertex in {𝑝 0, . . . , 𝑝𝑥 −1 } has a degree of at least 3. By the Handshaking Lemma, the total number of missing edges is at least the sum of degrees divided by 2, which implies that |𝐸 (𝑆𝑥 )| ≥ 3𝑥2 = 1.5𝑥. For 𝑥 > 0, we have 1.5𝑥 ≥ 𝑥 + 0.5 > 𝑥. We now address the boundary case 𝑥 = 0. If |𝐸 (𝑆 0 )| > 0, the claim |𝐸 (𝑆𝑥 )| > 𝑥 holds trivially since |𝐸 (𝑆 0 )| ≥ 1 > 0. If |𝐸 (𝑆 0 )| = 0 (i.e., 𝑆 0 is a clique), we show that 𝑥 cannot be 0. Note that 𝑆 0 contains an inherited pivot 𝑝 ′ with at least three non-neighbors in 𝐶 0 . If 𝑥 = 0, 𝐵 0 would be the fully connected node 𝐵𝑥 , implying that 𝐶 0 contains no non-neighbors of 𝑆 0 (including 𝑝 ′ ), which is a contradiction. Thus, if 𝑆 0 is a clique, we must have 𝑥 ≥ 1, ensuring the bound holds. Combining this with the monotonicity of missing edges after 𝐵𝑥 , we derive |𝐸 (𝑆𝑞 )| ≥ |𝐸 (𝑆𝑥 )| + (𝑞 −𝑥 − 1) ≥ (𝑥 + 1) +𝑞 −𝑥 − 1 = 𝑞. Given the feasibility constraint |𝐸 (𝑆𝑞 )| ≤ 𝑘, it follows that 𝑞 ≤ 𝑘. Let ℓ (𝐵 0 ) denote the number of leaf nodes rooted at node 𝐵 0 with non-empty 𝑆 0 . We then prove that ℓ (𝐵 0 ) ≤ 𝜆𝑘|𝐶0 | by induction. For the base case where 𝐵 0 is a leaf node, w.l.o.g., we let 𝐶 0 be empty since the corresponding branch can be solved directly. We thus have ℓ (𝐵 0 ) = 1 ≤ 𝜆𝑘|𝐶0 | . For a non-leaf node 𝐵 0 , we consider the path (𝐵 0, 𝐵 1, ..., 𝐵𝑞 ) and trivially have ℓ (𝐵 0 ) = ℓ (𝐵𝑞 ) + ℓ (𝐵𝑞+1 ) + .... + ℓ (𝐵 2𝑞 ), where 𝐵𝑞+𝑖 (1 ≤ 𝑖 ≤ 𝑞) is the right child of node 𝐵𝑖 −1 (See Figure 4). We have:

Proof of Lemma 4.3. We note that each recursion of BBRes runs in polynomial time 𝑂 (|𝐶 | 2 ), which is dominated by computing the upper bound and conducting the reductions (details are discussed in Section 5). When the size of the maximum 𝑘-defective clique |𝑉 (𝑔∗ )| ≥ 𝑘 + 2, we can utilize the diameter-two property, where the size of 𝐺 𝑣𝑖 can be bounded by Δ𝛿 [14], implying |𝐶 | ≤ Δ𝛿; otherwise, we have |𝐶 | ≤ 𝑛. Below, we analyze the number of recursions (or branches). We analyze the branching process based on the recursion tree T illustrated in Figure 4. Specifically, T is a binary tree where each node 𝐵𝑖 represents a state (𝑔𝑖 , 𝑆𝑖 , 𝐶𝑖 ). Recall that our branching strategy, BS-three, prioritizes selecting a pivot 𝑝𝑖 that has at least one non-neighbor in the current partial set 𝑆𝑖 . Based on this, the left child of 𝐵𝑖 is generated by adding 𝑝𝑖 to 𝑆𝑖 (i.e., 𝑆𝑖+1 ← 𝑆𝑖 ∪ {𝑝𝑖 }), while the right child corresponds to the branch where 𝑝𝑖 is excluded from 𝐶𝑖 . We focus our analysis on the leftmost path (𝐵 0, 𝐵 1, . . . , 𝐵𝑞 ), formed by recursively traversing the left children. We initially restrict our analysis to the scenario where 𝑆 0 is non-empty, deferring the discussion of the case where 𝑆 0 = ∅ to the end of the proof. We define the endpoint 𝐵𝑞 as either a leaf node or the first node along this path satisfying |𝐶𝑞 | ≤ |𝐶𝑞−1 | − 2. This definition implies that, in the transition to 𝐵𝑞 , either 1) at least one additional vertex (besides the pivot) is pruned from 𝐶𝑞−1 due to constraint violations (i.e., inability to form a 𝑘-defective clique with 𝑆𝑞 ); or 2) the remaining instance becomes tractable (i.e., it has fewer than three non-neighbors in 𝐶𝑞−1 after removing 𝑝𝑞−1 ), allowing IRSolver to directly obtain the final solution (i.e., terminate the branch). We first analyze the depth of this leftmost path and prove that: 𝑞 ≤ 𝑘.

(8)

To prove this, let 𝐵𝑥 (0 ≤ 𝑥 ≤ 𝑞) denote the last node on the path such that the pivot 𝑝𝑥 is fully connected to 𝑆𝑥 (i.e., 𝑝𝑥 introduces no missing edges). First, consider the case where no such node

𝐵0 −𝑝 0

+𝑝 0

𝐵𝑞+1

𝐵1 −𝑝 1

+𝑝 1

We note that when 𝑞 = 𝑘, ℓ (𝐵 0 ) reaches the largest number of leaf nodes, which corresponds to the worst case (we will discuss other cases 𝑞 < 𝑘 later). In addition, when 𝑞 = 𝑘, we note that |𝐸 (𝑆𝑘 )| = 𝑘 based on the above discussion of 𝑞 ≤ 𝑘. Therefore, we have:

𝐵𝑞+2

𝐵2 −𝑝 2

···

𝐵𝑞−1 +𝑝𝑞−1

(1) 𝑞 ≤ 𝑘 based on the above discussion; (2) |𝐶𝑞 | ≤ |𝐶𝑞−1 | − 2 ≤ |𝐶 0 | − 𝑞 − 1 based on the definition of 𝐵𝑞 ; (3) |𝐶𝑞+𝑖 | ≤ |𝐶𝑖 −1 | − 1 ≤ |𝐶 0 | − 𝑖 for 1 ≤ 𝑖 ≤ 𝑞, based on the branching relationship between the parent node 𝐵𝑖 −1 and its children 𝐵𝑖 and 𝐵𝑞+𝑖 .

𝐵𝑞+3 −𝑝𝑞−1

|𝐶𝑘 | ≤ |𝐶𝑘 −1 | − 4 ≤ |𝐶 0 | − 𝑘 − 3. 𝐵𝑞

(9)

𝐵 2𝑞

This is because 𝑝𝑘 −1 has three non-neighbors in 𝐶𝑘 −1 and those non-neighbors can be pruned since each of them cannot form a

Figure 4: Branching Tree in the Proof of Lemma 4.3. 14

Hence, 𝜆𝑘 → 2. By the same argument, one can show that 𝛾𝑘 is also monotonically increasing and converges to 2. Finally, we have 𝛾𝑘 − 𝜆𝑘 → 0 as 𝑘 → ∞, since both sequences converge to 2: lim𝑘→∞ (𝛾𝑘 −𝜆𝑘 ) = lim𝑘→∞ 𝛾𝑘 −lim𝑘→∞ 𝜆𝑘 = 2−2 = 0. We do not claim that the sequence (𝛾𝑘 − 𝜆𝑘 ) is monotone; rather, our formal result is that this gap vanishes asymptotically. □

𝑘-defective clique with 𝑆𝑘 . We thus have: ℓ (𝐵 0 )

ℓ (𝐵𝑞 ) + ℓ (𝐵𝑞+1 ) + .... + ℓ (𝐵 2𝑞 )

(10)

≤

ℓ (𝐵𝑘 ) + ℓ (𝐵𝑘+1 ) + .... + ℓ (𝐵 2𝑘 )

(11)

≤

𝜆𝑘|𝐶0 | −𝑘 −3 + 𝜆𝑘|𝐶0 | −1 + ... + 𝜆𝑘|𝐶0 | −𝑘 ,

(12)

=

where the inequality of 𝜆𝑘|𝐶0 | −𝑘 −3 +𝜆𝑘|𝐶0 | −1 +...+𝜆𝑘|𝐶0 | −𝑘 ≤ 𝜆𝑘|𝐶0 | holds if 𝜆𝑘 is the largest real root of the equation 𝑥 𝑘+4 −2𝑥 𝑘+3 +𝑥 3 −𝑥 +1 = 0. When 𝑞 < 𝑘, the recurrence becomes: ℓ (𝐵 0 )

=

ℓ (𝐵𝑞 ) + ℓ (𝐵𝑞+1 ) + .... + ℓ (𝐵 2𝑞 )

(13)

≤

′|𝐶 | −𝑞−1 ′|𝐶 | −𝑞 𝜆𝑘 0 + 𝜆𝑘′|𝐶0 | −1 + ... + 𝜆𝑘 0 ,

(14)

A.2

where 𝜆𝑞′ is the largest real root of the equation 𝑥 𝑞+2 − 2𝑥 𝑞+1 + 1 = 0. Since 𝜆𝑞′ demonstrably smaller than 𝜆𝑘 for 𝑞 < 𝑘, we adopt 𝜆𝑘 as our worst-case time complexity factor. In addition, we consider a general branch 𝐵 0 without the constraint 𝑆 0 ≠ ∅. Similar to the proof of Lemma 4.3 in [14], we can prove that the number of leaf nodes satisfies ℓ (𝐵 0 ) ≤ 𝜆𝑘|𝐶0 | , where |𝐶 0 | = |𝑉 (𝑔0 )|. If the size of the maximum 𝑘-defective clique is at least 𝑘 + 2, we can apply the diameter-two property to bound the initial candidate set by |𝐶 0 | ≤ Δ𝛿 [14], yielding a time complexity of 𝑂 ∗ (𝜆𝑘Δ𝛿 ). Otherwise, we trivially have |𝐶 0 | ≤ 𝑛, yielding 𝑂 ∗ (𝜆𝑘𝑛 ). Finally, we show that 𝜆𝑘 < 𝛾𝑘 for all 𝑘 ≥ 1. Recall that 𝜆𝑘 is the largest real root of 𝑥 𝑘+4 − 2𝑥 𝑘+3 + 𝑥 3 − 𝑥 + 1 = 0, and 𝛾𝑘 is the largest real root of 𝑥 𝑘+3 − 2𝑥 𝑘+2 + 𝑥 2 − 𝑥 + 1 = 0. Since both 𝜆𝑘 and 𝛾𝑘 are greater than 1, we can rewrite these equations as Í Í 1 = 𝑘𝑖=1 𝜆𝑘−𝑖 + 𝜆𝑘− (𝑘+3) and 1 = 𝑘𝑖=1 𝛾𝑘−𝑖 + 𝛾𝑘− (𝑘+2) . Define 𝑓 (𝑥) = Í𝑘 −𝑖 − (𝑘+3) . For 𝑥 > 1, 𝑓 (𝑥) is strictly decreasing. Moreover, 𝑖=1 𝑥 + 𝑥 Í by the above reformulation, we have 𝑓 (𝜆𝑘 ) = 𝑘𝑖=1 𝜆𝑘−𝑖 +𝜆𝑘− (𝑘+3) = 1. For 𝛾𝑘 , we have 𝑓 (𝛾𝑘 ) =

𝑘 ∑︁

Now, we analyze the cost 𝑐𝑜𝑠𝑡 (𝑔𝑐 ) associated with the constrained maximum flow in 𝑔𝑐 , which corresponds to the sum of the costs of all flow-carrying edges. We partition the total cost as 𝑐𝑜𝑠𝑡 (𝑔𝑐 ) = 𝑐𝑜𝑠𝑡 (𝐸𝑐1 ) +𝑐𝑜𝑠𝑡 (𝐸𝑐2 ) +𝑐𝑜𝑠𝑡 (𝐸𝑐3 ), where 𝐸𝑐1 denotes the edges between the source 𝑠 and the first color class 𝑉1′ , 𝐸𝑐2 denotes the edges between the second color class 𝑉2′ and the sink 𝑡, and 𝐸𝑐3 denotes the edges between 𝑉1′ and 𝑉2′ in 𝑔𝑐 . First, we have

𝛾𝑘−𝑖 + 𝛾𝑘− (𝑘+3)

𝑖=1

=

𝑘 ∑︁

Proof of Lemma 5.2

Proof of Lemma 5.2. We first show that there is a one-to-one correspondence between the selected flow edges in the constrained maximum flow of 𝑔𝑐 and the set 𝐷. Recall that each vertex 𝑣 ∈ 𝐶 in 𝑔 corresponds to an edge (𝑐𝑜𝑙 1 (𝑣), 𝑐𝑜𝑙 2 (𝑣)) ∈ 𝐸 (𝑔𝑐 ) via the mapping 𝑝 : 𝑣 ↦→ (𝑐𝑜𝑙 1 (𝑣), 𝑐𝑜𝑙 2 (𝑣)). The capacity of each edge between partitions 𝑉1′ and 𝑉2′ is set to 1, so in the maximum flow, each such edge either carries 1 unit of flow (selected) or 0 (not selected). Define 𝐸𝑐ans as the set of edges with flow value 1; this set corresponds to a subset 𝐷 of 𝐶, with |𝐸𝑐ans | = 𝑓 𝑙𝑜𝑤 (𝑔𝑐 ). Let 𝑓out (𝑣) and 𝑓in (𝑣) be the outgoing and incoming flow at vertex 𝑣 in 𝑔𝑐 . Since flow is conserved at each vertex except for 𝑠 and 𝑡, we have 𝑓in (𝑣) = 𝑓out (𝑣). Thus, Í Í |𝐸𝑐ans | = 𝑢 ∈𝑉 ′ 𝑓out (𝑢) = 𝑢 ∈𝑉 ′ 𝑓in (𝑢) = 𝑓out (𝑠) = 𝑓 𝑙𝑜𝑤 (𝑔𝑐 ). This 1 1 establishes the mapping between the selected flow edges in the constrained maximum flow and the set 𝐷.

! 𝛾𝑘−𝑖 + 𝛾𝑘− (𝑘+2)

− 𝛾𝑘− (𝑘+2) + 𝛾𝑘− (𝑘+3)

𝑖=1

= 1 − 𝛾𝑘− (𝑘+2) − 𝛾𝑘− (𝑘+3)

< 1.

𝑐𝑜𝑠𝑡 (𝐸𝑐3 ) =

𝑒 ∈𝐸𝑐ans

Hence, 𝑓 (𝛾𝑘 ) < 𝑓 (𝜆𝑘 ). Since 𝑓 is strictly decreasing on 𝑥 > 1, it follows that 𝛾𝑘 > 𝜆𝑘 , i.e., 𝜆𝑘 < 𝛾𝑘 . Remark. We now show that both 𝜆𝑘 and 𝛾𝑘 increase monotonically with 𝑘 and converge to 2. We first show this for 𝜆𝑘 . Define 𝑓𝑘 (𝑥) = 𝑥 𝑘+4 − 2𝑥 𝑘+3 + 𝑥 3 − 𝑥 + 1. By definition of 𝜆𝑘 , 𝑓𝑘 (𝜆𝑘 ) = 0 and 𝑓𝑘+1 (𝜆𝑘+1 ) = 0, where 𝜆𝑘 , 𝜆𝑘+1 ∈ (1, 2). Moreover, 𝑓𝑘+1 (𝑥) − 𝑓𝑘 (𝑥) = 𝑥 𝑘+3 (𝑥 − 2) (𝑥 − 1). Hence, for any 𝑥 ∈ (1, 2), we have 𝑓𝑘+1 (𝑥) − 𝑓𝑘 (𝑥) < 0, and in particular, 𝑓𝑘+1 (𝜆𝑘 ) < 𝑓𝑘 (𝜆𝑘 ) = 0. Since 𝑓𝑘+1 (2) = 7 > 0 and 𝑓𝑘+1 (𝑥) is continuous, the intermediate value theorem implies that 𝑓𝑘+1 has a root in (𝜆𝑘 , 2). Therefore, 𝜆𝑘 < 𝜆𝑘+1 < 2. Thus, (𝜆𝑘 ) is monotonically increasing and bounded above by 2. To show that 𝜆𝑘 → 2, we rewrite 𝑓𝑘 (𝜆𝑘 ) = 0 as 2 − 𝜆𝑘 =

𝜆𝑘3 −𝜆𝑘 +1

∑︁

𝑐𝑜𝑠𝑡 (𝑒) =

∑︁ 𝑒 ∈𝐸𝑐ans

𝑑 𝑆 (𝑝 −1 (𝑒)) =

∑︁

𝑑 𝑆 (𝑢),

𝑢 ∈𝐷

where the second equality follows the construction of 𝑔𝑐 and the mapping function 𝑝, and the last equality follows from the correspondence between 𝐸𝑐ans and 𝐷. Then, we consider 𝑐𝑜𝑠𝑡 (𝐸𝑐1 ) + 𝑐𝑜𝑠𝑡 (𝐸𝑐2 ). For each vertex 𝑣 in 𝑉1′ , the flow is 𝑓in (𝑣) which implies that there are 𝑓in (𝑣) selected edges in the maximum flow between 𝑠 and 𝑣. By our construction of 𝑔𝑐 and the constrained maximum flow, the 𝑓in (𝑣) edges with minimum cost, i.e., those corresponding to {0, 1, . . . , 𝑓in (𝑣) − 1}, will be selected. The same observation applies to each vertex 𝑣 in 𝑉2′ . Thus, we have Í Í 𝑓in (𝑣) −1 Í Í 𝑓out (𝑣) −1 𝑐𝑜𝑠𝑡 (𝐸𝑐1 ) = 𝑣 ∈𝑉 ′ 𝑖=0 𝑖 and 𝑐𝑜𝑠𝑡 (𝐸𝑐2 ) = 𝑣 ∈𝑉 ′ 𝑖=0 𝑖.

.

𝜆𝑘𝑘+3 3 Since 1 < 𝜆𝑘 < 2, we have 1 < 𝜆𝑘 − 𝜆𝑘 + 1 < 7. Also, since (𝜆𝑘 ) 7 is increasing, 𝜆𝑘 ≥ 𝜆1 > 1 for all 𝑘. Thus, 0 ≤ 2 − 𝜆𝑘 ≤ 𝑘+3 → 0. 𝜆1

1

15

2

Subsequently, we can derive the following: (𝑣) −1 ∑︁ 𝑓in∑︁ 𝑣 ∈𝑉1′

=

𝑖=0

(𝑣) −1 ∑︁ 𝑓out∑︁

𝑖+

𝑣 ∈𝑉2′

𝑣0

𝑣1

𝑆𝑜𝑝𝑡

𝑣5

𝑣0

𝑣4

𝑖=0

𝑣4

𝑣5

𝑣3

1 © ∑︁ 2 ª 1 © ∑︁ 2 ª 𝑓in (𝑣) − 𝑓in (𝑣) ® + ­ 𝑓out (𝑣) − 𝑓out (𝑣) ® ­ 2 2 ′ ′ ¬ ¬ «𝑣 ∈𝑉1 «𝑣 ∈𝑉2

𝑣2

𝑣3

𝑣2

𝐶𝑡𝑒𝑚𝑝

𝑆𝑜𝑝𝑡

𝐶𝑡𝑒𝑚𝑝

(a) Select 𝑣3 (Strategy 2).

=

𝑣1

𝑖

ª ∑︁ ∑︁ ∑︁ 1 ©­ ∑︁ ∑︁ ® 1− 1® ­ ® 2 ­ ′ 𝑝 ∈𝐷 𝑞 ∈𝐷 𝑣 ∈𝑉1 𝑣 ∈𝑉1′ 𝑝 ∈𝐷 col1 (𝑝 )=𝑣 col1 (𝑞)=𝑣 col1 (𝑝 )=𝑣 ¬ «

𝑣0

(b) Add 𝑣5 .

𝑣1 𝑣0 𝑣5

𝑣1 𝑣5

𝑣4

𝑣4 ª ∑︁ ∑︁ ∑︁ 1 ©­ ∑︁ ∑︁ ® 1− 1® + ­ ® 2 ­ ′ 𝑝 ∈𝐷 ′ 𝑞 ∈𝐷 𝑝 ∈𝐷 𝑣 ∈𝑉2 𝑣 ∈𝑉2 col2 (𝑝 )=𝑣 col2 (𝑞)=𝑣 col2 (𝑝 )=𝑣 ¬ «

𝑣3

𝑣2

𝑣3

𝑆𝑜𝑝𝑡

𝐶𝑡𝑒𝑚𝑝

𝑣2 𝐶𝑡𝑒𝑚𝑝 𝑆𝑜𝑝𝑡

(c) Add 𝑣2 .

∑︁ ª 1 © ∑︁ ∑︁ [col1 (𝑝) = col1 (𝑞)] − 1® ­ 2 𝑝 ∈𝐷 𝑞 ∈𝐷 𝑝 ∈𝐷 ¬ « ∑︁ ª 1 © ∑︁ ∑︁ + ­ [col2 (𝑝) = col2 (𝑞)] − 1® 2 𝑝 ∈𝐷 𝑞 ∈𝐷 𝑝 ∈𝐷 « ¬ ∑︁ ∑︁ ∑︁ ª 1© [col1 (𝑝) = col1 (𝑞)] + [col2 (𝑝) = col2 (𝑞)] − 2 1® = ­ 2 𝑝 ∈𝐷 𝑞 ∈𝐷 𝑝 ∈𝐷 ¬ « 1 ∑︁ 𝐼𝐺 (𝑢, 𝑣), = 2 𝑢,𝑣 ∈𝐷 =

(d) Termination.

Figure 5: Execution trace of IRSolver with 𝑘 = 1. Dark and light gray regions denote 𝑆𝑜𝑝𝑡 and 𝐶𝑡𝑒𝑚𝑝 , respectively. The algorithm resolves a tie using Greedy Strategy 2 in (a), sequentially adds unique candidates in (b)-(c), and terminates in (d) as adding 𝑣 1 violates the 𝑘-defective constraint. Table 4: Number of DIMACS instances solved by the algorithms with a 3-hour limit. 𝑘 =1 𝑘 =3 𝑘 =5 𝑘 = 10 𝑘 = 15 𝑘 = 20

where the second equality follows from the fact that 𝑓in (𝑣) = Í 𝑝 ∈𝐷 and col1 (𝑝 )=𝑣 1, and the last equality follows directly from the definition of the double-coloring indicator. Combining the above, we have:

BBRes 45 43 40 33 24 22

DIMACS graphs kDC2 MDC DnBk 37 42 44 23 31 19 19 24 17 14 18 16 12 14 13 11 14 12

WODC 44 41 37 33 23 16

𝑐𝑜𝑠𝑡 (𝑔𝑐 ) = 𝑐𝑜𝑠𝑡 (𝐸𝑐1 ) + 𝑐𝑜𝑠𝑡 (𝐸𝑐2 ) + 𝑐𝑜𝑠𝑡 (𝐸𝑐3 ) (𝑐 ) −1 ∑︁ 𝑓in∑︁

=

𝑐 ∈𝑉1′

=

𝑖=0

1 ∑︁ ∑︁

𝑖+

(𝑐 ) −1 ∑︁ 𝑓out∑︁ 𝑐 ∈𝑉2′

𝐼𝐺 (𝑢, 𝑣) +

2 𝑢 ∈𝐷 𝑣 ∈𝐷

𝑖=0

∑︁

Í

∑︁

𝑖+

𝑢 ∈𝑉 (ℎ) 𝑑 𝑆 (𝑢), while the violation value used by UB-Double is Í Í 𝑉 𝑖𝑜 double (ℎ) = 21 𝑢,𝑣 ∈𝑉 (ℎ) 𝐼 double (𝑢, 𝑣) + 𝑢 ∈𝑉 (ℎ) 𝑑 𝑆 (𝑢). Thus, ∑︁ 1 ∑︁ double 𝐼 (𝑢, 𝑣) + 𝑑 𝑆 (𝑢) 𝑉 𝑖𝑜 double (ℎ) = 2 𝑢,𝑣 ∈𝑉 (ℎ) 𝑢 ∈𝑉 (ℎ) ∑︁ 1 ∑︁ single ≥ 𝐼 (𝑢, 𝑣) + 𝑑 𝑆 (𝑢) 2

𝑐𝑜𝑠𝑡 (𝑒)

𝑒 ∈𝐸𝑐ans

𝑑 𝑆 (𝑢).

𝑢 ∈𝐷

This completes the proof of Lemma 5.2.

□

𝑢,𝑣 ∈𝑉 (ℎ)

A.3

𝑢 ∈𝑉 (ℎ)

= 𝑉 𝑖𝑜 single (ℎ).

Proof of Lemma 5.3

Now let Hsingle = {ℎ | 𝑉 𝑖𝑜 single (ℎ) ≤ 𝑘} and Hdouble = {ℎ | 𝑉 𝑖𝑜 double (ℎ) ≤ 𝑘 }. Since 𝑉 𝑖𝑜 double (ℎ) ≥ 𝑉 𝑖𝑜 single (ℎ) for every ℎ, we have Hdouble ⊆ Hsingle . Hence,

Proof of Lemma 5.3. Let ℎ be an arbitrary candidate subgraph considered in the upper-bound computation. For two distinct vertices 𝑢, 𝑣 ∈ 𝑉 (ℎ), define ( 1, if 𝑐𝑜𝑙 1 (𝑢) = 𝑐𝑜𝑙 1 (𝑣), single 𝐼 (𝑢, 𝑣) = 0, otherwise,

UB-Double =

max |𝑉 (ℎ)| ≤ max |𝑉 (ℎ)| = UB-Single.

ℎ∈ Hdouble

ℎ∈ Hsingle

Therefore, UB-Double is always at least as tight as UB-Single.

□

and ( 𝐼

double

(𝑢, 𝑣) =

1, 0,

if 𝑐𝑜𝑙 1 (𝑢) = 𝑐𝑜𝑙 1 (𝑣) or 𝑐𝑜𝑙 2 (𝑢) = 𝑐𝑜𝑙 2 (𝑣), otherwise.

B

OMITTED EXAMPLE

Example of IRSolver. Figure 5 demonstrates IRSolver on a MissingTwoDeg instance with 𝑘 = 1, initialized with 𝑆𝑜𝑝𝑡 = {𝑣 0 }. In Figure 5(a), the candidate set is Γ𝑚𝑖𝑛 = {𝑣 1, 𝑣 3, 𝑣 5 }. Since 𝑑 𝐶𝑡𝑒𝑚𝑝 (𝑣) = 2 for all candidates, Greedy Strategy 2 (Equation (3)) is triggered,

By definition, for every distinct pair 𝑢, 𝑣 ∈ 𝑉 (ℎ), 𝐼 double (𝑢, 𝑣) ≥ 𝐼 single (𝑢, 𝑣). We next define the violation value. The violation value Í used by UB-Single for ℎ is 𝑉 𝑖𝑜 single (ℎ) = 12 𝑢,𝑣 ∈𝑉 (ℎ) 𝐼 single (𝑢, 𝑣) + 16

Table 5: Running time (in seconds) on 10 representative DIMACS benchmark graphs. The best performer is highlighted in bold; specifically, if the running time is within 10% of the fastest time, it is considered as the best. Graphs c-fat500-2 c-fat500-5 c-fat500-1 c-fat500-10 san400-0-5-1 MANN-a27 hamming8-2 san200-0-7-1 c-fat200-2 c-fat200-5

𝑛 500 500 500 500 400 378 256 200 200 200

𝑚 9K 23K 4K 46K 39K 70K 31K 13K 3K 8K

BBRes 0.001 0.004 0.0 0.022 56.024 2262.145 0.601 14.743 0.005 0.003

kDC2 0.002 0.011 0.0 0.055 2070.312 1827.654 2509.822 0.001 0.005

𝑘 =5 MDC 0.005 0.014 0.003 0.035 2632.115 3057.384 787.899 72.747 0.002 0.005

DnBk 0.003 0.008 0.002 0.028 205.319 0.001 0.002

WODC 0.083 0.397 0.029 1.206 9.666 111.738 0.917 0.028 0.146

BBRes 0.001 0.009 0.006 0.029 93.256 2319.961 17.051 74.559 0.006 0.004

kDC2 0.004 0.023 0.005 0.117 0.002 0.015

𝑘 = 10 MDC 0.008 0.023 0.007 0.056 7391.9 1323.845 0.002 0.008

DnBk 0.006 0.014 0.023 0.074 1202.407 0.002 0.005

WODC 0.084 0.383 0.056 1.722 6707.4 1328.32 13.874 0.037 0.204

BBRes 0.01 0.011 0.009 0.029 95.123 2265.974 339.576 83.843 0.005 0.006

kDC2 0.046 0.034 0.007 0.18 0.015 0.016

𝑘 = 15 MDC 0.045 0.032 0.017 0.116 0.025 0.013

DnBk 0.145 0.025 0.024 0.093 0.036 0.006

WODC 0.388 0.577 0.071 1.858 5638.29 237.672 0.089 0.259

BBRes 0.045 0.015 1.196 0.047 460.396 3280.755 2109.191 101.182 0.015 0.008

kDC2 0.096 0.043 6.744 0.242 0.035 0.027

𝑘 = 20 MDC 0.072 0.044 11.956 0.134 0.021 0.016

DnBk 0.339 0.028 220.672 0.098 0.086 0.01

selecting 𝑣 3 for its minimum 𝑑 Γ𝑚𝑖𝑛 . Subsequently, unique candidates 𝑣 5 and 𝑣 2 are directly added to 𝑆𝑜𝑝𝑡 in Figure 5(b)-(c). The process terminates in Figure 5(d) as adding 𝑣 1 violates the 𝑘-defective constraint, yielding 𝐺 [𝑆𝑜𝑝𝑡 ] as the solution.

C

ADDITIONAL EXPERIMENTS ON DENSE AND SYNTHETIC GRAPHS

While the experimental results in the main text demonstrate the superior efficiency of BBRes on large-scale real-world graphs (which are typically sparse), the maximum 𝑘-defective clique problem is theoretically most challenging on dense graphs due to the exponential explosion of the search space. To rigorously stress-test our algorithm under these extreme conditions and to verify the effectiveness of our pruning strategy in high-density environments, we extend our evaluation to two complementary datasets:

(a) 𝑘 = 5

• DIMACS Benchmarks8 : A standard collection comprising 78 dense graphs. These instances serve as a stress test for raw performance on notoriously hard combinatorial problems. • LFR Synthetic Graphs: Generated via the LFR benchmark [33] with 𝑛 = 5, 000. By systematically varying the graph density from 0.004 to 0.04, these graphs enable a fine-grained sensitivity analysis of the algorithms to varying graph densities. (b) 𝑘 = 15

Detailed performance on DIMACS benchmarks. Table 4 presents the aggregate number of solved instances. In particular, the results confirm that BBRes maintains its dominance even in high-density environments. As summarized in Table 4, BBRes consistently outperforms state-of-the-art baselines across all tested values of 𝑘. The performance gap becomes particularly pronounced for larger 𝑘; for instance, at 𝑘 = 20, BBRes solves 22 instances, whereas kDC2 and DnBk only solve 11 and 12, respectively, marking a nearly 2× improvement in solvability. Table 5 provides a granular breakdown of the running times on 10 representative DIMACS graphs. These detailed statistics offer a deeper insight into the performance gaps between BBRes and the baselines, particularly on hard instances. The results in Table 5 reveal that BBRes achieves orders-of-magnitude speedups. Taking the hamming8-2 graph as an example, for 𝑘 ∈ {5, 10, 15}, BBRes finishes in 0.6s, 17.1s, and 339.6s, respectively. In stark contrast, kDC2, MDC, and DnBk require over 700s even for the easier case of 𝑘 = 5 and fail to terminate within the 3-hour cutoff (10,800s) for larger 𝑘. WODC also struggles, taking 111.7s for 𝑘 = 5 (186× slower than BBRes) and timing out for 𝑘 ≥ 10. We attribute this efficiency

Figure 6: Runtime analysis on LFR synthetic graphs with varying densities. The results illustrate the scalability of BBRes compared to its variants as graph density increases (𝑘 = 5 and 𝑘 = 15).

to the synergy between our diameter-2 partitioning and the doublecoloring upper bound, which effectively prunes the search space in the dense clusters characteristic of DIMACS graphs. Impact of graph density. To explicitly isolate the correlation between graph density and our pruning efficiency, we evaluate BBRes and its ablation variants (-Branch and -FlowUB) on the LFR synthetic datasets. Figure 6 plots the runtime against varying graph densities for 𝑘 = 5 and 𝑘 = 15. The results clearly demonstrate that as density increases, the performance advantage of BBRes becomes increasingly pronounced. Specifically, while BBRes outperforms its variants across the board, the relative speedup ratio grows substantially with density. For instance, at 𝑘 = 5 (Figure 6(a)), on the graph with a density of 0.012, -Branch and -FlowUB are 1.3× and 4.1× slower than BBRes, respectively. However, at a higher density of

8 https://networkrepository.com/dimacs.php

17

WODC 0.514 0.661 1.282 2.201 0.22 0.319

0.032, these slowdown factors escalate to approximately 73× and 174×. This empirical evidence confirms that our double-coloring upper bound is particularly effective in handling high-density regions, where simpler bounds (such as those used in -FlowUB) become loose and ineffective.

D

is often the strongest alternative. A possible explanation is that peel_rev, which reverses the initial degeneracy-based order, tends to produce a second coloring that is structurally different from the first one, and can therefore help expose additional conflicting pairs. However, on the most challenging instances, the strategy in BBRes still shows a clear advantage. For example, on sc-msdoor with 𝑘 = 15, BBRes finishes in 202.63 seconds, compared with 246.285 seconds for peel_rev; on sc-ldoor with 𝑘 = 15, BBRes runs in 365.331 seconds, compared with 442.794 seconds for peel_rev. Interestingly, the second-coloring strategy used in BBRes does not rely on an explicit structural heuristic. Instead, it follows the current storage order of candidate vertices, which is dynamically changed by the recursive branch-and-bound process. Empirically, this dynamic ordering appears to produce a favorable level of diversity between the two colorings, leading to better pruning performance than both strictly deterministic variants and the purely random ordering on many hard instances. However, we do not have a formal theoretical explanation for why this strategy performs best. Understanding the structural properties of effective secondcoloring orders remains an interesting direction for future work.

EFFECT OF SECOND-COLORING STRATEGIES ON UB-DOUBLE

To further evaluate the design of the second coloring phase in UB-Double, we conduct supplementary experiments using several alternative orderings for the second coloring, including random, S_ord, S_rev, peel_ord, and peel_rev. Table 6 reports the detailed running times. Here, BBRes denotes the default strategy used in our algorithm, which processes the vertices in 𝐶 according to their current memory order. random randomly permutes the vertices in 𝐶 before the second coloring. S_ord orders the vertices increasingly by the number of non-neighbors they have in 𝑆, while S_rev uses the reverse order. Finally, peel_ord follows the degeneracy order, and peel_rev uses the reverse degeneracy order. Overall, the default strategy used in BBRes achieves the best performance on the majority of the tested instances, while peel_rev

18

Table 6: Detailed runtime comparison for coloring sequences Graph ca-MathSciNet ca-citeseer ca-coauthors-dblp ca-dblp-2010 ca-dblp-2012 ca-hollywood-2009 sc-ldoor sc-msdoor sc-pwtk sc-shipsec1 sc-shipsec5 soc-delicious soc-digg soc-douban soc-flixster soc-gowalla soc-lastfm soc-orkut soc-pokec soc-youtube soc-youtube-snap socfb-A-anon socfb-B-anon tech-RL-caida tech-as-skitter web-arabic-2005 web-it-2004 web-sk-2005 web-uk-2005 web-wikipedia2009

BBRes 0.054 0.029 0.241 0.026 0.063 0.900 21.403 10.693 1.603 0.107 0.168 0.081 26.293 0.039 0.557 0.236 3.398 88.773 5.949 0.454 0.693 6.059 10.832 0.112 0.726 0.021 0.164 0.010 0.254 0.876

random 0.060 0.035 0.258 0.031 0.057 0.913 24.028 11.747 1.686 0.113 0.183 0.087 29.616 0.040 0.651 0.189 5.137 97.033 7.890 0.575 0.791 6.477 11.558 0.138 0.763 0.025 0.170 0.010 0.259 0.968

𝑘 =5 S_ord S_rev 0.049 0.059 0.034 0.031 0.246 0.242 0.031 0.031 0.053 0.065 0.871 0.856 21.417 24.961 10.637 12.662 1.654 1.668 0.113 0.139 0.175 0.183 0.103 0.086 28.104 27.454 0.031 0.031 0.640 0.599 0.233 0.237 5.496 3.678 107.130 104.046 6.655 6.191 0.482 0.555 0.784 0.724 5.806 5.873 11.309 10.390 0.138 0.140 0.738 0.720 0.024 0.021 0.166 0.169 0.012 0.013 0.257 0.253 0.943 0.879

peel_ord 0.045 0.028 0.238 0.027 0.048 0.853 21.812 10.995 1.667 0.111 0.184 0.084 29.653 0.032 0.706 0.183 5.461 105.480 6.131 0.522 0.776 6.825 10.069 0.110 0.762 0.025 0.167 0.010 0.263 0.884

peel_rev 0.063 0.034 0.241 0.029 0.058 0.901 24.997 12.581 1.735 0.135 0.199 0.084 27.522 0.040 0.652 0.185 3.938 102.082 6.191 0.549 0.764 6.714 10.564 0.138 0.764 0.021 0.177 0.010 0.258 0.915

19

BBRes 0.054 0.029 0.301 0.029 0.046 0.810 365.331 202.630 32.673 0.626 0.848 0.168 41.128 7.567 0.773 0.953 64.611 109.229 8.904 7.767 13.491 9.177 19.409 0.144 0.792 0.028 0.229 0.013 0.314 0.833

random 0.046 0.031 0.311 0.029 0.056 0.815 435.735 241.546 42.043 0.664 0.913 0.172 49.652 8.247 1.029 1.074 139.305 119.144 8.417 11.239 20.128 9.386 19.861 0.156 0.819 0.028 0.227 0.013 0.316 0.810

𝑘 = 15 S_ord S_rev 0.066 0.064 0.035 0.040 0.332 0.327 0.027 0.024 0.073 0.071 0.896 0.929 433.159 430.226 235.900 241.893 55.849 47.503 0.644 0.587 1.058 0.944 0.183 0.177 50.199 44.693 8.507 7.460 1.120 0.960 1.105 1.041 174.340 74.833 126.696 115.648 10.800 10.909 12.185 9.966 20.939 18.154 10.375 9.819 23.992 22.308 0.134 0.150 0.926 0.893 0.030 0.032 0.231 0.233 0.013 0.013 0.326 0.326 1.078 1.106

peel_ord 0.047 0.039 0.309 0.030 0.048 0.809 374.732 207.412 46.640 0.618 0.895 0.183 51.987 8.143 1.404 1.124 164.495 127.000 8.750 17.252 30.392 9.197 20.546 0.170 0.836 0.030 0.235 0.010 0.317 0.925

peel_rev 0.056 0.030 0.310 0.030 0.057 0.847 442.794 246.285 36.266 0.700 0.898 0.170 44.959 8.241 0.944 0.892 73.866 118.267 9.115 7.883 13.322 9.220 20.227 0.120 0.836 0.024 0.231 0.013 0.316 0.954

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181