How to find total number of friends groups

Question

I have a friendship graph as follows

I want to find all the possible group of friends. What is the best algorithm to find these grouping. For example in this graph , possible friendship groups are as follows: 1,2,3,4,12,13,23,123,14,143,124,1234

If I use brute-force algorithm (starting from each vertex and do this 4 times), it generates lots of duplicates.

note that the most interesting question would be, how to find a linear algorithm which introduces the fewest number of errors ( and defining an error count function ) — , Sep 28 '16 at 15:54
@igael I would prefer to store it as adjacency list because graph could be sparse in most cases. — NARAYAN CHANGDER, Sep 28 '16 at 16:10
no problem, provide a format ( while the question remains : *"find the number"* and not *"enumerate them"* ) — , Sep 28 '16 at 16:21

xenteros · Answer 1 · 2016-09-28T12:14:19.227

1

According to the Wikipedia it's NP-complete so you can only use brute-force for detecting such sets. The problem is called Clique problem and is one of first identified NP-complete problems.

edited Sep 28 '16 at 12:14

answered Sep 28 '16 at 12:06

xenteros

15,586
12
56
91

Yes it is NPH. I am looking for faster algorithm for sparse graph. – NARAYAN CHANGDER Sep 28 '16 at 12:12
Thanks I will check it – NARAYAN CHANGDER Sep 28 '16 at 12:31
1

According to the OP, `1234` is also a friendship group, but that is not a complete subgraph. OP's problem seems to me to find all possible connected components – Ankit Sultana Sep 28 '16 at 12:34
@NARAYANCHANGDER is 1234 ok? – xenteros Sep 28 '16 at 12:37
yes 1234 is a part of solution. In given graph the answer is 1,2,3,4,12,13,23,123,14,143,124,1234. – NARAYAN CHANGDER Sep 28 '16 at 13:19
@NARAYANCHANGDER how is 4 friend with 3? – xenteros Sep 28 '16 at 13:19
@bk2dcradle the problem is , if we count all possible connected components then for 1-2-3-1 we will get 123 as well as for 1-2-3 we will again get 123. hence, duplicate occurs. – NARAYAN CHANGDER Sep 28 '16 at 13:20
@xenteros 4 is not direct friend of 3 but if common friend 1 joins then 143 form a group. – NARAYAN CHANGDER Sep 28 '16 at 13:21
@xenteros if we pick 1, adjacent of 1 are 2,3 and 4 now 34 is a subset of 234. I posted the same thing in your previous answer but you deleted it. Could you please elaborate again your procedure. I am sorry if I could not get your answer. Thanks – NARAYAN CHANGDER Sep 28 '16 at 13:28

How to find total number of friends groups

1 Answers1