Before revision:  We derive lower-bound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for  Line Cover in the algebraic computation trees model.
After revision:  We derive lower-bound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for  Line Cover in the algebraic computation trees model.