<p>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)</p>

CC BY-SA 3.0
2011-10-06T15:29:44.120Z
2011-10-06T15:29:44.120Z
Suresh Venkat
<p>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).</p>

<p>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.</p>

<p>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).</p>

<p>The graph had hundreds of nodes, and solving the max clique problem on it was very far from being the bottleneck. </p>

<p>Hoping it helped,</p>

CC BY-SA 3.0
2011-10-06T11:16:54.340Z
I see. It helped, but may you point some extra problems, where Max Clique was used as subroutine?
Mixo123
CC BY-SA 3.0
2011-10-06T13:01:56.550Z
I would deal with metric TSP rather than with clique. AFAIK, there are graphs with 100 vertices, where the maximum clique size is unknown.
ilyaraz
CC BY-SA 3.0
2011-10-07T08:10:26.550Z
Oh. Metric TSP ? Never had to deal with this one. Which software do you use for that ? Concorde ? I'm using Sage, which in turn uses either Cliquer (for max cliques) or LP formulations (for TSP, cliques, and many others)
Nathann Cohen
CC BY-SA 3.0
2013-08-28T02:11:09.597Z
@ilyaraz do you have a reference for those open instances with 100 vertices?
Austin Buchanan
CC BY-SA 3.0
2013-08-28T04:01:07.387Z
@AustinBuchanan try to look at this paper: http://link.springer.com/article/10.1007%2Fs10732-012-9196-4 (I might be easily wrong though).
ilyaraz
CC BY-SA 3.0
2011-10-06T09:54:21.807Z
2011-10-06T09:54:21.807Z
Nathann Cohen
<p>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$).</p>

<p>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.</p>

<p>Large dense subgraphs (near-cliques) are useful in the analysis of protein-protein interaction graphs, specifically in the prediction of protein complexes.</p>

CC BY-SA 3.0
2011-10-06T17:50:02.427Z
2011-10-06T17:50:02.427Z
Andrew D. King
<p>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)?</p>

<p>All I came with is finding social cliques: groups of people who know each other personally.</p>

<p>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.</p>

<p>Would be glad to see some of them.</p>

CC BY-SA 3.0
2011-10-07T04:07:30.703Z
have you read this? http://en.wikipedia.org/wiki/Maximum_clique#Applications
didest
<ds.algorithms><graph-theory><application-of-theory><clique>
Maximum-clique practical applications
Mixo123
# Maximum-clique practical applications

(Asked by: username_0 on 2011-10-06)

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.

**Tags:** ds.algorithms, graph-theory, application-of-theory, clique

> **Comments:**
> **username_1**: have you read this? http://en.wikipedia.org/wiki/Maximum_clique#Applications  

---

## 3 answers

### Answer by username_2 on 2011-10-06. Score: 3

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)


---

### Answer by username_3 on 2011-10-06. Score: 3

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,

> **Comments:**
> **username_0**: I see. It helped, but may you point some extra problems, where Max Clique was used as subroutine?  
> **username_4**: I would deal with metric TSP rather than with clique. AFAIK, there are graphs with 100 vertices, where the maximum clique size is unknown.  
> **username_3**: Oh. Metric TSP ? Never had to deal with this one. Which software do you use for that ? Concorde ? I'm using Sage, which in turn uses either Cliquer (for max cliques) or LP formulations (for TSP, cliques, and many others)  
> **username_5**: @username_4 do you have a reference for those open instances with 100 vertices?  
> **username_4**: @AustinBuchanan try to look at this paper: http://link.springer.com/article/10.1007%2Fs10732-012-9196-4 (I might be easily wrong though).  

---

### Answer by username_6 on 2011-10-06. Score: 2

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.


---

