2026-08-15T23:21:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25154 2026-02-09T08:17:57Z ddc:004 open_access

Efficient Enumeration of k-Plexes and k-Defective Cliques Jiddou, Mohamed Manoussakis, George Parameterized complexity enumeration algorithms maximal cliques enumeration We investigate the enumeration of dense subgraphs under two well-known relaxations of cliques: k-plexes and k-defective cliques. Our main contribution is a family of algorithms with improved worst-case and output-sensitive complexities, driven by a decomposition technique based on graph degeneracy. We first propose a worst-case output-size near-optimal algorithm to enumerate all maximal k-plexes of size at least 2k-1, achieving a total time complexity of 𝒪(n(dk)³ 2^d Δ^k), where d is the degeneracy and Δ the maximum degree of the input graph. We then refine this result to obtain a fixed-parameter tractable output-sensitive algorithm with complexity 𝒪(α f(k) p(dΔ)), where α is the number of solutions, f(k) is an arbitrary function of k, and p is a polynomial. We then extend this framework to the enumeration of k-defective cliques and also show a linear-time O(n) algorithm for the enumeration of 2-plexes for graphs with bounded degeneracy. To the best of our knowledge, these complexities are competitive with or better than the current state of the art. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohamed Jiddou and George Manoussakis 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.22 urn:nbn:de:0030-drops-251545 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.22 eng https://creativecommons.org/licenses/by/4.0/legalcode