Given the following variant on the k-Cliquie proble, is there a polynomial algorithm to find a solution?
We are given a graph $G=(V,E)$ and a parameter $k$ and we need to find a clique of size $k$ in the graph.
Normally this problem is known to be NP-Hard, but we have the following two additional assumptions:
- It promised that there exists a clique of size exactly $k$ in the graph
- The nodes of the graph are deivided into $k$ sets of size up-to $n$ each (it can be lower, but let's assume all sets are of size exactly $n$ for simplicity). And, there are edges only between node in different sets (i.e. no edges between nodes in the same set $i$).
I believe that the second assumption implies that suck clique (of size $k$) will include exactlly 1 node from each set, which might make this problem easier than the general case.
Still, the naive idea of going over all possible combinations requires $O(n^k)$.
So, are those two assumptions enough to ensure a polynimial-time algorithm to find such a clique?
Best Answer
I think that there will not exist a polynomial time algorithm for this variant, and not even a fixed parameter tractable algorithm with parameter $k$. Observe that the second condition makes this problem very similar to the $\textit{Multicolored $k$-clique}$ problem, which is $W[1]$-hard (so not solvable in polynomial time or FPT). In those problems, we are given $k$ color classes together with our graph, and are looking for a $k$-clique where each vertex must be picked from distinct color classes. Although those problems are allowed to have edges between the same color classes, they won't make the instances harder because they will never be included in a solution. Hence, you can work out a reduction from $\textit{Multicolored $k$-clique}$.
I think that the first assumption also does not help you: if it did, you could intuitively solve $k$-clique in polynomial time for instances where such a $k$-clique exists, and stop the algorithm if it takes too long.