2

I have a homework question asking for a polynomial algorithm to find a clique of size Ω(logn).

My current implementation is as follows:

  1. Divide the graph into n^logn microsets (subgraphs) of size logn and store them as adjacency matrices
  2. For each subgraph, brute force check if S is a clique of size logn
  3. If S is a clique, return it.
  4. If we finish iterating without finding a clique, return None (no logn cliques in graph, which is the worst case)

Building the subgraphs will take n^k time. To check if a subgraph is a clique of size logn will take O((logn)^2), as each vertex in the subgraph will have k^2 edges (where k is the clique size, which in this case is logn). This must be done for all n^logn subgaphs, so the total runtime would be O(n^logn +(n^(logn))((logn)^2)).

My questions are:

  1. Is this polynomial, or does the k as an exponent make it exponential
  2. Is my logic sound?
  3. What does the runtime reduce to?

Thanks y'all!

EDIT 1: I realize that the only way to do this in polynomial time is going to involve not creating n^k subgraphs, but rather dividing the graph into n/k components. If I do this, however, there is no way to guarantee that any of my microsets will actually have a k-sized clique even if one is guaranteed in the graph. Is there any way around this?

EDIT 2: One VERY important thing that I failed to mention or consider earlier was that we are given that G has a clique size of n/2. Because of this, we know that the worst case for separating G into n/logn subsets of size logn will result when the maximum clique of n/2 is evenly separated into size logn/2 cliques into each subgraph. This guarantees that we find at least one clique of size logn/2, which satisfies finding a clique of size Ω(logn). This is also polynomial, as it runs in O(n/logn * n^(log2(3)/3) time. Apologies for not providing this earlier!

Clayton C.
  • 863
  • 1
  • 8
  • 17
  • 3
    To be polynomial, it must be bounded above by `n^C` for some constant `C`. But if `C` is constant then for large enough `n`, `C < log(n)`. Therefore this is not a polynomial algorithm. – btilly Feb 24 '22 at 21:55
  • 4
    With no other assumptions, it would be a big surprise if such an algorithm exists: https://www.sciencedirect.com/science/article/pii/S0022000006000675?via%3Dihub – David Eisenstat Feb 25 '22 at 01:53
  • Thanks for the help, I forgot a major piece of the puzzle that we were given which makes a huge difference. See my second edit. – Clayton C. Feb 25 '22 at 02:41
  • *"Building the subgraphs will take n^k time."* What is k? You have not defined it. – kaya3 Feb 25 '22 at 02:52
  • K is the size of clique in the k-clique problem: https://en.m.wikipedia.org/wiki/Clique_problem#Cliques_of_fixed_size – Clayton C. Feb 25 '22 at 03:12

0 Answers0