# Can a graph problem remain NP-hard when restricted to cycle graphs?

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.

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. • 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? Oct 13 at 11:59 • 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? Oct 13 at 12:01 • @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). – D.W. Oct 13 at 16:30 • @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).