Is it okay to work on a problem which is incremental as your first Ph.D problem? I am a Ph.D. student in theoretical computer science. I have recently come across one problem on which somebody has already done work, but in that work I figured out one problem which may be small (I don’t how significant it is). I asked my colleagues about this, and some of them suggested me to pick a new problem for your first Ph.D. problem. I am in confusion what to do.

My question is: Is it okay to work on a problem which is incremental as your first Ph.D problem? Incremental in my context simply means designing a faster algorithm.
Yes!

Your goal for your first problem is just to publish something. It doesn’t have to be significant. It doesn’t have to be in a top conference. It doesn’t have to be related to your eventual thesis topic. It doesn’t even have to be in the same subfield as anything else you publish in the future. Just publish something.

This is just getting you used to the process of writing and revising and submitting and being frustrated by bad reviews and rerevising and seeing the results in print, so that none of that stuff is a barrier later.  This is inoculation against the inevitable future Impostor Syndrome telling you that you can’t do this, because you already did this.