Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
The question is: what are examples of clique problem applications? I mean, what problems can be solved by reducing to clique problem (sorry for tautology)?
All I came with is finding social cliques: groups of people who know each other personally.
I understand, that similar ideas may arise in electronics, CS (i.e., compiler design?) and probably other fields, but can't think of other interesting problems.
Would be glad to see some of them.
If you ask questions like that, I feel that the only answers you could get are problems that "reduce to the maximum clique". That would be a mistake. There are many problems in practice where finding a maximum clique is thought of as a subroutine, as it is not the most expensive part of the algorithm. Finding cliques is known to be NP-Hard, and depending on the instances it is or it is not. NP Hard does not mean anything in practice. My (reduced) own experience tells me that I would prefer 1000 times to deal with a maximum clique problem that with a TSP, or worse : an integer multiflow. Max clique is for me one of the "kind" NP-hard problems. And it means that I sometimes reduce problems to Max Clique because it can be done this way, and because I know that I will get the result fast in practice (and also because I already have all the functions available, so there is nothing new to code).
If you are interested in pratical problems that can be formulated immediately as a max clique problem, I am afraid you will not find many. Practical problems have their own aspect. However, I solved one thousand time "Max Clique" problems, often on optimization problems which would not have required it, because Max Clique is, somehow, an easy problem, and because it is so general of aspect.
I guess the last time I computed a maximum independent set (which is exactly the same) was in order to obtain a decomposition of a graph (a partition of its edges into copies of a given graph).
The graph had hundreds of nodes, and solving the max clique problem on it was very far from being the bottleneck.
Hoping it helped,
Aaron Sterling might be able to say more about this, but clique detection has traditionally been a very important tool in chemoinformatics, where one problem is to identify common substructures between a collection of molecules known to possess certain pharmacological properties. The molecules are viewed as (low treewidth) graphs and clique detection is used to find common structures (the "cliques" are defined across graphs, not within)
Finding a maximum (or at least large) clique is often useful because it gives you a lower bound on the fractional chromatic number and chromatic number of the graph in question. Actually the maximum weight of a "fractional clique" is the same as the fractional chromatic number. So for just about any colouring application you can think of, finding a large clique is at least a little bit useful (even if finding $\omega$ is not any easier than finding $\chi$).
Also, any problem on independent sets can easily be converted into a clique problem by complementing the graph at hand. And just as you can lower-bound a chromatic number by the clique number, you can upper-bound the chromatic number by the number of vertices divided by the size of a maximum stable set.
Large dense subgraphs (near-cliques) are useful in the analysis of protein-protein interaction graphs, specifically in the prediction of protein complexes.
