I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start,
s and the target,
O(1) time as this doesn't depend on the size of the graph. Algorithms by Dasgupta et al. says that the pre and post processing steps take polynomial time.
One last detail, crucial but typically easy to check, is that the pre- and postprocessing functions take time polynomial in the size of the instance (G, s, t).
This makes me think that
O(1) is polynomial time. Is this incorrect?