Timeline for If the Clique-k Problem is in P, why not Clique as well?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 27, 2016 at 19:43 | vote | accept | lo tolmencre | ||
| Jun 27, 2016 at 18:20 | comment | added | chi | Say you have $2k$ nodes and you need to check whether there is a clique of $k$ nodes. The naive algorithm would 1) scan all combinations of $k$ nodes chosen among the $2k$, and 2) check if that is really a clique. The part 2) is indeed $O(k^2)$, but part 1) generates an exponential number of subsets, so the total cost is exponential * quadratic which is not polynomial. | |
| Jun 27, 2016 at 17:42 | comment | added | lo tolmencre | I don't quite understand. Surely the most steps needed is to compare every node with every other node, or is it not? That would be $n^2$ in the worst case. If you have a fully connected graph of $n$ nodes and are looking for a clique of size $n$ as well, then you have to compare every node with every other node. How could it get worse? And if the worst case has $n^2$ steps to solve, where does it play a role whether I know my $k$ beforehand or not? | |
| Jun 27, 2016 at 17:27 | history | edited | chi | CC BY-SA 3.0 |
added 23 characters in body
|
| Jun 27, 2016 at 17:22 | history | answered | chi | CC BY-SA 3.0 |