NP-Complete graph problems where a special vertex is given as input?

Question

I am currently working on a graph theory problem where the instance includes a graph and a special vertex in the graph. I am trying to prove the NP-completeness of the problem as well as explore algorithms on different classes of graphs. One problem I am having is that I have yet to find any similar problems where a special vertex is given as part of the input to the problem.

Any links to problems (either polynomial or NP-complete) where a special vertex is given as part of the input would be a great help.

Answer 1

A common reduction strategy is to construct a new graph where you add some dummy vertex/vertices and connect them to the special vertex in a particular way, which ensures that the solution uses the special vertex in the desired way (e.g., the path starts there, or something). Or, you might add dummy vertices and connect them to all other vertices except for the special vertex. The details will depend on the particular problem you are trying to prove NP-complete. Since you haven't told us anything about your problem, it's not possible to say much more.

So, don't limit yourself to looking for a reduction partner where the problem definition mentions a special vertex. Instead, look for a reduction partner that is similar to your original problem, and then deal with the special vertex by modifying the graph.