Timeline for Determine if a graph has a large clique
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2014 at 4:05 | answer | added | Sasho Nikolov | timeline score: 1 | |
| Apr 17, 2014 at 2:32 | answer | added | Michael | timeline score: 1 | |
| Mar 17, 2014 at 23:37 | answer | added | Dima Pasechnik | timeline score: 1 | |
| Mar 17, 2014 at 22:58 | history | edited | Jernej | CC BY-SA 3.0 |
added 126 characters in body
|
| Mar 17, 2014 at 20:26 | comment | added | Jernej | @TheMaskedAvenger No, I cannot guarantee such bound. | |
| Mar 17, 2014 at 19:56 | comment | added | The Masked Avenger | Can you guarantee an upper bound on C intersect O where C ranges over (the vertex sets of) all moderately large cliques and O ranges over all orbits? | |
| Mar 17, 2014 at 19:31 | comment | added | Jernej | @TheMaskedAvenger I don't know if understand your question correctly, but the graph induced by a given orbit does not have a large clique in my case. | |
| Mar 17, 2014 at 18:44 | comment | added | The Masked Avenger | The symmetry group may be large because one has a pendant large clique (attached to the rest of the graph by few vertices). If there are no such cliques, there may be a way to better estimate clique size with such a guarantee and good knowledge of the automorphism group. | |
| Mar 17, 2014 at 18:37 | comment | added | Jernej | @TheMaskedAvenger What exactly do you mean by "orthogonal"? | |
| Mar 17, 2014 at 18:37 | comment | added | Jernej | @JosephO'Rourke I've tried to use some bbasic spectral properties but they did not give any good bounds for this concrete class of graphs. I haven't yet checked the ideas in this Alon's paper though. | |
| Mar 17, 2014 at 18:36 | comment | added | The Masked Avenger | Do you know enough to say if an orbit is "orthogonal" to all large cliques (interscts any such in at most one vertex)? | |
| Mar 17, 2014 at 18:25 | comment | added | Joseph O'Rourke | I wonder if you can use spectral properties? For example: Alon, Noga, Michael Krivelevich, and Benny Sudakov. "Finding a large hidden clique in a random graph." SODA. 1998. | |
| Mar 17, 2014 at 17:32 | history | edited | Jernej | CC BY-SA 3.0 |
added 10 characters in body
|
| Mar 17, 2014 at 16:49 | comment | added | Jernej | @PeterMueller Great, I'll try that out | |
| Mar 17, 2014 at 16:49 | comment | added | Jernej | @joro Yes, using a MILP with CPLEX/GUROBI is much slower than cliquer itself. | |
| Mar 17, 2014 at 13:09 | comment | added | joro | Have you tried independent set on the complement using MILP? | |
| Mar 17, 2014 at 13:01 | answer | added | John | timeline score: 0 | |
| Mar 17, 2014 at 12:22 | comment | added | Nathann Cohen | Hey, perhaps we should add it to Sage if it is better than Cliquer O_o | |
| Mar 17, 2014 at 11:12 | comment | added | Peter Mueller | The little known program MaxCliqueDyn to be found at sicmm.org/~konc/maxclique often supersedes cliquer. Maybe it helps in your situation. | |
| Mar 17, 2014 at 11:00 | comment | added | Ben Barber | It's worth noting that detecting whether a general graph has a k-clique is NP-complete. | |
| Mar 17, 2014 at 10:46 | history | asked | Jernej | CC BY-SA 3.0 |