5
$\begingroup$

Definition. Given an undirected graph $G = (V,E)$, a $k$-plex is a subgraph $G'$ of $G$ such that each vertex in $G'$ is connected to at least $s - k$ other vertices in $G'$, where $s$ is the # of vertices in $G'$.

Computing the maximum $k$-plex is NP-hard since a clique is just a $1$-plex. In my understanding, such a reduction only shows the hardness of computing the maximum $1$-plex. Moreover, when $k=|V|$, the problem becomes trivial because any subgraph of $G$ is a $k$-plex then.

Question. Is the maximum $2$-plex still NP-hard to be computed? Or more generally, given a graph $G = (V,E)$, what is the maximum $k$ such that the maximum $1$-plex, the maximum $2$-plex, $\cdots$ and the maximum $k$-plex are all NP-hard to be computed?

This question seems interesting but I did not come up with a reduction from any other NP-complete problem, even from the MaxClique.

$\endgroup$
4
$\begingroup$

Lemma. If a graph has a $k$-plex on $m$ vertices, then it has a clique on $\frac m{k+1}$ vertices.

Proof. Greedily pick the vertices of the clique from the $k$-plex.

Since a clique on $m$ vertices is also a $k$-plex on $m$ vertices (for any $k$), we get that the size of the maximum $k$-plex is a $k$-approximation of the size of the maximum clique. Since clique is hard to approximate with an $O(n^{1-\epsilon})$ factor, determining the largest $k$-plex is also hard for any $k=O(n^{1-\epsilon})$.

$\endgroup$
4
$\begingroup$

The property of being a $k$-plex is hereditary, that is, closed under vertex deletion. Therefore, the NP-hardness for every fixed $k$ follows from a general result of Lewis and Yannakakis (http://dx.doi.org/10.1016/0022-0000(80)90060-4) which states that for every hereditary property $\Pi$ it is NP-hard to find, given a graph $G$, an induced subgraph of $G$ with a maximum number of vertices that fulfills $\Pi$.

A direct NP-hardness reduction is presented in a paper of Butenko et al. (http://dx.doi.org/10.1287/opre.1100.0851). There is quite a large body of work on the complexity of the Maximum $k$-Plex problem (sometimes the problem is called $s$-plex in the literature since $k$ is often used for the number of vertices in the solution).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy