Finding a 4-clique among $k$ node groups

Question

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?

Answer 1

The naive algorithm takes $O(n^4)$ time, , where $n$ is the number of vertices in the graph, as Stephen Bly explains.

It is possible to determine whether a graph contains a $4$-clique in $O(n^{3.334})$ time. See https://cs.stackexchange.com/a/18331/755 for a reference to the algorithm. I suspect their techniques could be extended to solve your problem (e.g., by enumerating all such cliques, and then you could check whether any of them satisfy your partition requirement) in the same running time. However, a caution: the techniques may be somewhat theoretical. The asymptotics may mean that their algorithm only becomes faster than naive solutions for large values of $n$.

As a trivial optimization, you can initially delete all vertices whose degree is $<3$, decompose your graph into connected components, and solve the problem separately on each connected component. You can also decompose into biconnected components and solve the problem separately on each biconnected component, since any clique will necessarily be contained in a single biconnected component. Taking this even further, we can delete a vertex $v$ if $\{p(w) : w \in N(v), p(w) \ne p(v)\}$ is of size 2 or smaller (since each vertex in any clique of the form you want will pass this check), then decompose into biconnected components, and enumerate all 4-cliques of each resulting component. This optimization might improve your running time in practice, even though it doesn't make any difference to the worst-case asymptotics.

Answer 2

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.