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.