Finding a 4-clique among $k$ node groups Given a connected graph $G = (V,E)$, assume that there are partitions $\{p_0, p_1, ..., p_k\}$.
Denote the partition set of a vertex $v \in V$ as $p(v)$.
The neighborhood of a vertex $v$ is denoted as $N(v)$

I need to find a 4-clique $V' = \{v_0, v_1, v_2, v_3\}$ such that the total degree of $V'$ is maximum and $\forall v_i, v_j \in V', p(v_i) \neq p(v_j)$.

Is this an NP-Hard problem?

The most straightforward method that comes to my mind is:


pick $v \in V$ with maximum degree.
pick vertex $w \in N(v)$ with maximum degree
pick vertex $u \in N(w) \bigcap N(v)$ with maximum degree
pick vertex $x \in N(u) \bigcap N(w) \bigcap N(v)$ with maximum
degree


Is there any more efficient way to do this?
First of all, the greedy strategy you outlined does not work. It may be possible that the node with highest degree is in a clique with lower total degree than the clique with the maximum degree.

Second, this problem is clearly in P because we can simply check all $\binom{n}{4} = O(n^4)$ cliques, checking they meet the partition requirement, and keeping track of the one with largest total degree. It's possible there's a more efficient algorithm though, especially considering this naive one does not use the partition information to rule out any cases.