2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ CLIQUE reduces to this problem so it is NP-hard in general, though this reduction cannot be applied to unit-disk graphs. $\endgroup$
    – pcpthm
    Feb 24, 2022 at 11:24
  • $\begingroup$ I see, do you mind showing me a reference for this? What is this problem I described called anyway? $\endgroup$
    – user113988
    Feb 24, 2022 at 11:29
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – pcpthm
    Feb 24, 2022 at 11:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.