5
$\begingroup$

Does anyone have any examples of NP-hard graph problems which stay NP-hard on cycles, or is this class somehow not able to have NP-hard problems?

I found a similar post concerning trees here which answers affirmatively, but by using the fact that any $n$-size input can be encoded as a tree of order $n$. Cycles only have one member per order and thus this trick cannot be used. Due to this, I've started to think that the only parameter of a cycle graph is just the order $n$, and so perhaps graph problems restricted on cycle graphs don't really make sense as it's more of a problem on integers? However, since there are problems on integers which could be NP-hard, such as integer factorization, could it be that NP-hard problems on cycles do exist?

I checked on graphclasses but no ``cycle'' graph class exists, which further confirms my suspicion that there's just something inherently too simple about this class.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

Assuming the problem instance is defined solely by the cycle itself (no labels or weights on the nodes, etc., no other inputs to the algorithm), then no, you should not expect any such problem to be NP-hard.

Any language containing just cycles is a sparse language. In other words, any question about cycles ("does this cycle have property $P$?", where $P$ is any property you care about) corresponds to a sparse language.

It is known that every sparse language is in $P/\text{poly}$, and if a sparse language is NP-complete, then $P=NP$. Since most people believe that, most likely, $P \ne NP$, it follows that, most likely, no problem about cycles will be NP-complete. Also, since every sparse language is in $P/\text{poly}$, any problem about cycles can't be "too hard", in some rough sense.

Or, to put it another way, if you find a problem about cycles that is NP-complete, then you will have found a proof that $P=NP$ and can claim the $1M Millenium Prize. Since no one has managed to do that so far, you shouldn't expect anyone to find such a problem about cycles, either.

The question about NP-hard is a little trickier because of complications with uniform vs non-uniform complexity classes and $P$ vs $P/\text{poly}$, but I hope that the above has addressed the core of your question. Incidentally, factorization is not believed to be NP-hard.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I read up on P/poly and it is stated on the Wikipedia page that it contains undecidable problems. Since it is not believed to contain NP-hard problems, but does contain undecidable problems, I am confused on whether to consider this a tractable class of problems or an intractable one. Is that what you address with uniformity in your answer? $\endgroup$
    – J. Schmidt
    Oct 13 at 11:59
  • $\begingroup$ Also, you say that any problem on cycles corresponds to a sparse language, but doesn't this depend on how you represent these cycle instances? If the input is the full graph with $n$ vertices and $n$ edges, or if the input is $1^n$, then I can see how this is a sparse language, but if one instead uses the binary representation of its size as input, would this still correspond a sparse language? $\endgroup$
    – J. Schmidt
    Oct 13 at 12:01
  • $\begingroup$ @J.Schmidt, yes, that business with undecidable problems is what I was alluding to in my last paragraph ("trickier.. non-uniform...") -- there is a sense in which P/poly contains easy/tractable problems (it is analogous to P; intuitively, most natural problems that happen to fall in P are also tractable), and a sense in which it can contain very hard/intractable problems (it can encode undecidable problems, though they may be artificial or unnatural). $\endgroup$
    – D.W. ♦
    Oct 13 at 16:30
  • $\begingroup$ @J.Schmidt, the question asks about problems on graphs that remain hard when the input is a cycle. So my interpretation is that the input to the algorithm is a graph that happens to be a cycle, with the graph represented in some standard format (e.g., adjacency list format). With this interpretation, $n$ is effectively represented in unary. There is no standard representation of graphs such that the length of the representation of a $n$-cycle is less than $n$, so binary representations simply do not come up in this context (though in that case it would not be sparse). $\endgroup$
    – D.W. ♦
    Oct 13 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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