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, t is 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).

Since O(1) is polynomial time of order 0, is this reduction O(1)?

  • $\begingroup$ You have to describe the steps $\endgroup$
    – Pål GD
    Mar 21 at 17:04
  • $\begingroup$ Could you please clarify? I thought that adding a vertex and 2 edges were the steps. $\endgroup$ Mar 21 at 17:11
  • $\begingroup$ This depends on the model of computation, on the input representation, and on how you want your algorithm to return its output. It seems that you just want to (destructively) modify the input instance. In this case you can perform the reduction in $O(1)$ time if, for example, you are in the word-ram model and the input graph is represented as a list of edges (pairs of integers). For reasonable representations and models of computations you need $O(n)$ time (notice that constants are also in $O(n)$), where $n$ is the size of the input instance, even if the input instance is read-only. $\endgroup$
    – Steven
    Mar 21 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.