The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.5.1 Clique

Problem Input | Problem Output

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.


  • Cliquer - routines for clique searching (C) (rating 10)
  • RAPID - Robust and Accurate Polygon Interface detection (C,FORTRAN) (rating 9)
  • C.A.G.E.S. (C) (rating 8)
  • GOBLIN: A Graph Object Library for Network (C++) (rating 8)
  • NetworkX: High productivity software for complex networks () (rating 6)
  • Neural-Networks for Cliques and Coloring (C,Mathematica) (rating 5)

  • Recommended Books

  • None Available

    Related Links

  • Neil Sloan's clique page

    Related Problems

    Independent Set
    Vertex Cover

    This page last modified on 2008-07-10 .