Efficient Maximum k-Defective Clique Computation with Improved Time Complexity

Summary: Introduces kDC, a framework for exact maximum k-defective clique with sub-2^n time, via non-fully-adjacent-first branching, excess-removal, and high-degree reductions. Separates worst-case techniques from practical optimizations; adds a tighter upper bound, two reductions, and fast initial solution; benchmarks on 290 graphs show kDC vastly outperforms KDBB. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h7a605739ad4f0709
Venue: SIGMOD
Year: 2023
Pagerank: 7.1655231e-05
Overall Rank: 3,591 | 75.94%
DOI: 10.1145/3617313

Incoming Non-self Citations Over Time

Authors

1. Lijun Chang (University of Sydney)

BibTeX Citation

@inproceedings{chang_sigmod23,
        title = {{Efficient Maximum k-Defective Clique Computation with Improved Time Complexity}},
        author = {Chang, Lijun},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3617313},
        url = {https://dl.acm.org/doi/10.1145/3617313},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,569	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD	6.0630474e-05
6,933	Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance	2025	VLDB	5.6252271e-05
8,913	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	5.2361195e-05
9,713	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.124163e-05
9,714	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.124163e-05
10,395	Efficient Querying of Maximum Connectivity-Based Quasi-Cliques in Large Graphs	2027	SIGMOD	4.9605343e-05
10,572	Querying Cohesive Subgraphs in Temporal Graphs	2026	SIGMOD	4.9605343e-05
10,684	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.9605343e-05
10,868	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB	4.9605343e-05
10,930	Maximum Defective Biclique Search in Large Bipartite Graphs	2026	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
96	Truss Decomposition in Massive Networks	2012	VLDB	0.00034261728
978	Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification	2012	VLDB	0.00012699423

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,066	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD
2	4,567	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
3	10,930	Maximum Defective Biclique Search in Large Bipartite Graphs	2026	VLDB
4	3,000	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB
5	4,155	Maximal Defective Clique Enumeration	2023	SIGMOD
6	3,597	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD
7	10,868	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB
8	8,913	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD
9	5,569	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
10	6,933	Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance	2025	VLDB