Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance

Download PDF

Abstract

𝑘-defective clique is a relaxation of the well-studied clique structure, by allowing up-to 𝑘 edges missing from a clique. The problem of finding a 𝑘-defective clique with the largest number of vertices, although being NP-hard, has been receiving increasing interests recently, with advancements in both the theoretical time complexity and practical efficiency. The state-of-the-art time complexity is O∗(𝛾ⁿₖ), where O∗ ignores polynomial factors, 𝑛 is the number of 𝑘 vertices in the input graph 𝐺, and 𝛾ₖ < 2 is a constant that only depends on 𝑘. In this paper, we first prove, through a more refined and non-trivial analysis, that the time complexity of an existing algorithm can actually bebounded by O∗(𝛾𝑛 ),where 𝛾ₖ₋₁ <𝛾ₖ. 𝑘−1Then, by utilizing the diameter-two property of large 𝑘-defective cliques, we show that for graphs with maximum 𝑘-defective clique sizes 𝜔𝑘(𝐺) ≥ 𝑘 + 2, a maximum 𝑘-defective clique can be found in O∗((𝛼Δ)ᵏ⁺²𝛾ᵅₖ₋₁ ) time when using the degeneracy parameteri- 𝑘−1 zation 𝛼 and in O∗((𝛼Δ)ᵏ⁺²(𝑘 + 1)𝛼+k+1−𝜔ₖ(𝐺)) time when using thedegeneracy-gapparameterization 𝛼+𝑘+1−𝜔ₖ(𝐺);here,𝛼 and Δ are the degeneracy and maximum degree of 𝐺 , respectively. Note that, most real graphs satisfy 𝜔𝑘 (𝐺) ≥ 𝑘 + 2 and 𝛼 ≪ 𝑛. Lastly, to improve the practical performance, we design a new degree- sequence-based reduction rule that can be efficiently applied, and theoretically demonstrate its effectiveness compared with the exist- ing reduction rules. Extensive empirical studies on three benchmark graph collections, containing 290 graphs in total, show that our algorithm is also practically efficient, by outperforming all existing algorithms by several orders of magnitude. We remark that our proving techniques for reducing the base from 𝛾ₖ to 𝛾ₖ₋₁ and our general principle of designing a new reduction rule may also be beneficial to other problems.