Hi CF's .
Is there any algorithm that can find the biggest Complete graph inside a graph.
I searched a little but i didn't find any resources , is such algorithm even exist ?
→ Pay attention
Before contest
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
2 days
Register now »
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
2 days
Register now »
*has extra registration
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Oct/15/2026 13:41:57 (g2).
Desktop version, switch to mobile version.
Supported by
Good day to you
Complete graph inside graph is called "Clique" so you can try to search this term and you will find more results.
Anyway algorithms searching for clique (unless specific cases) are exponential :(
Thanks , i'm seeking for O(n) algorithm , but that seems to be impossible right ?
I'm afraid it is impossible :'(
This problem is known to be NP-hard. If someone finds even a polynomial solution, not necessary linear, he will get a Millenium Prize.
So you are telling me that i spent the night trying to solve a millenium prize algorithm ... lol
I assume you are trying to apply this to Today's D, since I was thinking of the same thing. Try drawing example graphs and you might notice some special properties of the cliques.
Okay you got me. I'll try that may be i will come up with something.