Efficient Enumeration of $𝒌$-Plexes and $𝒌$-Defective Cliques

Let $C$ be a maximal $k$-plex in $G$ with $|C|\ge 2k-1$, and let $i\in [n]$ be the smallest index such that $v_i\in C$. By Lemma 4, the subgraph $G[C]$ has diameter at most two and contains $v_i$, which implies that every vertex $u\in C\setminus \{v_i\}$ is at distance at most two from $v_i$. Therefore, each such vertex $u$ is either a neighbor of $v_i$ or is at distance two from $v_i$, so by the definition of $G_i$, it follows that $C\subseteq V(G_i)$.

To show uniqueness, suppose for contradiction that there exists an index $j\ne i$ such that $C\subseteq V(G_j)$ and $v_j\in C$. If , then $v_j\in C$, which contradicts the minimality of $i$. If $j>i$, then since $C\subseteq V(G_j)$, we must have $v_i\in V(G_j)$. By definition, $V(G_j)=\{v_j\}\cup N(v_j)\cup N_2(v_j)$, so $v_i\in N(v_j)\cup N_2(v_j)$. However, this is impossible, since all vertices in $N(v_j)\cup N_2(v_j)$ have indices strictly greater than $j$, whereas . Therefore, such an index $j$ cannot exist, proving the uniqueness. $◀$

Suppose that $C$ is a maximal $k$-plex of size at least $2k-1$ in $G_i$, for some $i\in [n]$, but that $C$ is not maximal in $G$. Then there exists a set $S\subseteq V(G)\setminus C$ such that the subgraph $G[C\cup S]$ is a $k$-plex of size at least $2k-1$, and is maximal in $G$. Let $v_j\in S$ be the vertex with the smallest rank according to the ordering $\sigma$.

If $j>i$, then since $G[C\cup S]$ has a diameter of at most 2, the vertex $v_j$ must be at distance at most 2 from every vertex in $C$. By the definition of $G_i$, this means $v_j\in V(G_i)$, so $C\cup \{v_j\}\subseteq V(G_i)$ forms a $k$-plex of size at least $2k-1$ in $G_i$, contradicting the maximality of $C$ in $G_i$. Therefore, it must be that . Now set $C^{\prime }=C\cup S$, which by hypothesis is a $k$-plex of size at least $2k-1$, maximal in $G$. Since $v_j\in C^{\prime }\setminus C$, we have $C⊊C^{\prime }$, and $C^{\prime }\subseteq V(G_j)$ with . This completes the first implication.

Conversely, suppose that there exists a maximal $k$-plex $C^{\prime }$ of size at least $2k-1$ in $G$, included in a subgraph $G_j$ for some , such that $C⊊C^{\prime }$. Then, by definition, $C$ cannot be maximal in $G$, which completes the proof. $◀$

First observe that, by Lemma 6, the $k$-plex $C$ is well defined and $K⊊C$. Let $v_i$ be the vertex of $K$ with the smallest index in ${\sigma }_G$; thus, $v_i$ appears first in $W(K)$. Since $K⊊C$, we also have $v_i\in C$.

Assume for contradiction that $W(K)$ is not a proper suffix of $W(C)$. This means that there exists at least one vertex $x\in C\setminus K$ which appears after $v_i$ in $W(C)$. Otherwise, $W(K)$ would indeed be a proper suffix of $W(C)$. Let $v_j$ denote the vertex of $C$ with the smallest index in ${\sigma }_G$; according to Lemma 6, we have . Since any subset of a $k$-plex is itself a $k$-plex, it follows that $K\cup \{x\}$ is a $k$-plex in $G_j$. Moreover, as $K$ has size at least $2k-1$, so does $K\cup \{x\}$. By Lemma 4, $K\cup \{x\}$ must have diameter at most $2$, implying $x\in N(v_i)\cup N_i^2(v_i)$. Thus, $K\cup \{x\}$ is a $k$-plex of size at least $2k-1$ in $G_i$, which contradicts the maximality of $K$ in $G_i$. $◀$

Let $C$ be a maximal $k$-plex in $G$ of size at least $2k-1$, and let $\sigma$ be a degeneracy ordering of $G$ with degeneracy $d$. Let $v_i$ be the vertex of $C$ with the smallest rank in ${\sigma }_G$. By Lemma 5, $C\subseteq V(G_i)$. Therefore, $C$ can contain at most $k-1$ vertices in $N_i^2(v_i)$; otherwise, the number of $v_i$’s non-neighbors would exceed the allowed $k-1$, contradicting the definition of a $k$-plex. Moreover, by the definition of degeneracy, $v_i$ has at most $d$ neighbors in $V_i$, so at most $d$ vertices in $N_i(v_i)$ can belong to $C$. Since $N_i(v_i)$ and $N_i^2(v_i)$ are disjoint, we obtain the following inequality: $|C|\le d+k$. $◀$

Let $G$ be a $d$-degenerate graph and $\sigma$ a degeneracy ordering of its vertices. Denote by $𝒫([d])$ the set of all subsets of $[1,d]$, and by ${𝒫}_{k-1}$ the set of all subsets of $N_i^2(v_i)$ of size at most $k-1$. Let ${\alpha }_i$ denote the number of maximal $k$-plex of size at least $2k-1$ in the graph $G_i$, for $i\in [n]$, containing $v_i$, and let $\alpha$ be the number of maximal $k$-plex of size at least $2k-1$ in the graph $G$. According to Lemma 5, for every maximal $k$-plex of size at least $2k-1$ in $G$, there exists $i\in [n]$ such that $C\subseteq V(G_i)$ and $v_i\in C$. Furthermore, by Lemma 6, there may exist a maximal $k$-plex of size at least $2k-1$ in $G_i$ containing $v_i$ (for some $i\in [n]$), which are not maximal in $G$. It follows that $\alpha \le {\sum }_{i=1}^n{\alpha }_i$.

Let $i\in [n]$. By definition of $\sigma$, the vertex $v_i$ has at most $d$ neighbors of higher rank (i.e., greater index) in $\sigma$; in other words, the cardinality of $N(v_i)$ is at most $d$. Each vertex in $N(v_i)$ is adjacent to at most $\mathrm{\Delta }$ vertices in $N_{2i}(v_i)$, so $|N_{2i}(v_i)|\le d\mathrm{\Delta }$. Moreover, by arguments analogous to those in the proof of Lemma 8, any maximal $k$-plex of size at least $2k-1$ in $G_i$ containing $v_i$ contains at most $d$ vertices from $N(v_i)$ and at most $k-1$ vertices from $N_{2i}(v_i)$. Thus, for $k$-plex $C$, there exist two sets $S_1\subseteq 𝒫([d])$ and $S_2\subseteq {𝒫}_k$ such that $C=\{v_i\}\cup S_1\cup S_2$. Therefore, we obtain the following inequality: ${\alpha }_i\le |𝒫([d])\times {𝒫}_{k-1}|$, with $|{𝒫}_{k-1}|={\sum }_{r=0}^{k-1}\left(\genfrac{}{}{0pt}{}{d\mathrm{\Delta }}{r}\right)$ and $|𝒫([d])|=2^d$. As ${\sum }_{r=0}^{k-1}\left(\genfrac{}{}{0pt}{}{d\mathrm{\Delta }}{r}\right)\in 𝒪(k{\mathrm{\Delta }}^{k-1})$, it follows that $|𝒫([d])\times {𝒫}_{k-1}|\in 𝒪(k{2}^d{\mathrm{\Delta }}^{k-1})$, and thus ${\alpha }_i\in 𝒪(k{2}^d{\mathrm{\Delta }}^{k-1})$. Consequently, $\alpha \le {\sum }_{i=1}^n{\alpha }_i$ which is bounded by $𝒪(nk{2}^d{\mathrm{\Delta }}^{k-1})$. $◀$

Let $G=(V,E)$ be a simple, undirected, $d$-degenerate graph with maximum degree $\mathrm{\Delta }$, and let $\sigma =(v_1,v_2,\mathrm{\dots },v_n)$ be a degeneracy ordering. Set $S_1=\{v_i:1\le i\le n-d-\mathrm{\Delta }\}$, $S_2=V\setminus S_1$, and consider a partition $S_2=S_2^1\cup S_2^2$ such that $|S_2^1|=d$, $G[S_2^2]$ is a clique, and $S_1$ is an independent set.

For every $i\in \{1,\mathrm{\dots },n-d-\mathrm{\Delta }\}$, let $G_i$ be the subgraph induced by the vertex set $\{v_i\}\cup S_2$, where $v_i$ is adjacent to all vertices in $S_2^1$, and $v_i$ is not adjacent to any vertex in $S_2^2$. Let ${\alpha }_i$ denote the number of maximal $k$-plexes of size at least $2k-1$ in $G_i$, and let $\alpha$ denote the number of such $k$-plexes in $G$. For $i\in \{1,\mathrm{\dots },n-d-\mathrm{\Delta }\}$, Consider $C=\{v_i\}\cup C_1\cup C_2$, where $C_1$ is a maximal clique of $S_2^1$ and $C_2\subseteq S_2^2$ is a subset of cardinality $k-1$. We show that $C$ is a maximal $k$-plex of size at least $2k-1$ in $G_i$. First, $C\subseteq V(G_i)$, and since $v_i\notin C_2$, we have $|C|=d+k\ge k+2$ by Lemma 8. Moreover, since $S_2^2$ induces a clique and $v_i$ is not adjacent to any vertex in $S_2^2$, the subgraph $G_i[C]$ missing exactly $k-1$ edges, namely those between $v_i$ and each vertex of $C_2$. Thus, $C$ is indeed a $k$-plex in $G_i$.

Assume for contradiction that $C$ is not maximal in $G$; then there exists $u\in V\setminus C$ such that $C\cup \{u\}$ is a $k$-defective clique. Since $|S_2^1|=d$, then $v_i$ and $u$ are not adjacent; hence, $v_i$ has exactly $k$ non-neighbors in $G[C\cup \{u\}]$, contradicting the definition of a $k$-plex. $C$ is therefore maximal both in $G$ and in $G_i$.

For every choice of a pair $(C_1,C_2)$, we obtain a distinct maximal $k$-plex. There are exactly $3^{d/3}$ maximal cliques in $S_2^1$ and $\left(\genfrac{}{}{0pt}{}{|S_2^2|}{k-1}\right)=\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{k-1}\right)$ subsets of size $k$ in $S_2^2$ (since $|S_2^2|=\mathrm{\Delta }$). Thus, we obtain $3^{d/3}\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{k-1}\right)$ maximal $k$-plexes of the form $C$. Therefore, for each $i\in \{1,\mathrm{\dots },n-d-\mathrm{\Delta }\}$, we have ${\alpha }_i\ge 3^{d/3}\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{k-1}\right)$. Moreover, since $S_1$ is an independent set, every maximal $k$-plex of size at least $2k-1$ in $G_i$ is also maximal in $G$, for each such $i$.

Finally, we obtain: $\alpha ={\sum }_{i=1}^{n-d-\mathrm{\Delta }}{\alpha }_i\ge (n-d-\mathrm{\Delta })3^{d/3}\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{k-1}\right)$ Now, since $\left(\genfrac{}{}{0pt}{}{\mathrm{\Delta }}{k-1}\right)\in \mathrm{\Omega }({\mathrm{\Delta }}^{k-1})$, it follows that $\alpha \in \mathrm{\Omega }((n-d-\mathrm{\Delta })3^{d/3}{\mathrm{\Delta }}^{k-1}).$$◀$

Let $C\subseteq V(G_i)$ be a $k$-plex of size at least $2k-1$. To check whether $C$ is maximal in $G_i$, it suffices, by Definition 2, to verify whether there exists a vertex $u\in V(G_i)\setminus C$ such that $C\cup \{u\}$ is still a $k$-plex in $G_i$. The cardinality of $V(G_i)$ is bounded by $1+d+d\mathrm{\Delta }$ (i.e., $O(d\mathrm{\Delta })$), since $G_i$ contains at most $d$ direct neighbors of $v_i$ and $d\mathrm{\Delta }$ vertices at distance two. Therefore, the size of $V(G_i)\setminus C$ is also $O(d\mathrm{\Delta })$. For each $u\in V(G_i)\setminus C$, one needs to check whether $|C\cup \{u\}|-{\mathrm{deg}}_{G[C\cup \{u\}]}(v)\le k-1$, for each $v\in C\cup \{u\}$, which can be done in $O(d+k)$ time, since $|C|\le d+k$ by Lemma 4. If this condition holds for every $v\in C\cup \{u\}$), then $C$ is not maximal in $G_i$. Therefore, the maximality of a $k$-plex can be verified in $O((d+k)d\mathrm{\Delta })$ time. $◀$

Let $m_i$ denote the number of maximal $k$-plexes of size at least $2k-1$ in $G_i$, $i\in [n]$ that are also maximal in $G$, and let $N{m}_i$ be the number of such $k$-plexes in $G_i$ that are not maximal in $G$. Thus, ${\alpha }_i=m_i+N{m}_i$.

Let $C$ be a maximal $k$-plex of size at least $2k-1$ in $G$. By Lemma 8, the number of vertices in $C$ is at most $d+k$. Consequently, $W(C)$, the word formed by the vertices of $C$ ordered according to ${\sigma }_G$, can have at most $d+k-1$ proper suffixes.

Moreover, by Corollary 7, every maximal $k$-plex $K$ of size at least $2k-1$ in some subgraph $G_i$, $i\in [n]$, that is not maximal in $G$, satisfies $W(K)$ being a proper suffix of $W(C)$ for some maximal $k$-plex $C$ in $G$. Therefore, ${\sum }_{i=1}^{n}N{m}_i\le (d+k-1)\alpha$, and it follows that ${\sum }_{i=1}^n{\alpha }_i={\sum }_{i=1}^n(m_i+N{m}_i)\le {\sum }_{i=1}^n{m}_i+{\sum }_{i=1}^{n}N{m}_i\le \alpha +(d+k-1)\alpha =(d+k)\alpha$. $◀$

Since every k-defective clique is a $(k+1)$-plex, the enumeration algorithm for maximal $(k+1)$-plexes can be leveraged to enumerate all maximal k-defective cliques. Specifically, Algorithm 2 is applied to enumerate all maximal $(k+1)$-plexes of size at least $2k+1$. Immediately after Line 11 of Algorithm 2, an additional verification step is incorporated to test whether the current $(k+1)$-plex is also a $k$-defective clique. This verification consists in counting the number of missing edges in the subgraph induced by the current $(k+1)$-plex. It can be performed in $𝒪({(d+k)}^2)$ time. According to Theorem 16, Algorithm 2 enumerates all maximal $(k+1)$-plexes of size at least $2k+1$ in $𝒪\left(n{(dk)}^3{2}^d{\mathrm{\Delta }}^{k+1}\right)$ time. Since the additional verification for the $k$-defective clique condition is performed once per candidate and requires at most $𝒪({(d+k)}^2)$ time, the total time per candidate becomes $𝒪\left({(dk)}^3{(d+k)}^2{2}^d{\mathrm{\Delta }}^{k+1}\right)=𝒪\left({(dk)}^5{2}^d{\mathrm{\Delta }}^{k+1}\right)$. Finally, by Lemma 9, Lemma 10, and Corollary 7, the suffix-tree-based filtering guarantees that only the k-defective cliques which are maximal in $G$ are retained, and that no duplicates are produced. Hence, this approach yields an exhaustive, duplication-free enumeration of all maximal k-defective cliques of size at least $k+2$ in $G$, with overall time complexity $𝒪\left({(dk)}^5{2}^d{\mathrm{\Delta }}^{k+1}\right)$. $◀$

Let $\alpha$ denote the number of maximal $k$-defective cliques of size at least $K+2$ of $G$, and let ${\alpha }_i$ denote the number of maximal $k$-defective cliques of size at least $k+2$ in the subgraph $G_i$, $i\in [n]$. In [10], Algorithm 3 enumerates all maximal $k$-defective cliques of size at least $k+2$ in a graph $G$, with a delay of $𝒪\left(n^2{N}_m^{2k+1}/4^k\right)$ between two outputs, where $n$ is the order of the graph and $N_m$ denotes the size of the largest maximal $k$-defective clique in $G$. This algorithm can be adapted to our decomposition into subgraphs $G_i$, which allows for a significant complexity improvement to $𝒪\left(n{(d\mathrm{\Delta })}^2{(d+k)}^{2k+2}/4^k\right)$, where $d$ is the degeneracy of the input graph and $n$ its order. More concretely, the approach consists in applying Algorithm 3 to each subgraph $G_i$, $i\in [n]$. For every $i\in [n]$, the order of $G_i$ is $\mathrm{\Theta }(d\mathrm{\Delta })$, where $\mathrm{\Delta }$ is the maximum degree of $G$. Moreover, Lemma 4 ensures that the size of the largest maximal $k$-defective clique of size at least $k+2$ in $G_i$ is at most $d+k+1$. Thus, the enumeration in each $G_i$ can be performed with a polynomial delay of $𝒪\left({(d\mathrm{\Delta })}^2{(d+k)}^{2k+1}/4^k\right)$. Consequently, the enumeration in each $G_i$ can be performed with a polynomial delay between two outputs in $𝒪\left({(d\mathrm{\Delta })}^2\frac{{(d+k)}^{2k+1}}{4^k}\right)$. Since there are ${\alpha }_i$ such cliques in $G_i$, for $i\in [n]$, the enumeration in $G_i$ takes $𝒪\left({\alpha }_i{(d\mathrm{\Delta })}^2\frac{{(d+k)}^{2k+1}}{4^k}\right)$ time. Moreover, by applying exactly the same arguments used in the proof of Lemma 12, it can be shown that ${\sum }_{i=1}^n{\alpha }_i\le (d+k-1)\alpha$. It follows that the enumeration over all subgraphs $G_i$ can be performed in total time $𝒪\left({(d\mathrm{\Delta })}^2\frac{{(d+k)}^{2k+1}}{4^k}{\sum }_{i=1}^n{\alpha }_i\right)\in 𝒪\left(\alpha {(d\mathrm{\Delta })}^2\frac{{(d+k)}^{2k+2}}{4^k}\right)$. To ensure that only cliques which are maximal in $G$ are retained, one can use a similar filtering procedure as in Algorithm 2, which requires $𝒪\left(\alpha (d+k)\right)$ time, as established in the proof of Theorem 16. Therefore, by Lemma 5, Lemma 6, and Corollary 7, this approach yields an exhaustive, duplication-free enumeration of all maximal $k$-defective cliques of size at least $k+2$ in $G$ with$𝒪\left(\alpha {(d\mathrm{\Delta })}^2\frac{{(d+k)}^{2k+3}}{4^k}\right)$ time. $◀$