Finding the maximum no. of people who get along in a group [closed]

Question

Suppose that there are 15 people in a room. Assume that each person gets along with other people in the room (but not everyone). (Note that the "feeling is mutual" between any two people who are thought to respect each other.)

And suppose your goal is to assemble a list (or lists, because there can be more than one optimal solution) which consists of the largest number of people who all get along with each other.

This diagram shows an example scenario. The first column is just there to enumerate the people in the room. (Only view it as an index.) The "main diagonal" along with random entries are blank, signifying the instances when any two given people DO NOT get along. (That is, with the main diagonal's entries being blank, we make the assumption that "it doesn't count for an individual to get along with hisself or herself.) For example, the first row says that "person 1 gets along with everyone except for persons 5 and 6. The second column (which contains all 1's except in rows 5 and 6) agrees with this.

One optimal solution for this example is {3,4,5,6,7,10,11,15}.

Now in general, if we have an unlimited number of people to consider (not just 15), what is the time complexity of finding all possible lists of numbers which represent people who (mutually) get along with each other? (Because obviously if we find all possible "get along lists" then we just use a simple SORT routine to find the list(s) containing the most numbers.)

Answer 1

Convert your array to a zero-one array where $a_{ij}=1$ if persons $i,j$ get along, else it is zero. Let this be the adjacency matrix of an undirected graph $G$ where the vertices are the persons in your formulation.

What you are asking about is how to find the maximal cliques (maximal connected subgraphs) of $G.$

This is in general a very difficult problem, but there is an immense literature on it.