Before revision:  Our exact algorithm runs in linear time when K^2 is sublinear.
After revision:  Our exact algorithm runs in linear time when K^2 is O(N^C) for C < 1.