# Background

At the time of writing this, the P vs NP problem is still unsolved, but you might have heard of Norbert Blum's new paper claiming proof that P != NP, which is already suspected to be erroneous (but we will see).

The problem discussed in this paper is the clique problem. At least that's what I read in a newspaper article, so correct me if I'm wrong, but in any case, I'd like you to write a program that solves the following variant:

Assume we have a large school with lots of students. Each of these students has some friends at this school. A clique of students is a group consisting only of students who are friends with each other member.

Your program will receive pairs of students who are friends as its input. From this information, the program must find the size of the largest clique. Students are identified by integer IDs.

If you prefer mathematical terms, this means you're fed the edges of an undirected graph, identified by two nodes each.

### Input

Your input will be a non-empty list of positive integer pairs, e.g. [[1,2],[2,5],[1,5]]. You can take this input in any sensible form, e.g. as an array of arrays, as lines of text containing two numbers each, etc ...

### Output

The expected output is a single number n >= 2: the size of the largest clique. With the example input above, the result would be 3, as all students (1, 2 and 5) are friends with each other.

### Test cases

[[1,2]]
=> 2

[[1,2],[3,1],[3,4]]
=> 2

[[1,2],[2,5],[1,5]]
=> 3

[[2,5],[2,3],[4,17],[1,3],[7,13],[5,3],[4,3],[4,1],[1,5],[5,4]]
=> 4 (the largest clique is [1,3,4,5])

[[15,1073],[23,764],[23,1073],[12,47],[47,15],[1073,764]]
=> 3 (the largest clique is [23,764,1073])

[[1296,316],[1650,316],[1296,1650],[1296,52],[1650,711],[711,316],[1650,52],
[52,711],[1296,711],[52,316],[52,1565],[1565,1296],[1565,316],[1650,1565],
[1296,138],[1565,138],[1565,711],[138,1650],[711,138],[138,144],[144,1860],
[1296,1860],[1860,52],[711,1639]]
=> 6 (the largest clique is [52,316,711,1296,1565,1650])


You can use this (stupid) reference implementation (prints extra output with -d flag) for verifying the results of other test cases.

# The rules

1. Your program doesn't need a defined result on invalid input. So you can assume that:
• you will always get at least one pair of IDs
• each pair consists of two different IDs
• no pair appears twice (swapping the places of the IDs would still be the same pair)
2. Your algorithm isn't allowed to set an upper bound on input size. Purely technical limitations and limitations set by your language/environment (like stack size, computation time, etc) are of course inevitable.
3. Standard loopholes are forbidden.
4. This is , so the shortest code, measured in bytes, wins.
5. If your algorithm has polynomial time complexity, you score -1 immediately regardless of your code size, but in that case, you might want to submit your solution somewhere else. ;)
• I can almost guarantee that there will be someone who will do it (or try to), so it would simply be safer to remove it. If you want to reward people for doing it, you can offer a bounty to the shortest answer that does it it polynomial time. Aug 30, 2017 at 11:55
• @cairdcoinheringaahing if someone does it, the -1 is well deserved ;) Aug 30, 2017 at 11:57
• @cairdcoinheringaahing If somebody managed to prove that P = NP, them having the automatic lowest score on a code golf problem is the least of our concerns. That said, Rule 5 doesn't really contribute much to the challenge, so I agree that it should be removed.
– user45941
Aug 30, 2017 at 12:17
• @Mego it merely contributes a joke and a tiny bonus to the 1M offered by CMI. Aug 30, 2017 at 12:19
• Well, I won't, in favor of the few people having some sense of "scientific humor". Please don't comment more suggestions concerning this, thanks :) Aug 30, 2017 at 12:21

# Mathematica, 34 bytes

Tr[1^#&@@FindClique[#<->#2&@@@#]]&


Basically FindClique does the job and "finds a largest clique in the graph g."
All the other stuff is converting input-list into graph

Input

[{{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}}]

Output

4

Input

[{{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565, 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}]

Output

6

thanx @Kelly Lowder for -10 bytes

• Of course Mathematica has a builtin for this. Aug 30, 2017 at 13:06
• Shave off 10 Bytes with Tr[1^#&@@FindClique[#<->#2&@@@#]]& Aug 30, 2017 at 13:30
• FindClique ಠ___ಠ Aug 30, 2017 at 13:43

# Jelly,  15 18  16 bytes

+3 bytes to fix bugs in my method.
-2 bytes thanks to miles (noting that n×(n-1)÷2 = nC2)

ẎQL©c2⁼Lȧ®
ŒPÇ€Ṁ


A monadic link taking the list of friendships (edges) and returning an integer.

Try it online! forms the power-set of the edges in memory so is inefficient both in space and time (yep,that's O(2n) folks)!

### How?

ẎQL©c2⁼Lȧ® - Link 1, isClique?: list, edges  e.g. [[1,3],[2,3],[3,4],[4,1],[4,2],[2,1]]
Ẏ          - tighten                              [ 1,3 , 2,3 , 3,4 , 4,1 , 4,2 , 2,1 ]
Q         - de-duplicate (gets unique ids)          [1,3,2,4]
L        - length (get number of people involved)  4
©       - (copy to the register)
c2     - combinations of 2 (z-choose-2)          6
L   - length (of edges)                       6
⁼    - equal?                                  1
® - recall value from register              4
ȧ  - logical and                             4
- (Note: the number of edges of a clique of size n is n*(n-1) and we're
-  guaranteed no repeated edges and that all edges are two distinct ids)

ŒPÇ€Ṁ - Link: list of lists, edges
ŒP    - power-set (all possible sets of edges (as lists))
Ṁ - maximum

• Wow, explanation when you have time please Aug 30, 2017 at 17:13
• @EriktheOutgolfer I agree. I can probably add code to salvage... Aug 30, 2017 at 17:22
• Aug 30, 2017 at 17:23
• 16 bytes Aug 30, 2017 at 23:05
• @miles - nice, I just spent a while trying to get a 15 from that, I feel like it should be possible! Aug 31, 2017 at 0:22

# Jelly, 20 bytes

ŒPẎ€µQL’=ċÐ€ẠµÐfṪQL


Try it online!

Of course this doesn't deserve the million :p

This would've beat Pyth, if not for the µ(...)µ and 2-byte Ðf.

• Amazing. I may as well give up now. Aug 30, 2017 at 12:15
• @FelixPalmen brute force :p Aug 30, 2017 at 12:16
• @EriktheOutgolfer I didn't mean the runtime of the code ;) Aug 30, 2017 at 12:18
• @FelixPalmen I mean, brute force approach doesn't need much thinking :p Aug 30, 2017 at 12:19
• Gives a MemoryError with the largest test-case :( Of course still valid, this is a "technical limitation" -- but just out of curiosity, is there a way to increase available resources with jelly? Aug 30, 2017 at 13:24

# J, 36 bytes

[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#


Try it online!

Runs in time O(2n) where n is the number of pairs.

A faster solution for 65 bytes is

3 :'$>{._2{~.@((+.&(e.&y)&<|.)@(-.,-.~)&>/#&,/:~@~.@,&.>/)~^:a:y'  Try it online! ## Explanation [:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^# Input: list of pairs # Length 2 ^ 2^n i.@ Range [0, 2^n) #:@ Binary #~ Copy ( )@ For each , Flatten ~.@ Unique #@ Length ( ) Dyad with RHS at previous and LHS as next ] Get RHS 2! Binomial coefficient, choose 2 = Equals [ Get LHS * Times ] Get RHS # Length [:>./ Reduce using maximum  # Pyth, 19 bytes l{ef.AqLtl{T/LTTsMy  Try it here. # Python 2, 180 bytes G=input() m=0 L=len for i in range(2**L(G)): u=[];p=sum([G[j]for j in range(L(G))if 2**j&i],u) for j in p:u+=[j][j in u:] m=max(m,L(u)*all(p.count(j)==L(u)-1for j in u)) print m  Try it online! -2 thanks to shooqie. -1 thanks to Mr. Xcoder. -3 thanks to recursive. • You can save two bytes by assigning len to a variable Aug 30, 2017 at 15:46 • 183 bytes. (x not in y) means 0**(x in y). Aug 30, 2017 at 17:05 • @Mr.Xcoder I knew there was a way to shorten it! Thanks! Aug 30, 2017 at 17:07 • I have never used that before, just a trick that crossed thorugh my mind a couple of days ago but couldn't find a use to it yet. Aug 30, 2017 at 17:08 • @Mr.Xcoder Doesn't matter, if it works then why not? :D BTW you can also replace 0** with -~-. Aug 30, 2017 at 17:08 # 6502 machine code (C64), 774 703 bytes (I just had to do this, my C64 can do everything ... hehe) hexdump: 00 C0 A9 00 A2 08 9D 08 00 CA 10 FA A2 04 9D FB 00 CA 10 FA 20 54 C0 B0 20 AD C9 C2 AE CA C2 20 92 C1 B0 31 8D 31 C0 AD CB C2 AE CC C2 20 92 C1 B0 23 A2 FF 20 FE C1 90 DB 20 6A C2 20 C1 C1 B0 05 20 6A C2 50 F6 A5 FB 8D D3 C2 20 43 C1 A9 CD A0 C2 20 1E AB 60 A2 00 86 CC 8E 61 C0 20 E4 FF F0 FB A2 FF C9 0D F0 10 E0 0B 10 0C 9D BD C2 20 D2 FF E8 8E 61 C0 D0 E5 C6 CC A9 20 20 D2 FF A9 0D 20 D2 FF A9 00 9D BD C2 AA BD BD C2 F0 5C C9 30 30 0E C9 3A 10 0A 9D CD C2 E8 E0 06 F0 4C D0 E9 C9 20 D0 46 A9 00 9D CD C2 E8 8E BC C0 20 EB C0 AD D3 C2 8D C9 C2 AD D4 C2 8D CA C2 A2 FF A0 00 BD BD C2 F0 0F C9 30 30 21 C9 3A 10 1D 99 CD C2 C8 E8 D0 EC A9 00 99 CD C2 20 EB C0 AD D3 C2 8D CB C2 AD D4 C2 8D CC C2 18 60 38 60 A2 FF E8 BD CD C2 D0 FA A0 06 88 CA 30 0A BD CD C2 29 0F 99 CD C2 10 F2 A9 00 99 CD C2 88 10 F8 A9 00 8D D3 C2 8D D4 C2 A2 10 A0 7B 18 B9 53 C2 90 02 09 10 4A 99 53 C2 C8 10 F2 6E D4 C2 6E D3 C2 CA D0 01 60 A0 04 B9 CE C2 C9 08 30 05 E9 03 99 CE C2 88 10 F1 30 D2 A2 06 A9 00 9D CC C2 CA D0 FA A2 08 A0 04 B9 CE C2 C9 05 30 05 69 02 99 CE C2 88 10 F1 A0 04 0E D3 C2 B9 CE C2 2A C9 10 29 0F 99 CE C2 88 10 F2 CA D0 D9 C8 B9 CD C2 F0 FA 09 30 9D CD C2 E8 C8 C0 06 F0 05 B9 CD C2 90 F0 A9 00 9D CD C2 60 85 0A A4 09 C0 00 F0 11 88 B9 D5 C2 C5 0A D0 F4 8A D9 D5 C3 D0 EE 98 18 60 A4 09 E6 09 D0 01 60 A5 0A 99 D5 C2 8A 99 D5 C3 98 99 D5 C4 18 60 A6 0B E4 09 30 01 60 BD D5 C5 C5 0B 30 09 A9 00 9D D5 C5 E6 0B D0 E9 A8 FE D5 C5 8A 29 01 D0 02 A0 00 BD D5 C4 59 D5 C4 9D D5 C4 59 D5 C4 99 D5 C4 5D D5 C4 9D D5 C4 A9 00 85 0B 18 60 A8 A5 0C D0 08 A9 20 C5 0D F0 21 A5 0C 8D 1E C2 8D 21 C2 A5 0D 09 60 8D 1F C2 49 E0 8D 22 C2 8C FF FF 8E FF FF E6 0C D0 02 E6 0D 18 60 86 0E 84 0F A5 0D 09 60 8D 54 C2 49 E0 8D 5F C2 A6 0C CA E0 FF D0 10 AC 54 C2 88 C0 60 10 02 18 60 8C 54 C2 CE 5F C2 BD 00 FF C5 0E F0 04 C5 0F D0 E0 BD 00 FF C5 0E F0 04 C5 0F D0 D5 38 60 A2 00 86 FC 86 FD 86 FE BD D5 C4 A8 A6 FE E4 FC 10 11 BD D5 C7 AA 20 2B C2 90 14 E6 FE A6 FE E4 FC D0 EF A6 FD BD D5 C4 A6 FC E6 FC 9D D5 C7 E6 FD A6 FD E4 09 D0 16 A6 FB E4 FC 10 0F A2 00 BD D5 C7 9D D5 C6 E8 E4 FC D0 F5 86 FB 60 A0 00 84 FE F0 B5  ### Online demo Usage: Start with sys49152, then enter the pairs one per line like e.g. 15 1073 23 764 23 1073 12 47 47 15 1073 764  Backsapce isn't handled during input (but if you use vice, just copy&paste your input into the emulator). Enter an empty line to start calculation. This is too large to post an explanatory disassembly listing here, but you can browse the ca65-style assembly source. The algorithm is very inefficient, it generates every possible permutation of the nodes and with each of these greedily builds a clique by checking all the edges. This allows for a space efficiency of O(n) (kind of important on a machine with this little RAM), but has horrible runtime efficiency (*). The theoretical limits are up to 256 nodes and up to 8192 edges. • -71 bytes: optimized routine for checking edges and zeropage usage There's a larger (883 805 bytes) version with better features: • visual feedback during calculation (each permutation of the nodes changes the border color) • uses bank switching to store the edges in the RAM "hidden" by the ROMs to conserve space • outputs the size and the nodes of the maximal clique found Online demo Browse source (*) The last test case takes something between 12 and 20 hours (I was sleeping when it finally finished). The other test cases finish at worst within some minutes. # Pyth, 28 bytes l{sSef<T.{SMQm.{ft{T.Cd2yS{s  Try it online ### Explanation l{sSef<T.{SMQm.{ft{T.Cd2yS{s S{sQ Get the distinct nodes in the (implicit) input. y Take every subset. m .Cd2 Get the pairs... ft{T ... without the [x, x] pairs... .{ ... as sets. f<T Choose the ones... .{ Q ... which are subsets of the input... SM ... with edges in sorted order. e Take the last element (largest clique). l{sS Get the number of distinct nodes.  # Python 3, 162 159 bytes lambda x,f=lambda x:{i for s in x for i in s}:len(f(x))if all([(y,z)in x or(z,y)in x for y in f(x)for z in f(x)if y<z])else max(c(x.difference({y}))for y in x)  Try it online! Function c takes vertices in the form of a set of sorted tuples ({(x,y),...} where x is less than y). A function called "entry" is in the TIO header to test with data in list of unsorted lists format. If clique, returns length. If not clique, returns max clique size of vertices, minus a vertice for each vertice in vertices. Exceeds time on last test case in TIO Update: "or(z,y)in x" portion added to remove dependency on sortedness "f=lambda x:{i for s in x for i in s}" instead of itertools.chain wrapped in set. -minus 3 bytes thanks to @Jonathan Allen • Aug 30, 2017 at 22:47 • Aside - you do not need to name c, so can remove c= (you'd need to put c=\ at the end of the header and place the lambda at the top of the code block for TIO) Aug 30, 2017 at 22:49 • Also you can get rid of s and replace s(...) with {*...} allowing the removal of some spaces too. Aug 30, 2017 at 22:56 • @JonathanAllan thanks, sortedness fixed Aug 31, 2017 at 2:38 # 05AB1E, 19 bytes æ€˜ʒDÙg<s{γ€gQP}θÙg  Try it online! • Aug 30, 2017 at 13:51 # Jelly, 28 bytes œ^e³;U¤ Œcç/Ðfœ|Ṣ¥/€QµÐĿ-ịḢL  Try it online! Faster solution that is able to solve the last test case in a second on TIO. • And what complexity does this have? If it's anything lower than O(2ⁿ) then it deserves$1,000,000. Aug 31, 2017 at 8:55
• @EriktheOutgolfer, you are wrong, there are algorithms which have O(1.1888ⁿ) runtime. Aug 31, 2017 at 10:15
• Adding to that, to be worth a million, the n may only appear in the bases :) Aug 31, 2017 at 11:13
• @FelixPalmen, or it can' t. Anyway, for million one of two statements must be proved. Aug 31, 2017 at 18:16
• I believe this is O(1.414^n). You can see worse performance when the input is a complete graph. Sep 1, 2017 at 6:23

# Java + Guava 23.0, 35 + 294 = 329 bytes

import com.google.common.collect.*;


This algorithm is not graphing, but instead is generating all combinations of pairs, of a specific size. I feed all pair-combinations into a multiset and check that they all have the expected size (the number of unique entries - 1). If they do, I found a clique and I go look for a bigger one.

From the Guava library, I use the new combinations method, and the tool-collection-type Multiset.

# Ungolfed

import com.google.common.collect.*;
import java.util.function.*;

public class Main {

public static void main(String[] args) {
ToIntFunction<java.util.Set<int[]>> f
= a -> {
int l = 0, o = 1, c, z = a.size();
for (; o > 0 & l < z;) {
o = 0;
c:
for (Iterable<int[]> s : Sets.combinations(a, l * (l + 1) / 2)) {
Multiset<Integer> m = TreeMultiset.create();
for (int[] x : s) {
}
c = m.elementSet().size();
for (int e : m.elementSet()) {
if (m.count(e) != c - 1) {
continue c;
}
}
l += o = 1;
break;
}
}
return z < 3 ? 2 : l;
};
int[][][] tests = {
{{1, 2}},
{{1, 2}, {3, 1}, {3, 4}},
{{1, 2}, {2, 5}, {1, 5}},
{{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}},
{{15, 1073}, {23, 764}, {23, 1073}, {12, 47}, {47, 15}, {1073, 764}},
{{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565, 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}
};
for (int[][] test : tests) {
java.util.Set<int[]> s = new java.util.HashSet<int[]>();
for (int[] t : test) {
}
System.out.println(f.applyAsInt(s));
}
}
}

• I'd be very surprised, see Finding maximum cliques in arbitrary graphs -- but it'll take me a while to analyze this code, I'm not too familiar with Java :) Aug 31, 2017 at 10:20
• @FelixPalmen I liked this challenge so my answer will stay no matter what, but I'm totally okay with removing the "-1" if it's not a polynomial complexity. Then I should probably go review some books :P Aug 31, 2017 at 10:24
• "Combination of size x is polynomial" <- are you sure? I guess that's the method used. The return value is an AbstractSet with an iterator, and the following for loop will call this iterator x! times if I'm not mistaken... Aug 31, 2017 at 11:11
• Correction: as long as x < n (with n being the complete size of the input set), it's n!/(x!(n-x)!), still not polynomial :) Aug 31, 2017 at 11:18
• @FelixPalmen You're most likely right. Also, are you saying that if I make a combinations method that's X^n (which is entirely possible), I can get it? Meanwhile, I remove my claim of the "-1". Aug 31, 2017 at 11:21

# Python 2, 102 bytes

def f(g):
x=g
while x:y=x;x=map(set,{tuple(u|v)for u in x for v in x if u^v in g})
return len(y[0])


Try it online!

# C (gcc), 790 778 757 748 731 687 642 632 bytes

typedef struct F F;typedef struct{int c,p;F**m;}g;struct F{int d;g f;};g*a,S,y,q,*x=&y,*p=&q,Q;A(g*g,F*s){g->c++[g->m=g->c-g->p?g->m:realloc(g->m,(g->p+=32)*20)]=s;}i,c[999],b,j,k,l,*s;*B(d){s=0;for(i=S.c;i--;)s=S.m[i]->d-d?s:S.m[i];!s?s=calloc(5,4),*s=d,A(&S,s):0;s=s;}F*u,*v;E(){for(i=-1;b=++i<S.c;b&&A(x,S.m[i]))for(l=x->c;k=l--*b;b&=!k)for(j=(Q=x->m[l]->f).c;j--&&(k=Q.m[j]->d-S.m[i]->d););x->c>p->c?a=x,x=p,p=a:0;x->c=0;}main(){for(;~scanf("%d %d",&a,&b)&&A(&(u=B(a))->f,v=B(b))|~A(&v->f,u););for(E();b<S.c;)c[b]>=b?c[b++]=0:E(S.m[b]=a,S.m[i]=S.m[b],a=S.m[i=b%2*c[b]++]);for(printf("%d,",i=p->c);i--;)printf(" %d",p->m[i]->d);}


This is a slightly golfed version of the reference implementation. Thanks to @jdt for -5. Try it online!

Slightly golfed less

typedef struct F F;
// student group
typedef struct{
int c, // count
p; // capacity
F**m;  // members
}g;
// student
struct F{
int d; // id
g f;   // friends
};
g*a,S,y,q,*x=&y,*p=&q,Q;
A(g*g,F*s){
g->c++[g->m=g->c-g->p?g->m:realloc(g->m,(g->p+=32)*20)]=s;
}
i,c[999],b,j,k,l,*s;
*B(d){
s=0;
for(i=S.c;i--;)
s=S.m[i]->d-d?s:S.m[i];
!s?
s=calloc(5,4),
*s=d,
A(&S,s)
:
0;
s=s;
}
F*u,*v;
E(){
for(i=-1;b=++i<S.c;b&&A(x,S.m[i]))
for(l=x->c;k=l--*b;b&=!k)
for(j=(Q=x->m[l]->f).c;j--&&(k=Q.m[j]->d-S.m[i]->d););
x->c>p->c?
a=x,
x=p,
p=a
:
0;
x->c=0;
}
main(){
for(;~scanf("%d %d",&a,&b)&&A(&(u=B(a))->f,v=B(b))|~A(&v->f,u););
for(E();b<S.c;)
c[b]>=b?
c[b++]=0
:
E(S.m[b]=a,S.m[i]=S.m[b],a=S.m[i=b%2*c[b]++]);
for(printf("%d,",i=p->c);i--;)
printf(" %d",p->m[i]->d);
}


# Pyth, 17 bytes

l{seq#.c{sT2tySSM


Try it online!

• SSM: Sort each edge, then sort the edges.

• y: Form all subsets of edges, with each subset in sorted order. The subsets are ordered by increasing length.

• t: Remove the first subset, which is the empty subset, as it would cause the program to crash.

• q#: Filter over the subsets on the following resulting in an identical list of edges as the particular subset.

• {sT: Sum the list and deduplicate, giving all vertices in any of the edges. If the subset was a clique, the vertices will be in sorted order.

• .c ... 2: All distinct pairs of vertices, in sorted order.

• e: The filter returns all cliques. Take the last clique, which is the largest clique.

• {s: Sum and deduplicate, giving the vertices in the largest clique.

• l: Length of the longest clique.

Apparently, during the brief window from May 2017 to Nov. 2017, during which this challenge was posted, sY returned an empty list, rather than 0, as it currently does, so the t` could have been removed for -1 byte. Before and after, this would cause a crash. See commit 5b973af89b, which was the most recent commit when this challenge was posted.