The clique problem is a well known NP-complete problem. The definition is short. Take an undirected graph G and choose a subset C of its vertices. If every pair of vertices in C is joined by an edge, that is, if C induces a complete graph, then C is a clique. The clique problem asks for the size of the largest clique.
There are n points on the x axis, all at different coordinates. Point i has coordinate xi and weight wi. Build a graph on these points: two different points i and j are joined by an edge if and only if wi+wj≤∣xi−xj∣.
Find the size of the largest clique in that graph.