Do the NP: find the largest clique

Question

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:

The task

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 code-golf, 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. ;)

Answer 1

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

Answer 2

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(2ⁿ) 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))
  Ç€  - call last link (1) as a monad for €ach
    Ṁ - maximum

Answer 3

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.

Answer 4

J, 36 bytes

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

Try it online!

Runs in time O(2ⁿ) 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

Answer 5

Pyth, 19 bytes

l{ef.AqLtl{T/LTTsMy

Try it here.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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

Answer 10

05AB1E, 19 bytes

怘ʒDÙg<s{γ€gQP}θÙg

Try it online!

Answer 11

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.

Answer 12

Java + Guava 23.0, 35 + 294 = 329 bytes

import com.google.common.collect.*;
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){m.add(x[0]);m.add(x[1]);}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;}

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) {
                m.add(x[0]);
                m.add(x[1]);
              }
              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) {
        s.add(t);
      }
      System.out.println(f.applyAsInt(s));
    }
  }
}

Answer 13

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!

Answer 14

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);
}

Answer 15

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.