DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2025.22

Efficient Enumeration of k-Plexes and k-Defective Cliques

Authors: Mohamed Jiddou and George Manoussakis

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract

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.

Cite as

Mohamed Jiddou and George Manoussakis. Efficient Enumeration of k-Plexes and k-Defective Cliques. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jiddou_et_al:LIPIcs.IPEC.2025.22,
  author =	{Jiddou, Mohamed and Manoussakis, George},
  title =	{{Efficient Enumeration of k-Plexes and k-Defective Cliques}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.22},
  URN =		{urn:nbn:de:0030-drops-251545},
  doi =		{10.4230/LIPIcs.IPEC.2025.22},
  annote =	{Keywords: Parameterized complexity, enumeration algorithms, maximal cliques enumeration}
}

Search Results

Documents authored by Jiddou, Mohamed

Efficient Enumeration of k-Plexes and k-Defective Cliques

Abstract

Cite as

Thanks for your feedback!

Could not send message