Efficient Maximal Directed Plex Enumeration with Worst-Case Time Guarantee

Directed graphs are essential for modeling real-world networks, where edge directionality encodes critical information. Cohesive subgraphs in directed graphs, such as directed (k, ℓ)-plexes (DPlexes), are widely used in applications including community detection, anomaly detection, and functional group discovery. A DPlex is defined as a subgraph in which each vertex disconnects at most k vertices and is meanwhile not pointed to by at most ℓ vertices. However, enumerating all maximal DPlexes is computationally challenging, as finding even one maximum DPlex is NP-hard. Furthermore, existing algorithms for undirected graphs cannot be directly applied to directed graphs due to the complexities introduced by edge directionality. To address these challenges, we propose an efficient branch-and-bound algorithm, DPEnum, which incorporates two key techniques: (1) a pivot technique based on a new concept, out-degeneracy (δ), which quantifies sparseness in directed graphs and satisfies δ < n, where n is the number of vertices; and (2) a preprocessing technique that removes reducible vertices and directly identifies several maximal DPlexes. DPEnum achieves a worst-case time complexity of O^*(α_k^δ), where O^* suppresses the polynomial factors and α_k < 2, outperforming the naive O^*(2ⁿ). Additionally, we propose LDPEnum for enumerating large maximal DPlexes with at least s vertices, which uses the upper-bounding technique to prune search branches. Extensive experiments on real-world datasets show that our algorithms achieve up to four orders of magnitude speedup compared to the baseline.