Clique Identification Task

See: Clique Potential, Maximal Clique Task, Clique Problem.

---

---

References

2009

• http://en.wikipedia.org/wiki/Clique_problem
  • In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements that are pairwise connected.
  • For example, the maximal clique problem arises in the following real-world setting. Consider a social network, where the graph’s vertices represent people, and the graph’s edges represent mutual acquaintance. To find a largest subset of people who all know each other, one can systematically inspect all subsets, a process that is too time-consuming to be practical for social networks comprising more than a few dozen people. However, despite many attempts to find better algorithms for this problem, no significantly better approach is known. Instead, much of the theory about the clique problem is devoted to identifying special types of graph that admit efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation. Along with its applications in social networks, the clique problem also has many applications in bioinformatics and computational chemistry.
  • Clique problems include:
    • finding the maximum clique (a clique with the largest number of vertices),
    • finding a maximum weight clique in a weighted graph,
    • listing all maximal cliques (cliques that cannot be enlarged)
    • solving the decision problem of testing whether a graph contains a clique larger than a given size.
  • These problems are all hard: the clique decision problem is NP-complete (one of Karp's 21 NP-complete problems), the problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate, and listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Nevertheless, there are a number algorithms for these problems that run in exponential time or that handle certain more specialized input graphs in polynomial time.

---