A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems

Basic Information

• Paper ID: 2511.03157
• Title: A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
• Authors: Yi Zhou (University of Electronic Science and Technology of China), Chunyu Luo (University of Electronic Science and Technology of China), Zhengren Wang (Peking University), Zhang-Hua Fu (Shenzhen Institute of Artificial Intelligence and Robotics for Society, CUHK Shenzhen)
• Classification: cs.DS (Data Structures and Algorithms)
• Publication Date: November 6, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2511.03157v2

Abstract

This paper investigates the maximum low-diameter f(·)-dense subgraph problem (MfDS). An f(·)-dense graph is defined as a graph with n vertices containing at least f(n) edges, where f(·) is a well-defined function. This concept encompasses various clique relaxation models including γ-quasi-cliques, k-defective cliques, and dense cliques. However, f(·)-dense graphs may be disconnected or weakly connected. To address this issue, the paper studies the problem of finding maximum f(·)-dense subgraphs with diameter at most 2. Specifically, a decomposition-based branch-and-bound algorithm is proposed to optimally solve this problem. The algorithm's key characteristic is decomposing the graph into n smaller subgraphs, allowing independent search within each subgraph. The paper introduces decomposition strategies such as degeneracy ordering and two-hop degeneracy ordering, along with a branch-and-bound algorithm featuring novel ordering-based bounds. Experimental results on 139 real-world graphs demonstrate that the algorithm outperforms MIP solvers and pure branch-and-bound methods, solving nearly twice as many instances within one hour.

Research Background and Motivation

1. Problem to be Solved

Identifying tightly connected subgraphs (cohesive subgraphs) is a core task in network analysis, with applications in community detection, protein complex identification, financial network analysis, and other domains. The classical clique model requires edges between all pairs of vertices, but this requirement is too restrictive, especially in practical applications with noise and errors. Consequently, various clique relaxation models have emerged, such as:

• γ-quasi-cliques: Induced subgraphs of n vertices with at least γ(n choose 2) edges
• s-defective cliques: With at least (n choose 2) - s edges
• Average s-plex: With at least n(n-s)/2 edges

These models can be unified as f(·)-dense graphs: graphs with n vertices containing at least f(n) edges.

2. Problem Importance

Existing f(·)-dense graph models suffer from a critical flaw: they may be disconnected or have weak connectivity. The paper demonstrates this through two examples in Figure 1:

• G1: A 200-vertex clique plus a 10-vertex path, requiring 10 hops from v1 to v210
• G2: A 200-vertex clique plus 10 isolated vertices, with no path between v1 and v210

Both graphs satisfy the density requirement f(n)=0.9(n choose 2), but are clearly not tightly connected communities.

3. Limitations of Existing Methods

• MIP approaches: While mixed integer programming models exist for specific f(·) functions (e.g., GF3), they are inefficient for large-scale graphs and lack MIP models for diameter constraints
• Branch-and-bound methods: Existing algorithms target specific problems (e.g., maximum s-defective clique, maximum γ-quasi-clique) but lack a unified framework for general f(·)-dense graphs
• Connectivity constraints: Santos et al. (2024) proposed spanning tree-based connectivity constraints, but diameter constraints better ensure tight connectivity

4. Research Motivation

This paper introduces the concept of low-diameter f(·)-dense graphs: requiring the graph to be connected, have at least f(n) edges, and have diameter at most 2. The diameter-2 constraint (called 2-club) ensures that the shortest path between any two vertices is at most 2, guaranteeing strong connectivity. The paper aims to design efficient exact algorithms to solve this NP-hard problem.

Core Contributions

1. Problem Formalization:
   • First systematically defines f(·)-dense graphs and their hereditary properties
   • Formalizes the maximum low-diameter f(·)-dense subgraph problem (MfDS)
   • Provides the MIP-fD mixed integer linear programming model
2. Algorithm Framework:
   • Proposes a preprocessing framework based on graph decomposition, decomposing the input graph into n smaller subgraphs
   • Introduces two decomposition strategies: degeneracy ordering and two-hop degeneracy ordering
   • Designs a branch-and-bound algorithm with novel ordering-based bounds
   • Provides worst-case complexity analysis for each component and the overall algorithm
3. Experimental Verification:
   • Tests two f(·) functions (γ-quasi-cliques and s-defective cliques) on 139 real-world graphs
   • Demonstrates that the decomposition framework significantly improves performance, solving twice as many instances as pure branch-and-bound within one hour
   • Shows that ordering-based bounds dramatically reduce search tree size

Method Details

Task Definition

Input:

• Undirected simple graph G=(V,E)
• Density function f: ℤ≥0 → ℝ, satisfying f(i) ≤ (i choose 2)
• Computation oracle for f(·) (constant time)

Output: Maximum vertex set S⊆V such that:

1. |E(S)| ≥ f(|S|) (f(·)-density)
2. diam(GS) ≤ 2 (low-diameter constraint)

Objective: ωf(G) = max{|S| : S⊆V, |E(S)|≥f(|S|), diam(GS)≤2}

Complexity: NP-hard, W1-hard, difficult to approximate in polynomial time (since maximum clique is a special case)

Core Algorithm Framework

1. Overall Decomposition Framework (Algorithm 1)

Key Lemma (Lemma 3): Given any vertex ordering π=⟨v1,...,vn⟩ of graph G, for each vertex vi, define:

• Vi = {vi} ∪ {N^(2)_G(vi) ∩ {vi+1,...,vn}}
• Gi = GVi

If S_i is the maximum low-diameter f(·)-dense subgraph containing vi in Gi, then: **ωf(G) = max(|S_1|,...,|S*_n|)**

Algorithm Flow:

1. Obtain initial solution S using heuristic (lower bound)
2. Determine vertex order π using ordering algorithm
3. For each vi in π:
   - Construct subgraph Gi = G[Vi]
   - Solve using ExactSearch(Gi, f(·), {vi}, N^(2)_G(vi), lb)
4. Return maximum solution from all subproblems

Time Complexity: O(Theur(G) + Torder(G) + poly(αG)2^αG)

• αG = max(|V1|,...,|Vn|): maximum subgraph size
• Key is minimizing αG to control exponential part

2. Efficient Heuristic Algorithm (Algorithm 2)

Based on degeneracy ordering:

• Definition: A k-degeneracy ordering is a vertex ordering ⟨v1,...,vn⟩ where each vi has degree ≤ k in the induced subgraph {vi,...,vn}
• Computation: Using peel algorithm, O(|V|+|E|) time, repeatedly removing minimum-degree vertices
• Degeneracy: dG, the minimum k value

Heuristic Flow:

1. Compute degeneracy ordering ⟨v1,...,vn⟩
2. For each vi:
   - Si ← {vi} ∪ {NG(vi) ∩ {vi+1,...,vn}}
   - Gi ← G[Si] (diameter ≤ 2)
   - While |Ei| < f(|Si|):
       Remove minimum-degree vertex in Gi
   - Update optimal solution S*
3. Return S*

Time Complexity: O(|E| + |V|d²G)

• In real graphs, dG << |V| (e.g., ca-dblp-2010: dG=74, |V|=226413)

3. Vertex Ordering Strategies

Strategy 1: Degeneracy Ordering

• Advantage: O(|V|+|E|) time
• Bound: αG ≤ min(dG·ΔG, |V|)
• Proof: |Vi| = 1 + |NG(vi)∩{vi+1,...,vn}| + |N^(2)_G(vi)\NG(vi)∩{vi+1,...,vn}| ≤ 1 + dG + dG·ΔG

Strategy 2: Two-Hop Degeneracy Ordering (Algorithm 3)

• Definition: A k-two-hop degeneracy ordering where each vi has at most k two-hop neighbors in {vi,...,vn}
• Computation: Similar to peel, repeatedly removing vertex with minimum |N^(2)_G(v)|
• Time Complexity: O(|V||E|·min(tdG, ΔG))
• Bound: αG ≤ tdG
• Advantage: tdG typically much smaller than dG·ΔG (e.g., ca-dblp-2010: tdG=238 vs dG·ΔG=17612)

Branch-and-Bound Algorithm (Algorithm 4)

Core Structure

BranchBound(G, S, C, lb):
  Input: Graph G, current solution S, candidate set C, lower bound lb
  
  1. If G[S] is feasible and |S|>lb: update lb and optimal solution
  
  2. If f(·) is hereditary and |E(S)|<f(|S|): prune and return
  
  3. UB ← SortBound(G, f(·), S, C)  // Compute upper bound
  
  4. If UB ≤ lb: prune and return
  
  5. If f(·) is hereditary: apply reduction rules (Lemma 5)
  
  6. Randomly select u∈C
  
  7. If conditions in Lemma 4 are satisfied: recurse only on S∪{u} branch
     Otherwise: recurse on both S∪{u} and S branches

Reduction Rules (Lemma 4 & 5)

Lemma 4 (General Reduction): If u∈C satisfies:

1. |NG(u)| = |V|-1, or
2. |NG(u)| = |V|-2 and GS∪{u} is feasible

Then there exists an optimal solution containing u → only search the branch containing u

Lemma 5 (Hereditary Function Reduction): If f(·) is hereditary:

1. If |E(S)| < f(|S|), then no feasible solution contains S
2. If v∈C such that |E(S∪{v})| < f(|S|+1), then no feasible solution contains v

Ordering-Based Upper Bound Algorithm (Algorithm 5)

Simple Bound (Section 4.6.1)

For v∈C, define wS(v) = |S\N(v)| (number of non-neighbors of v in S)

1. Sort C in non-decreasing order of wS(v) to get ⟨v1,...,v|C|⟩
2. Find maximum k such that wS(Sk) + |E(S)| ≤ gf(|S|+k), where gf(n)=(n choose 2)-f(n)
3. Return |S|+k

Correctness (Lemma 6): wS(S') + |E(S)| underestimates |E(S∪S')|

Improved Ordering-Based Bound (SortBound)

Core Idea:

1. Simple bound ignores edges between S and C
2. Simple bound doesn't account for diameter-2 constraint

Algorithm Flow:

1. Partition C into χ independent sets Π1,...,Πχ using greedy coloring
   (minimize χ ≈ graph coloring problem, O(|C|³) greedy)

2. For each Πi:
   a. Sort Πi by wS(v)
   b. Further partition Πi into multiple Rσ such that any two vertices 
      in Rσ have distance > 2
   c. From each Rσ select vertex with minimum wS(·) and add to C'
   d. Compute w'S(uj) = wS(uj) + j - 1

3. Sort C' by w'S(·), find maximum k such that |E(S)| + w'S(Sk) ≤ gf(|S|+k)

4. Return |S|+k

Time Complexity: O(|C|³ + |S||C|)

Correctness (Theorem 3):

• Each independent set Πi can contribute at most s'i vertices
• Each Rσ can contribute at most 1 vertex due to diameter-2 constraint
• |E(S*)| ≥ |E(S)| + Σw'S(v^(ij)m) ≥ |E(S)| + Σ^{|S'|} w'S(vj)

Advantages:

• Accounts for independent set structure (reduces edge count overestimation)
• Accounts for diameter-2 constraint (at most 1 vertex per Rσ)
• Faster than LP relaxation with comparable bound tightness

Experimental Setup

Dataset

• Source: Network Data Repository
• Scale: 139 undirected real-world graphs
• Range: Up to 5.87×10⁷ vertices, 1.06×10⁸ edges
• Domains: Social networks, biological networks, collaboration networks, road networks, etc.

f(·) Function Configuration

1. γ-quasi-cliques: f(i) = γ(i choose 2), γ ∈ {0.99, 0.95, 0.90, 0.85}
   • Non-hereditary function
2. s-defective cliques: f(i) = (i choose 2) - s, s ∈ {1, 3}
   • Hereditary function

Comparison Algorithms

1. Deg-BnB: Degeneracy ordering + branch-and-bound
2. TwoDeg-BnB: Two-hop degeneracy ordering + branch-and-bound
3. BnB: Pure branch-and-bound (no decomposition)
4. MIP: Gurobi solver + MIP-fD model
5. Deg-MIP: Degeneracy ordering decomposition + MIP solving subproblems
6. TwoDeg-MIP: Two-hop degeneracy ordering decomposition + MIP solving subproblems

Experimental Environment

• CPU: Intel Xeon Platinum 8360Y @ 2.40GHz
• System: Ubuntu 22.04
• Compiler: g++ 9.3.0 with -Ofast
• Time Limit: 3600 seconds (1 hour)
• Code: https://github.com/cy-Luo000/MDSL

Evaluation Metrics

• Number of instances solved at different time points
• Runtime on specific graphs
• Upper bound tightness (gap from optimal solution)
• Search tree node count

Experimental Results

Main Results

1. Overall Performance (Figure 4 & 5)

γ-quasi-cliques (γ=0.99, 0.95):

• TwoDeg-BnB and Deg-BnB comprehensively outperform other algorithms at all time points
• Within 1 hour, TwoDeg-BnB solves approximately 100 instances, BnB only 50
• MIP can barely solve any instances

γ-quasi-cliques (γ=0.90, 0.85):

• After 1000 seconds, TwoDeg-MIP and Deg-MIP performance approaches branch-and-bound methods
• Decomposition framework significantly improves MIP performance

s-defective cliques (s=1, 3):

• TwoDeg-BnB and Deg-BnB solve approximately 110 instances
• Pure BnB solves about 60 instances
• Hereditary property provides greater advantage for branch-and-bound methods

Key Finding: Decomposition framework doubles the number of solved instances

2. Large-Scale Graph Detailed Results (Table 1 & 2)

Notable Cases (γ=0.99):

• web-uk-2005 (129,632 vertices): TwoDeg-BnB 634 seconds, MIP timeout
• inf-road-usa (23,947,347 vertices): TwoDeg-BnB 70 seconds, other methods timeout
• scc_infect-dublin: Deg-BnB 0.54 seconds, TwoDeg-BnB timeout (ordering choice impact)

Acceleration Effects:

• TwoDeg-BnB 2-3 orders of magnitude faster than BnB (e.g., web-indochina-2004: 0.25 seconds vs timeout)
• 39 instances solved by TwoDeg-BnB or Deg-BnB but failed by BnB
• Decomposition+MIP sometimes outperforms pure combinatorial algorithms (e.g., web-sk-2005)

s-defective cliques (Table 2):

• Hereditary property enables more pruning
• scc_infect-dublin (s=1): TwoDeg-BnB 0.83 seconds vs Deg-MIP timeout
• rec-amazon: TwoDeg-BnB 0.08 seconds vs BnB 264 seconds

Ablation Studies

Upper Bound Effectiveness Analysis (Table 3 & 4)

Upper Bound Tightness Comparison:

LP Relaxation > SortBound > Simple Bound

Specific Cases (γ=0.95):

• ca-CondMat:
  • Optimal: 28
  • LP: 29, Simple: 280, SortBound: 142
  • SortBound achieves balance between tightness and scalability
• inf-roadNet-CA:
  • Optimal: 4
  • LP: Infeasible, Simple: 13, SortBound: 5
  • LP fails on large graphs

Search Tree Size Impact:

• inf-roadNet-CA (γ=0.95):
  • TwoDeg-BnB: 5 seconds, 10 nodes
  • TwoDeg-BnB/ub (without SortBound): 10 seconds, 14,138,820 nodes
  • Search tree reduction of 6 orders of magnitude
• ca-MathSciNet (s=3):
  • TwoDeg-BnB: 7.62 seconds, 80 nodes
  • TwoDeg-BnB/ub: 1228 seconds, 256,325,020 nodes
  • 100x speedup

Key Finding: SortBound maintains tightness while scaling to million-vertex graphs

Relationship between αG and Runtime (Figure 6 & 7)

Observations:

• Nearly half of instances have αG ≤ 1000 (much smaller than |V|)
• Runtime positively correlates with αG
• Two-hop degeneracy ordering typically produces smaller αG

Typical Case:

• ca-dblp-2010: |V|=226,413, dG=74, tdG=238, dG·ΔG=17,612
  • Two-hop degeneracy ordering advantage evident

Validation: Supports the design principle of minimizing αG

Case Studies

Graph Decomposition Effect Example

Using web-indochina-2004 as example (|V|=11,358, |E|=47,606):

• Degeneracy: dG=49
• Two-hop degeneracy: tdG=199
• After decomposition: αG=199 (two-hop ordering) vs αG≈2450 (degeneracy ordering)
• Performance: TwoDeg-BnB 0.25 seconds vs Deg-BnB 0.18 seconds vs BnB 12.10 seconds

Upper Bound Algorithm Example (Figure 2 & 3)

Input: 10 vertices, S={v1,v2}, C={v3,...,v10}

Steps:

1. Partition into independent sets: Π1={v3,v5,v7,v9}, Π2={v4,v6,v8,v10}
2. Compute wS: wS(v3)=0, wS(v5)=1, wS(v7)=2...
3. Further partition by distance: R¹₁={v3,v7}, R²₁={v5,v9}, R¹₂={v8,v4}, R²₂={v10,v6}
4. Select minimum wS: C'={v3,v5,v8,v10}
5. Compute w'S: w'S(v3)=0, w'S(v8)=0, w'S(v5)=2, w'S(v10)=2

Results:

• f(i)=0.8(i choose 2): upper bound=4
• f(i)=(i choose 2)-4: upper bound=5

Related Work

1. Clique Relaxation Models

• γ-quasi-cliques (Abello et al. 2002): NP-hard for γ∈(0,1]
  • MIP methods (Pattillo et al. 2013a)
  • Branch-and-bound (Mahdavi Pajouh et al. 2014, Ribeiro & Riveaux 2019)
• s-defective cliques (Yu et al. 2006): NP-hard for s≥1
  • Low-diameter constraint (Luo et al. 2024): O(nc·1.2ⁿ)
  • Branch-and-bound (Chen et al. 2021b, Gao et al. 2022, Chang 2023)
• Average s-plex (Veremyev et al. 2016)

2. General f(·)-Dense Graphs

• Veremyev et al. 2016:
  • Proposes multiple MIP models (GF3 optimal)
  • Doesn't consider diameter constraints
• Complexity Results (Asahiro et al. 2002):
  • NP-hard when f(n)=Θ(n^(1+ε)) or f(n)=n+Ω(n^ε)
  • Polynomial-time solvable when f(n)=n+c

3. 2-Club Problem

• Definition: Subgraph with diameter ≤ 2
• MIP methods (Pajouh et al. 2016, Lu et al. 2022)
• Branch-and-bound (Hartung et al. 2012, Komusiewicz et al. 2019)
• This paper's contribution: First to combine 2-club with f(·)-density constraint

4. Connectivity Constraints

• Santos et al. 2024: Spanning tree-based connected quasi-cliques
• This paper's advantage: Diameter constraint stronger than mere connectivity

5. Graph Decomposition Techniques

• Degeneracy ordering (Matula & Beck 1983): O(|V|+|E|)
• Two-hop degeneracy (Wünsche 2021): First used for k-plex and k-club
• This paper's innovation: Systematic application to general f(·)-dense graphs

Conclusions and Discussion

Main Conclusions

1. Theoretical Contributions:
   • Systematized theoretical framework for f(·)-dense graphs
   • Proved necessary and sufficient conditions for hereditary property
   • Provided correctness and complexity analysis for decomposition framework
2. Algorithmic Contributions:
   • Decomposition framework reduces problem to n independent subproblems
   • Two-hop degeneracy ordering effectively controls subgraph size
   • Ordering-based bounds achieve balance between tightness and efficiency
3. Experimental Verification:
   • Doubled number of solved instances on 139 real-world graphs
   • Scalable to tens of millions of vertices
   • Ordering-based bounds reduce search tree by 6 orders of magnitude

Limitations

1. Algorithm Limitations:
   • Still exponential-time algorithm (O(2^αG))
   • For dense graphs, αG may approach |V|
   • Difficult to pre-determine which ordering strategy is superior
2. Model Limitations:
   • Diameter=2 constraint may be too restrictive
   • Doesn't consider vertex weights or edge weights
   • f(·) must satisfy specific conditions for hereditary property
3. Experimental Limitations:
   • Only tests two f(·) functions
   • Lacks direct comparison with all related work
   • Missing tests on ultra-large-scale graphs (hundred-million vertices)

Future Directions

1. Algorithm Extensions:
   • Parallelize decomposition framework (subgraphs can be processed in parallel)
   • Extend to other diameter constraints (k-club, k≥3)
   • Combine with other structural constraints (vertex connectivity)
2. Theoretical Deepening:
   • Analyze hereditary property for more f(·) functions
   • Study parameterized complexity
   • Design approximation algorithms
3. Application Extensions:
   • Incremental algorithms for dynamic graphs
   • Extensions to weighted graphs
   • Domain-specific models (e.g., biological networks)

In-Depth Evaluation

Strengths

1. Theoretical Rigor:
   • Complete mathematical proofs (Appendix A)
   • Clear complexity analysis
   • Necessary and sufficient conditions for hereditary property (Lemma 1 & 2)
2. Algorithmic Innovation:
   • Decomposition Framework: Lemma 3 cleverly decomposes global problem into local subproblems
   • Two-Hop Degeneracy Ordering: Novel ordering strategy tailored for diameter constraint
   • Ordering-Based Bound: Sophisticated multi-level partitioning design (independent sets + distance constraints)
3. Experimental Comprehensiveness:
   • 139 real-world graphs, 6 algorithms, 2 classes of f(·) functions
   • Detailed ablation studies (Table 3 & 4)
   • Visual analysis (Figure 6 & 7)
   • Open-source code ensures reproducibility
4. Practical Value:
   • Scalable to tens of millions of vertices
   • Several orders of magnitude faster than MIP
   • General framework applicable to multiple clique relaxation models
5. Writing Clarity:
   • Clear motivation in introduction (Figure 1 intuitive)
   • Detailed algorithm pseudocode
   • Complete theorem proofs

Weaknesses

1. Ordering Strategy Selection:
   • Lacks theoretical guidance on when to use degeneracy vs two-hop degeneracy
   • Table 1 shows Deg-BnB sometimes faster (e.g., scc_infect-dublin)
   • Suggestion: Design adaptive strategy or provide selection heuristic
2. Upper Bound Algorithm Complexity:
   • O(|C|³) may become bottleneck
   • Greedy coloring is suboptimal
   • Improvement direction: Use faster coloring algorithms or relax optimality
3. Experimental Comparison:
   • Missing comparison with Santos et al. 2024's spanning tree method
   • Lacks comparison with problem-specific optimal algorithms (e.g., Chang 2023's k-defective clique algorithm)
   • MIP model may have room for improvement (e.g., adding valid inequalities)
4. Scalability Analysis:
   • Insufficient discussion of cases where αG>10,000
   • Dense graph performance not thoroughly tested
   • Missing memory consumption analysis
5. Theoretical Gaps:
   • No approximation ratio analysis provided
   • Parameterized complexity (e.g., with αG as parameter) not discussed
   • Average-case complexity not analyzed

Impact

1. Academic Contribution:
   • Unified theoretical framework for multiple clique relaxation models
   • Decomposition techniques transferable to other subgraph extraction problems
   • High citation value (combines NP-hard problems, graph decomposition, branch-and-bound)
2. Practical Value:
   • Direct application to community detection, bioinformatics, etc.
   • Open-source code promotes technology transfer
   • Can serve as baseline for other algorithms
3. Reproducibility:
   • Detailed algorithm descriptions
   • Open-source code (https://github.com/cy-Luo000/MDSL)
   • Public datasets (Network Data Repository)
   • Clear experimental setup
4. Limitations:
   • Industrial-scale applications require further optimization (e.g., parallelization)
   • Problem-specific algorithms may outperform general approach
   • Need more domain expert validation for practical utility

Applicable Scenarios

Recommended Scenarios:

1. Social Network Analysis: Finding tightly connected communities (diameter ≤ 2 ensures fast communication)
2. Biological Networks: Protein complex identification (allows few missing edges)
3. Collaboration Networks: Core research team identification
4. Medium-scale Graphs: |V|<10⁶, αG<5000 optimal performance

Not Recommended Scenarios:

1. Ultra-large Dense Graphs: αG approaching |V| causes exponential explosion
2. Real-time Applications: Worst-case still requires exponential time
3. Approximate Solutions Sufficient: Exact algorithm overhead too high

Improvement Suggestions:

1. Combine with heuristics for fast approximate solutions
2. Parallelize for ultra-large-scale graphs
3. Design specialized algorithms for specific f(·)

References

Core Related Work

1. Veremyev et al. (2016): "Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs" - Proposes GF3 MIP model
2. Luo et al. (2024): "A faster branching algorithm for the maximum k-defective clique problem" - ECAI 2024, O(nc·1.2ⁿ) algorithm
3. Chang (2023): "Efficient maximum k-defective clique computation with improved time complexity" - PACMMOD, improved branch-and-bound
4. Santos et al. (2024): "Ensuring connectedness for the maximum quasi-clique and densest k-subgraph problems" - Spanning tree connectivity constraint
5. Wünsche (2021): "Mind the gap when searching for relaxed cliques" - First proposes two-hop degeneracy ordering

Theoretical Foundations

6. Matula & Beck (1983): "Smallest-last ordering and clustering and graph coloring algorithms" - Classical work on degeneracy ordering
7. Asahiro et al. (2002): "Complexity of finding dense subgraphs" - Complexity results for f(·)-dense graphs
8. Downey & Fellows (2012): "Parameterized complexity" - W1-hardness theory

Overall Assessment: This is an excellent paper with rigorous theory, innovative algorithms, and comprehensive experiments. The decomposition framework and ordering-based bound methods have high generality and practical value. The main contribution lies in unifying multiple clique relaxation models and providing efficient solution algorithms. Recommended for acceptance with significant contributions to graph algorithms and network analysis.