Timeline for Is finding a path with more red vertices than blue vertices NP-hard?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 4, 2019 at 8:23 | comment | added | j_random_hacker | @ValeriePoulain: Vince is right that starting and ending vertices are not given for the usual HP problem, but if they are given, your reduction needs a slight tweak: You must insert a chain of $|V \setminus \{s, t\}|-1$ blue vertices in a line along each edge between $s$ and any other red vertex. This is to prevent, e.g., a single edge from $s$ to some red vertex from being a valid solution to the constructed instance. | |
| Apr 4, 2019 at 7:55 | history | edited | Optidad | CC BY-SA 4.0 |
added 18 characters in body
|
| Apr 4, 2019 at 7:46 | comment | added | Optidad | @Quuxplusone you are right I edit to make it clearer. | |
| Apr 3, 2019 at 18:45 | comment | added | Quuxplusone | Upvoted for (I think) correctness; but this argument would be WAY easier to understand if you STARTED with the arbitrary graph $G'$ and then embedded it within the specially constructed $G$. Right now the reduction is hiding entirely in the single sentence "Finally, you put any number of edges between red vertices," which I missed on my first reading. "Any number of edges" is code for "you pick any arbitrary graph $G'$ whose Hamiltonian path you'd like to discover, and embed it in there." That's what makes this a valid reduction. | |
| Apr 3, 2019 at 14:26 | comment | added | Optidad | Yes I am not very familiar with NP-completeness demonstration but this way to present it is clearly better. I would nevertheless start with an instance of $G$ without $s$ & $t$ as initial Hamiltonian path problem has no specific vertex. | |
| Apr 3, 2019 at 14:02 | vote | accept | Valerie Poulain | ||
| Apr 3, 2019 at 14:02 | comment | added | Valerie Poulain | Neat, thanks. So if I wanted to formally prove $DHP \preceq ProblemAbove$ where I have to start with an instance $G,s,t$ for the Hamiltonian Path and map it to an instance $G',s',t'$ of this problem, could I do the following: Color all existing vertices red, add $|V\setminus\{s,t\}|-1$ blue vertices and connect them in a chain $(b_1)\rightarrow \ldots \rightarrow(b_n)$. Add an edge $(s,b_1)$, and for each $(s,v)$ in $G$ an edge $(b_n,v)$ in $G'$, the rest stays as it is. | |
| Apr 3, 2019 at 12:56 | history | answered | Optidad | CC BY-SA 4.0 |