It seems to me to be incorrect to say that lexicographic DFS is P-complete, since it isn't a decision problem. There is a corresponding decision problem, first DFS ordering, which is known to be P-complete. However, I want to talk about complexity of DFS, not it's decision problem. What complexity class should I say DFS belongs to?


The formal name for a problem where you want to actually produce the solution as the output (not just say yes or no to whether one exists) is a Function Problem if every input has an associated output, or a Search Problem if some inputs might not have any solution (of course a function problem is just a special case of a search problem).

In this case, every graph has a lexicographic depth first ordering, so for any graph there is some output that can be produced, and you have a function problem. The class of function problems that can be computed in deterministic polynomial time is (cunningly) called FP.

Going out on a limb (with regards to my knowledge, someone else might be able to confirm this), I suspect that the obvious relationship1 between P and FP holds for complete problems too, so your problem should also be FP-complete.

  1. Note that this relationship normally relies on Turing reductions, but seeing as P=co-P there shouldn't be too much of a problem here.
  • $\begingroup$ Thanks, it makes a lot of sense, the confusing fact was that in a research paper I was reading somebody was calling DFS a P-complete problem, which was somewhat of an abuse (so it seemed). $\endgroup$ May 15 '14 at 16:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.