-1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ This sounds too open-ended/vague/unclear to me. I don't think it's interesting or useful to provide a list of all such problems; there are an unlimited number of them. $\endgroup$ – D.W. Jun 17 '18 at 17:58
  • $\begingroup$ A possible way to save the question: Are you looking for problems of finding substructures in graph, where the unrestricted version is in P, but finding one that contains the given vertex in NP-complete? $\endgroup$ – Hsien-Chih Chang 張顯之 Jun 26 '18 at 17:59
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.