patternModerate
Can a graph problem remain NP-hard when restricted to cycle graphs?
Viewed 0 times
problemcancyclegraphgraphshardremainwhenrestricted
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#162386, answer score: 10
Revisions (0)
No revisions yet.