# Clique

 Input Output

Input Description: A graph $$G=(V,E)$$.
Problem: What is the largest $$S \subset V$$ such that for all $$x,y \in S$$, $$(x,y) \in E$$?

Excerpt from The Algorithm Design Manual: When I went to high school, everybody complained about the clique'', a group of friends who all hung around together and seemed to dominate everything social. Consider a graph whose vertices represent a set of people, with edges between any pair of people who are friends. Thus the clique in high school was in fact a clique in this friendship graph.

Identifying clusters'' of related objects often reduces to finding large cliques in graphs. One example is in a program recently developed by the Internal Revenue Service (IRS) to detect organized tax fraud, where groups of phony tax returns are submitted in the hopes of getting undeserved refunds. The IRS constructs graphs with vertices corresponding to submitted tax forms and with edges between any two tax-forms that appear suspiciously similar. A large clique in this graph points to fraud.

### Related Problems

 Independent Set Vertex Cover

Go To Main Page