<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-06-17T18:00:11.730Z
2018-06-17T18:00:11.730Z
D.W.
<p>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. </p>

<p>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. </p>

CC BY-SA 4.0
2018-06-17T17:58:28.220Z
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.
D.W.
CC BY-SA 4.0
2018-06-26T17:59:28.003Z
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?
Hsien-Chih Chang 張顯之
<cc.complexity-theory><graph-theory><np-hardness><np-complete>
NP-Complete graph problems where a special vertex is given as input?
balr41
# NP-Complete graph problems where a special vertex is given as input?

(Asked by: username_0 on 2018-06-15)

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.

**Tags:** cc.complexity-theory, graph-theory, np-hardness, np-complete

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  

---

## 1 answers

### Answer by username_1 on 2018-06-17. Score: 3 | Accepted answer

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.


---

