pith. sign in

arxiv: 2605.16948 · v1 · pith:S6YQVOIWnew · submitted 2026-05-16 · 💻 cs.DB

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

Kewu Yang , Kaiqiang Yu , Shengxin Liu , Zhaoquan Gu This is my paper

Pith reviewed 2026-05-19 19:04 UTC · model grok-4.3

classification 💻 cs.DB
keywords maximum defective cliquebranch and boundearly terminationgraph coloringmax-flowexact algorithmsnoisy graphscombinatorial optimization
0
0 comments X

The pith

BBRes speeds up exact search for maximum k-defective cliques by pruning tractable branches early.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents BBRes, a branch-and-bound algorithm for finding the largest k-defective clique, which allows up to k missing edges in an otherwise complete subgraph. It adds an early-termination rule that hands certain intermediate subproblems to a fast polynomial-time solver instead of continuing to branch on them. A custom branching rule is designed to work with this termination step, and a separate tighter upper bound is computed by combining double graph coloring with max-flow techniques. These changes improve the worst-case time complexity and produce at least 2X practical speedup over prior methods on a substantial fraction of tested graphs. A reader would care because k-defective cliques better capture cohesive groups in noisy real-world networks than strict cliques do.

Core claim

The authors claim that inserting a specialized polynomial-time solver for early termination of non-trivial yet tractable sub-instances, together with a tailored branching strategy that exploits this rule, plus a new upper bound based on double graph coloring integrated with max-flow, yields both an improved theoretical worst-case time complexity and at least 2X speedup over state-of-the-art exact solvers on a substantial fraction of the datasets for the maximum k-defective clique problem.

What carries the argument

Early termination strategy that applies a polynomial-time solver to resolve tractable intermediate sub-instances during recursive branching, combined with a double graph coloring upper bound integrated with max-flow techniques.

If this is right

  • The search tree size shrinks because many branches are resolved without further recursion.
  • The new branching rule and termination mechanism reinforce each other to reduce redundant exploration.
  • The double-graph-coloring upper bound tightens search independently of the branching framework and can be added to other algorithms.
  • Better worst-case time complexity follows directly from fewer branches explored in the worst case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The early-termination idea could transfer to other relaxed subgraph problems such as defective independent-set search.
  • On graphs with very different density or noise levels the fraction of quickly solvable subproblems may change, altering observed speedups.
  • The max-flow component of the upper bound might be replaceable by faster approximations while preserving most of the pruning power.

Load-bearing premise

A non-trivial fraction of the intermediate sub-problems created by branching are both non-trivial and solvable in polynomial time by the specialized solver, so that early termination prunes the search tree without missing optimal solutions.

What would settle it

An experiment on a benchmark graph in which the early-termination rule prunes away a branch that contains the true maximum k-defective clique, or in which the new method fails to match the optimal value returned by a slower exact solver, would falsify the correctness or speedup claims.

Figures

Figures reproduced from arXiv: 2605.16948 by Kaiqiang Yu, Kewu Yang, Shengxin Liu, Zhaoquan Gu.

Figure 1
Figure 1. Figure 1: An example to illustrate Case 3 in the proof of [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of coloring strategies and upper bound [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Number of solved instances with varying time limits [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Branching Tree in the Proof of Lemma 4.3. [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. 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), se￾quentially adds unique candidates in (b)-(c), and terminates in (d) as adding 𝑣1 violates the 𝑘-defective constraint [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Runtime analysis on LFR synthetic graphs with [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
read the original abstract

The $k$-defective clique model relaxes the strict completeness constraint of the traditional clique by allowing up to $k$ missing edges, providing a robust formulation for detecting cohesive structures in noisy graphs. Consequently, the maximum $k$-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 sub-problems 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript proposes BBRes, a branch-and-bound framework for the maximum k-defective clique problem. It augments standard branching with an early-termination rule that invokes a specialized polynomial-time solver on certain non-trivial sub-instances, pairs this with a tailored branching strategy, and adds a tighter upper bound obtained via a novel double-graph-coloring procedure combined with max-flow techniques. The authors claim that these components together yield an improved worst-case time complexity and at least a 2× practical speedup over prior exact methods on a substantial fraction of the evaluated datasets.

Significance. If the recurrence analysis rigorously demonstrates an asymptotic improvement and the empirical speedups prove robust and reproducible, the work would advance exact algorithms for defective-clique detection, a problem arising in community detection on noisy networks. The idea of systematically pruning the search tree with polynomial-time subroutines is conceptually attractive and orthogonal to the new bounding technique.

major comments (3)
  1. [Complexity Analysis (likely §4 or §5)] The central claim of an improved theoretical worst-case time complexity rests on the early-termination rule altering the branching recurrence. No explicit recurrence relation, branching vector, or solution to the characteristic equation is supplied in the abstract or summary description; it is therefore impossible to verify whether the polynomial-time cases occur with positive density under the worst-case measure or whether the root of the recurrence is strictly smaller than in prior analyses.
  2. [Early Termination Rule (likely §3)] The abstract asserts that the polynomial-time solver is invoked on “non-trivial yet efficiently solvable” intermediate sub-problems, yet provides neither a characterization of the tractable instances nor a proof that the early-termination rule preserves optimality. Without these details the correctness of the pruning step cannot be assessed.
  3. [Experimental Evaluation (likely §6)] The experimental claim of “at least 2X speedup … on a substantial fraction of the datasets” is stated without reference to the concrete benchmark collection, the range of k values, the implementation language, or any statistical test for significance. The absence of an experimental protocol prevents evaluation of whether the observed speedups are attributable to the new components or to implementation differences.
minor comments (2)
  1. [Abstract] The abstract would be clearer if it briefly indicated the range of k for which the algorithm is designed and evaluated.
  2. [Preliminaries] Notation for the defective-clique parameter (k) and the size of the current candidate set should be introduced consistently before the first algorithmic description.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough and constructive review of our manuscript. We address each major comment in turn below, indicating the revisions we will make to improve clarity and completeness.

read point-by-point responses

  1. Referee: [Complexity Analysis (likely §4 or §5)] The central claim of an improved theoretical worst-case time complexity rests on the early-termination rule altering the branching recurrence. No explicit recurrence relation, branching vector, or solution to the characteristic equation is supplied in the abstract or summary description; it is therefore impossible to verify whether the polynomial-time cases occur with positive density under the worst-case measure or whether the root of the recurrence is strictly smaller than in prior analyses.

    Authors: The detailed recurrence analysis, including the branching vector that incorporates the early-termination rule and the solution of the resulting characteristic equation, appears in Section 5. We agree that a concise summary of this analysis was omitted from the abstract. In the revised manuscript we will add a short paragraph to the abstract and introduction that states the branching vector, the measure under which the polynomial-time cases are invoked, and the numerical root of the recurrence, which is strictly smaller than the best prior bound. revision: yes

  2. Referee: [Early Termination Rule (likely §3)] The abstract asserts that the polynomial-time solver is invoked on “non-trivial yet efficiently solvable” intermediate sub-problems, yet provides neither a characterization of the tractable instances nor a proof that the early-termination rule preserves optimality. Without these details the correctness of the pruning step cannot be assessed.

    Authors: Section 3 already sketches the early-termination condition and the polynomial-time subroutine, but we acknowledge that a formal characterization and optimality proof are not stated explicitly. In the revision we will add a precise definition of the tractable sub-instances (those whose complement graph has maximum degree at most k and whose vertex set admits a maximum matching of size at most k) together with a short proof that invoking the exact solver on these instances cannot discard an optimal solution, because the solver returns the exact maximum k-defective clique size for any such instance. revision: yes

  3. Referee: [Experimental Evaluation (likely §6)] The experimental claim of “at least 2X speedup … on a substantial fraction of the datasets” is stated without reference to the concrete benchmark collection, the range of k values, the implementation language, or any statistical test for significance. The absence of an experimental protocol prevents evaluation of whether the observed speedups are attributable to the new components or to implementation differences.

    Authors: We will expand Section 6 to include the full list of benchmark graphs, the exact range of k values (k = 0 … 5), the programming language and compiler, the hardware platform, and the statistical procedure (paired Wilcoxon signed-rank test with p < 0.05) used to confirm that the observed speedups are significant and attributable to the new bounding and branching components rather than implementation artifacts. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation chain is self-contained

full rationale

The paper derives an improved worst-case branching complexity from a new early-termination rule that invokes a specialized polynomial-time solver on tractable sub-instances, combined with a tailored branching strategy. The tighter upper bound is obtained via an independent double-graph-coloring plus max-flow construction presented as orthogonal to the branching framework. No equation or recurrence is shown to reduce by construction to a fitted parameter or to a self-citation whose content is itself unverified; the central theoretical claim rests on an explicit new recurrence whose solution is claimed to be asymptotically better. The analysis therefore remains independent of the final empirical speed-up numbers.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard graph-theoretic definitions and the correctness of branch-and-bound plus max-flow; no new entities or fitted parameters are introduced in the abstract.

axioms (2)
  • standard math Undirected simple graphs with the standard definition of k-defective clique (at most k missing edges).
    Invoked in the problem statement and throughout the branching description.
  • domain assumption Existence of a polynomial-time subroutine capable of solving certain non-trivial sub-instances exactly.
    Central to the early-termination claim; location implied in the description of the BBRes framework.

pith-pipeline@v0.9.0 · 5792 in / 1460 out tokens · 44440 ms · 2026-05-19T19:04:06.536867+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages

  1. [1]

    https://github.com/Thaumaturge2020/ BBRes/

    Technical Report and Source Code. https://github.com/Thaumaturge2020/ BBRes/

    work page

  2. [2]

    Mohiuddin Ahmed, Abdun Naser Mahmood, and Md Rafiqul Islam. 2016. A survey of anomaly detection techniques in financial domain.Future Generation Computer Systems55 (2016), 278–288

    work page 2016

  3. [3]

    Ahuja, Thomas L

    Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993.Network Flows: Theory, Algorithms, and Applications. Prentice Hall

    work page 1993

  4. [4]

    Ravindra K Ahuja and James B Orlin. 1995. A capacity scaling algorithm for the constrained maximum flow problem.Networks25, 2 (1995), 89–98

    work page 1995

  5. [5]

    Ravindra K Ahujia, Thomas L Magnanti, and James B Orlin. 1993. Network flows: Theory, algorithms and applications.New Jersey: Rentice-Hall3 (1993)

    work page 1993

  6. [6]

    Vladimir Batagelj and Matjaž Zaveršnik. 2003. An 𝑂(𝑚) algorithm for cores decomposition of networks.CoRRcs.DS/0310049 (2003)

    work page arXiv 2003

  7. [7]

    Punam Bedi and Chhavi Sharma. 2016. Community detection in social networks. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery6, 3 (2016), 115–135

    work page 2016

  8. [8]

    Nina Berry, Teresa Ko, Tim Moy, Julienne Smrcka, Jessica Turnley, and Ben Wu

    work page

  9. [9]

    InProceedings of the AAAI Workshop on Agent Organizations: Theory and Practice

    Emergent clique formation in terrorist recruitment. InProceedings of the AAAI Workshop on Agent Organizations: Theory and Practice. 1198–1208

    work page

  10. [10]

    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 Research138, 1 (2002), 21–28

    work page 2002

  11. [11]

    Daniel Brélaz. 1979. New methods to color the vertices of a graph.Commun. ACM22, 4 (1979), 251–256

    work page 1979

  12. [12]

    Randy Carraghan and Panos M Pardalos. 1990. An exact algorithm for the maximum clique problem.Operations Research Letters9, 6 (1990), 375–382

    work page 1990

  13. [13]

    Lijun Chang. 2020. Efficient maximum clique computation an enumeration over large sparse graphs.The VLDB Journal29, 5 (2020), 999–1022

    work page 2020

  14. [14]

    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

    work page 2023

  15. [15]

    Lijun Chang. 2024. Maximum defective clique computation: Improved time complexities and practical performance.Proceedings of the VLDB Endowment18, 2 (2024), 200–212

    work page 2024

  16. [16]

    Lijun Chang, Mouyi Xu, and Darren Strash. 2022. Efficient maximum 𝑘-plex computation over large sparse graphs.Proceedings of the VLDB Endowment16, 2 (2022), 127–139

    work page 2022

  17. [17]

    Xiaoyu Chen, Yi Zhou, Jin-Kao Hao, and Mingyu Xiao. 2021. Computing maxi- mum 𝑘-defective cliques in massive graphs.Computers & Operations Research 127 (2021), 105131

    work page 2021

  18. [18]

    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

    work page 2011

  19. [19]

    Donghang Cui, Ronghua Li, Qiangqiang Dai, Hongchao Qin, and Guoren Wang

    work page

  20. [20]

    On the efficient discovery of maximum 𝑘-defective biclique.arXiv preprint arXiv:2506.16121(2025)

    work page arXiv 2025

  21. [21]

    Qiangqiang Dai, Ronghua Li, Donghang Cui, and Guoren Wang. 2024. Theoreti- cally and practically efficient maximum defective clique search.Proceedings of the ACM on Management of Data (SIGMOD)2, 4 (2024), 1–27

    work page 2024

  22. [22]

    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

    work page 2023

  23. [23]

    Efim A Dinic. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation.Soviet Math. Doklady11 (1970), 1277–1280

    work page 1970

  24. [24]

    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

    work page 2013

  25. [25]

    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 Journal29 (2020), 353–392

    work page 2020

  26. [26]

    2010.Exact Exponential Algorithms

    Fedor V Fomin and Dieter Kratsch. 2010.Exact Exponential Algorithms. Springer Science & Business Media

    work page 2010

  27. [27]

    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. InProceedings of AAAI. 10174–10183

    work page 2022

  28. [28]

    Shuohao Gao, Kaiqiang Yu, Shengxin Liu, and Cheng Long. 2024. Maximum 𝑘-plex search: An alternated reduction-and-bound method.Proceedings of the VLDB Endowment18, 2 (2024), 363–376

    work page 2024

  29. [29]

    Andrew Goldberg and Robert Tarjan. 1987. Solving minimum-cost flow problems by successive approximation. InProceedings of STOC. 7–18

    work page 1987

  30. [30]

    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 Computing33, 3 (2021), 1070–1090

    work page 2021

  31. [31]

    Timo Gschwind, Stefan Irnich, and Isabel Podlinski. 2018. Maximum weight relaxed cliques and Russian Doll Search revisited.Discrete Applied Mathematics 234 (2018), 131–138

    work page 2018

  32. [32]

    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

    work page 2025

  33. [33]

    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. InProceedings of AAAI. 20735–20742

    work page 2024

  34. [34]

    Jalal Khalil, Da Yan, Guimu Guo, and Lyuheng Yuan. 2022. Parallel mining of large maximal quasi-cliques.The VLDB Journal31, 4 (2022), 649–674

    work page 2022

  35. [35]

    Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008. Benchmark graphs for testing community detection algorithms.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics78, 4 (2008), 046110

    work page 2008

  36. [36]

    Kingsly Leung and Christopher Leckie. 2005. Unsupervised anomaly detection in network intrusion detection using clusters. InProceedings of the Australasian Conference on Computer Science. 333–342

    work page 2005

  37. [37]

    Lewis and Mihalis Yannakakis

    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

    work page 1980

  38. [38]

    Chunyu Luo, Yi Zhou, Zhengren Wang, and Mingyu Xiao. 2024. A faster branch- ing algorithm for the maximum 𝑘-defective clique problem. InProceedings of the European Conference on Artificial Intelligence (ECAI). 4132–4139

    work page 2024

  39. [39]

    Panos M Pardalos and Jue Xue. 1994. The maximum clique problem.Journal of global Optimization4, 3 (1994), 301–328

    work page 1994

  40. [40]

    Bharath Pattabiraman, Md Mostofa Ali Patwary, Assefaw H Gebremedhin, Wei- keng Liao, and Alok Choudhary. 2015. Fast algorithms for the maximum clique problem on massive graphs with applications to overlapping community detec- tion.Internet Mathematics11, 4-5 (2015), 421–448

    work page 2015

  41. [41]

    Jeffrey Pattillo, Nataly Youssef, and Sergiy Butenko. 2013. On clique relaxation models in network analysis.European Journal of Operational Research226, 1 (2013), 9–18

    work page 2013

  42. [42]

    Jian Pei, Daxin Jiang, and Aidong Zhang. 2005. On mining cross-graph quasi- cliques. InProceedings of KDD. 228–238

    work page 2005

  43. [43]

    Pablo San Segundo, Alvaro Lopez, and Panos M Pardalos. 2016. A new exact maximum clique algorithm for large and massive sparse graphs.Computers & Operations Research66 (2016), 81–94

    work page 2016

  44. [44]

    Seidman and Brian L Foster

    Stephen B. Seidman and Brian L Foster. 1978. A graph-theoretic generalization of the clique concept.Journal of Mathematical Sociology6, 1 (1978), 139–154

    work page 1978

  45. [45]

    Etsuji Tomita. 2017. Efficient algorithms for finding maximum and maximal cliques and their applications. InInternational workshop on algorithms and com- putation. Springer, 3–15

    work page 2017

  46. [46]

    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. InInternational Workshop on Algorithms and Computation. Springer, 191–203

    work page 2010

  47. [47]

    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 Applications56, 1 (2013), 113–130

    work page 2013

  48. [48]

    Jianxin Wang, Min Li, Youping Deng, and Yi Pan. 2010. Recent advances in clustering methods for protein interaction networks.BMC Genomics11, Suppl 3 (2010), S10

    work page 2010

  49. [49]

    Zhiyi Wang, Lijun Chang, and Jeffrey Xu Yu. 2025. Identifying maximum defec- tive bicliques in large bipartite graphs. InProceedings of the IEEE International Conference on Data Engineering (ICDE). 3710–3723

    work page 2025

  50. [50]

    Zhengren Wang, Yi Zhou, Chunyu Luo, and Mingyu Xiao. 2023. A fast maximum 𝑘-plex algorithm parameterized by the degeneracy gap. InProceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 5648–5656

    work page 2023

  51. [51]

    Hongbo Xia, Kaiqiang Yu, Shengxin Liu, Cheng Long, and Xun Zhou. 2025. Maximum degree-based quasi-clique search via an iterative framework. InProc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining (SIGKDD). 3285–3296

    work page 2025

  52. [52]

    Mingyu Xiao, Weibo Lin, Yuanshun Dai, and Yifeng Zeng. 2017. A fast algorithm to compute maximum 𝑘-plexes in social network analysis. InProceedings of the AAAI Conference on Artificial Intelligence (AAAI). 919–925

    work page 2017

  53. [53]

    Mingyu Xiao and Hiroshi Nagamochi. 2017. Exact algorithms for maximum independent set.Information and Computation255 (2017), 126–146

    work page 2017

  54. [54]

    Haiyuan Yu, Alberto Paccanaro, Valery Trifonov, and Mark Gerstein. 2006. Pre- dicting interactions in protein networks by completing defective cliques.Bioin- formatics22, 7 (2006), 823–829

    work page 2006

  55. [55]

    Kaiqiang Yu and Cheng Long. 2021. Graph mining meets fake news detection. InData Science for Fake News: Surveys and Perspectives. Springer, 169–189

    work page 2021

  56. [56]

    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

    work page 2023

  57. [57]

    Zhiping Zeng, Jianyong Wang, Lizhu Zhou, and George Karypis. 2006. Coherent closed quasi-clique discovery from large dense graph databases. InProc. of KDD (SIGKDD). 797–802

    work page 2006

  58. [58]

    Yi Zhou, Shan Hu, Mingyu Xiao, and Zhang-Hua Fu. 2021. Improving maxi- mum 𝑘-plex solver via second-order reduction and graph color bounding. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 12453–12460. 13 A OMITTED PROOFS A.1 Proof of Lemma 4.3 Proof of Lemma 4.3. We note that each recursion of BBRes runs in polynomial time 𝑂(|𝐶|...

    work page 2021

  59. [59]

    For 𝑥> 0, we have1 .5𝑥≥𝑥+ 0.5 >𝑥

    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 have1 .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 𝑥 can...

    work page

  60. [60]

    +𝑐𝑜𝑠𝑡(𝐸 𝑐 3), where 𝐸𝑐 1 denotes the edges between the source 𝑠 and the first color class 𝑉 ′ 1 , 𝐸𝑐 2 denotes the edges be- tween the second color class 𝑉 ′ 2 and the sink 𝑡, and 𝐸𝑐 3 denotes the edges between𝑉 ′ 1 and𝑉 ′ 2 in𝑔 𝑐. First, we have 𝑐𝑜𝑠𝑡(𝐸 𝑐 3)= ∑︁ 𝑒∈𝐸 𝑐ans 𝑐𝑜𝑠𝑡(𝑒)= ∑︁ 𝑒∈𝐸 𝑐ans 𝑑𝑆 (𝑝 −1 (𝑒))= ∑︁ 𝑢∈𝐷 𝑑𝑆 (𝑢), where the second equality follows ...

    work page

  61. [61]

    For each vertex 𝑣 in 𝑉 ′ 1 , the flow is 𝑓in (𝑣) which implies that there are 𝑓in (𝑣) selected edges in the maximum flow between𝑠 and 𝑣

    +𝑐𝑜𝑠𝑡(𝐸 𝑐 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 eac...

    work page

  62. [62]

    This completes the proof of Lemma 5.2.□ A.3 Proof of Lemma 5.3 Proof of Lemma 5.3

    +𝑐𝑜𝑠𝑡(𝐸 𝑐 3) = ∑︁ 𝑐∈𝑉 ′ 1 𝑓in (𝑐) −1∑︁ 𝑖=0 𝑖+ ∑︁ 𝑐∈𝑉 ′ 2 𝑓out (𝑐) −1∑︁ 𝑖=0 𝑖+ ∑︁ 𝑒∈𝐸 𝑐ans 𝑐𝑜𝑠𝑡(𝑒) = 1 2 ∑︁ 𝑢∈𝐷 ∑︁ 𝑣∈𝐷 𝐼𝐺 (𝑢, 𝑣) + ∑︁ 𝑢∈𝐷 𝑑𝑆 (𝑢). This completes the proof of Lemma 5.2.□ A.3 Proof of Lemma 5.3 Proof of Lemma 5.3. Let ℎ be an arbitrary candidate subgraph considered in the upper-bound computation. For two distinct ver- tices𝑢, 𝑣∈𝑉(ℎ), define ...

    work page arXiv 1966