Finding a 4-clique among $k$ node groups - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T15:31:11Z https://cs.stackexchange.com/feeds/question/27552 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/27552 0 Finding a 4-clique among $k$ node groups padawan https://cs.stackexchange.com/users/17185 2014-06-09T21:34:59Z 2014-06-09T23:08:18Z <p>Given a connected graph $G = (V,E)$, assume that there are partitions $\{p_0, p_1, ..., p_k\}$.<br> Denote the partition set of a vertex $v \in V$ as $p(v)$.<br> The neighborhood of a vertex $v$ is denoted as $N(v)$</p> <p>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)$.</p> <p>Is this an NP-Hard problem?</p> <p>The most straightforward method that comes to my mind is:</p> <ul> <li>pick $v \in V$ with maximum degree.</li> <li>pick vertex $w \in N(v)$ with maximum degree</li> <li>pick vertex $u \in N(w) \bigcap N(v)$ with maximum degree</li> <li>pick vertex $x \in N(u) \bigcap N(w) \bigcap N(v)$ with maximum degree</li> </ul> <p>Is there any more efficient way to do this?</p> https://cs.stackexchange.com/questions/27552/finding-a-4-clique-among-k-node-groups/27553#27553 7 Answer by gardenhead for Finding a 4-clique among $k$ node groups gardenhead https://cs.stackexchange.com/users/18181 2014-06-09T21:46:11Z 2014-06-09T21:46:11Z <p>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.</p> <p>Second, this problem is clearly in <strong>P</strong> 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.</p> https://cs.stackexchange.com/questions/27552/finding-a-4-clique-among-k-node-groups/27557#27557 2 Answer by D.W. for Finding a 4-clique among $k$ node groups D.W. https://cs.stackexchange.com/users/755 2014-06-09T22:58:31Z 2014-06-09T23:08:18Z <p>The naive algorithm takes $O(n^4)$ time, , where $n$ is the number of vertices in the graph, as Stephen Bly explains.</p> <p>It is possible to determine whether a graph contains a $4$-clique in $O(n^{3.334})$ time. See <a href="https://cs.stackexchange.com/a/18331/755">https://cs.stackexchange.com/a/18331/755</a> 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$.</p> <p>As a trivial optimization, you can initially delete all vertices whose degree is $&lt;3$, decompose your graph into connected components, and solve the problem separately on each connected component. You can also <a href="https://en.wikipedia.org/wiki/Biconnected_component" rel="nofollow noreferrer">decompose into biconnected components</a> 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.</p>