A question about the clique problem (specifically k-clique). Is there any algorithm that takes advantage of the properties of connected graphs to find cliques of a given size k, if such cliques exist?
Any algorithm can be made to take advantage of connected components. Just find the connected components before running the algorithm, discard those smaller than k and run the algorithm separately on each of the remaining ones.