# Maximum Edges Subgraph

Given an (undirected) graph $$G = (V,E)$$ with $$|V| = 2n$$, what is the complexity of the problem of finding the subgraph $$G' = (V',E')$$ with $$V' \subset V, |V'| = n$$, such that the number of edges $$|E'| = |\{(v,u) \in E\ |\ v,u \in V'\}|$$ is maximized?

I feel like this is similar to Max-Bisection problem but focuses on the number of edges in a partition rather than edges between partitions, so maybe it is also NP-hard.

I'm particularly interested in the complexity of this problem for unit disks graphs, whether it is NP-hard, but any pointers or references to this kind of problem would be appreciated.

• CLIQUE reduces to this problem so it is NP-hard in general, though this reduction cannot be applied to unit-disk graphs. Feb 24, 2022 at 11:24
• I see, do you mind showing me a reference for this? What is this problem I described called anyway? Feb 24, 2022 at 11:29
• The problem is a special case ($k=n/2$) of Densest $k$-Subgraph. Reduction of $k$-Clique is: add $k$ isolated vertices and a complete graph of size $n-k$ connected to all original vertices, so the density is maximal if and only if it is a $k$-Clique in the original graph + added $K_{n-k}$. Feb 24, 2022 at 11:38