Is finding a path with more red vertices than blue vertices NP-hard?
$begingroup$
Given a connected, directed graph $G=(V,E)$, vertices $s,t in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?
I think it should be possible but our TA said this was NP-hard.
Idea for a solution:
From $G$ create $G'=(V',E')$ as follows:
Split all $v in Vsetminus {s,t}$ in two vertices $v_{in}$ and $v_{out}$.
$V'$ is made up of the split vertex pairs and $s$ and $t$.
For all $e=(u,v) in E$ introduce an edge $(u_{out},v_{in})$. (For edge $(x,v)$ or $(u,x)$ where $x in {s,t}$ create edge $(x,v_{in})$ or $(u_{out},x)$ resp.). Also, introduce an edge $(v_{in},v_{out})$ for any of the split vertices.
So $E'$ contains two types of edges: the ones that correspond to edges from $E$ and the ones that correspond to vertices from $V$.
Now, we introduce weights as follows:
- $w((v_{in},v_{out})) = -1$ if the corresponding vertex $v$ was red.
- $w((v_{in},v_{out})) = +1$ if the corresponding vertex $v$ was blue.
- $w(e) = 0$ for all other edges, i.e. the ones that correspond to edges of $G$ rather than vertices.
Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,... , check whether the length of the given path is $<0$ and you are done.
Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we'd have to find the desired path with non-efficient means rendering this decision problem NP-hard?
Is there an elegant reduction to show NP-hardness?
complexity-theory graphs
asked 16 hours ago
Valerie PoulainValerie Poulain
282
New contributor
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Given a connected, directed graph $G=(V,E)$, vertices $s,t in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?
I think it should be possible but our TA said this was NP-hard.
Idea for a solution:
From $G$ create $G'=(V',E')$ as follows:
Split all $v in Vsetminus {s,t}$ in two vertices $v_{in}$ and $v_{out}$.
$V'$ is made up of the split vertex pairs and $s$ and $t$.
For all $e=(u,v) in E$ introduce an edge $(u_{out},v_{in})$. (For edge $(x,v)$ or $(u,x)$ where $x in {s,t}$ create edge $(x,v_{in})$ or $(u_{out},x)$ resp.). Also, introduce an edge $(v_{in},v_{out})$ for any of the split vertices.
So $E'$ contains two types of edges: the ones that correspond to edges from $E$ and the ones that correspond to vertices from $V$.
Now, we introduce weights as follows:
- $w((v_{in},v_{out})) = -1$ if the corresponding vertex $v$ was red.
- $w((v_{in},v_{out})) = +1$ if the corresponding vertex $v$ was blue.
- $w(e) = 0$ for all other edges, i.e. the ones that correspond to edges of $G$ rather than vertices.
Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,... , check whether the length of the given path is $<0$ and you are done.
Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we'd have to find the desired path with non-efficient means rendering this decision problem NP-hard?
Is there an elegant reduction to show NP-hardness?
complexity-theory graphs
asked 16 hours ago
Valerie PoulainValerie Poulain
282
New contributor
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Given a connected, directed graph $G=(V,E)$, vertices $s,t in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?
I think it should be possible but our TA said this was NP-hard.
Idea for a solution:
From $G$ create $G'=(V',E')$ as follows:
Split all $v in Vsetminus {s,t}$ in two vertices $v_{in}$ and $v_{out}$.
$V'$ is made up of the split vertex pairs and $s$ and $t$.
For all $e=(u,v) in E$ introduce an edge $(u_{out},v_{in})$. (For edge $(x,v)$ or $(u,x)$ where $x in {s,t}$ create edge $(x,v_{in})$ or $(u_{out},x)$ resp.). Also, introduce an edge $(v_{in},v_{out})$ for any of the split vertices.
So $E'$ contains two types of edges: the ones that correspond to edges from $E$ and the ones that correspond to vertices from $V$.
Now, we introduce weights as follows:
- $w((v_{in},v_{out})) = -1$ if the corresponding vertex $v$ was red.
- $w((v_{in},v_{out})) = +1$ if the corresponding vertex $v$ was blue.
- $w(e) = 0$ for all other edges, i.e. the ones that correspond to edges of $G$ rather than vertices.
Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,... , check whether the length of the given path is $<0$ and you are done.
Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we'd have to find the desired path with non-efficient means rendering this decision problem NP-hard?
Is there an elegant reduction to show NP-hardness?
complexity-theory graphs
asked 16 hours ago
Valerie PoulainValerie Poulain
282
New contributor
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Given a connected, directed graph $G=(V,E)$, vertices $s,t in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?
I think it should be possible but our TA said this was NP-hard.
Idea for a solution:
From $G$ create $G'=(V',E')$ as follows:
Split all $v in Vsetminus {s,t}$ in two vertices $v_{in}$ and $v_{out}$.
$V'$ is made up of the split vertex pairs and $s$ and $t$.
For all $e=(u,v) in E$ introduce an edge $(u_{out},v_{in})$. (For edge $(x,v)$ or $(u,x)$ where $x in {s,t}$ create edge $(x,v_{in})$ or $(u_{out},x)$ resp.). Also, introduce an edge $(v_{in},v_{out})$ for any of the split vertices.
So $E'$ contains two types of edges: the ones that correspond to edges from $E$ and the ones that correspond to vertices from $V$.
Now, we introduce weights as follows:
- $w((v_{in},v_{out})) = -1$ if the corresponding vertex $v$ was red.
- $w((v_{in},v_{out})) = +1$ if the corresponding vertex $v$ was blue.
- $w(e) = 0$ for all other edges, i.e. the ones that correspond to edges of $G$ rather than vertices.
Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,... , check whether the length of the given path is $<0$ and you are done.
Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we'd have to find the desired path with non-efficient means rendering this decision problem NP-hard?
Is there an elegant reduction to show NP-hardness?
complexity-theory graphs
complexity-theory graphs
asked 16 hours ago
Valerie PoulainValerie Poulain
282
New contributor
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 16 hours ago
Valerie PoulainValerie Poulain
282
New contributor
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 16 hours ago
Valerie PoulainValerie Poulain
282
New contributor
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 16 hours ago
Valerie PoulainValerie Poulain
282
asked 16 hours ago
Valerie PoulainValerie Poulain
282
282
New contributor
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Valerie Poulain is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.
I think the best to show NP-completeness, is to use the Hamiltonian path problem.
Let's build a graph $G$ with $N+1$ red vertices and $N$ blue vertices. You first chain with edges all the blues vertices from the source to the last blue one. Then you put edges between this last one to every red vertex and an edge from every red vertex to the sink. Finally, you put any number of edges between red vertices.
So a single path from $s$ to $t$ passes necessarly through all blue nodes. Answering to
Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?
is like answering to:
Is there an Hamiltonian path in $G'$
with $G'$, the subgraph containing only red vertices.
And this problem is known as NP-complete.
answered 15 hours ago
VinceVince
64328
$endgroup$
1
$begingroup$
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 $|Vsetminus{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.
$endgroup$
– Valerie Poulain
14 hours ago
$begingroup$
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.
$endgroup$
– Vince
14 hours ago
$begingroup$
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.
$endgroup$
– Quuxplusone
9 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Valerie Poulain is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106420%2fis-finding-a-path-with-more-red-vertices-than-blue-vertices-np-hard%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.
I think the best to show NP-completeness, is to use the Hamiltonian path problem.
Let's build a graph $G$ with $N+1$ red vertices and $N$ blue vertices. You first chain with edges all the blues vertices from the source to the last blue one. Then you put edges between this last one to every red vertex and an edge from every red vertex to the sink. Finally, you put any number of edges between red vertices.
So a single path from $s$ to $t$ passes necessarly through all blue nodes. Answering to
Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?
is like answering to:
Is there an Hamiltonian path in $G'$
with $G'$, the subgraph containing only red vertices.
And this problem is known as NP-complete.
answered 15 hours ago
VinceVince
64328
$endgroup$
1
$begingroup$
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 $|Vsetminus{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.
$endgroup$
– Valerie Poulain
14 hours ago
$begingroup$
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.
$endgroup$
– Vince
14 hours ago
$begingroup$
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.
$endgroup$
– Quuxplusone
9 hours ago
add a comment |
$begingroup$
Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.
I think the best to show NP-completeness, is to use the Hamiltonian path problem.
Let's build a graph $G$ with $N+1$ red vertices and $N$ blue vertices. You first chain with edges all the blues vertices from the source to the last blue one. Then you put edges between this last one to every red vertex and an edge from every red vertex to the sink. Finally, you put any number of edges between red vertices.
So a single path from $s$ to $t$ passes necessarly through all blue nodes. Answering to
Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?
is like answering to:
Is there an Hamiltonian path in $G'$
with $G'$, the subgraph containing only red vertices.
And this problem is known as NP-complete.
answered 15 hours ago
VinceVince
64328
$endgroup$
1
$begingroup$
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 $|Vsetminus{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.
$endgroup$
– Valerie Poulain
14 hours ago
$begingroup$
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.
$endgroup$
– Vince
14 hours ago
$begingroup$
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.
$endgroup$
– Quuxplusone
9 hours ago
add a comment |
$begingroup$
Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.
I think the best to show NP-completeness, is to use the Hamiltonian path problem.
Let's build a graph $G$ with $N+1$ red vertices and $N$ blue vertices. You first chain with edges all the blues vertices from the source to the last blue one. Then you put edges between this last one to every red vertex and an edge from every red vertex to the sink. Finally, you put any number of edges between red vertices.
So a single path from $s$ to $t$ passes necessarly through all blue nodes. Answering to
Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?
is like answering to:
Is there an Hamiltonian path in $G'$
with $G'$, the subgraph containing only red vertices.
And this problem is known as NP-complete.
answered 15 hours ago
VinceVince
64328
$endgroup$
Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.
I think the best to show NP-completeness, is to use the Hamiltonian path problem.
Let's build a graph $G$ with $N+1$ red vertices and $N$ blue vertices. You first chain with edges all the blues vertices from the source to the last blue one. Then you put edges between this last one to every red vertex and an edge from every red vertex to the sink. Finally, you put any number of edges between red vertices.
So a single path from $s$ to $t$ passes necessarly through all blue nodes. Answering to
Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?
is like answering to:
Is there an Hamiltonian path in $G'$
with $G'$, the subgraph containing only red vertices.
And this problem is known as NP-complete.
answered 15 hours ago
VinceVince
64328
answered 15 hours ago
VinceVince
64328
answered 15 hours ago
VinceVince
64328
answered 15 hours ago
VinceVince
64328
64328
1
$begingroup$
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 $|Vsetminus{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.
$endgroup$
– Valerie Poulain
14 hours ago
$begingroup$
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.
$endgroup$
– Vince
14 hours ago
$begingroup$
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.
$endgroup$
– Quuxplusone
9 hours ago
add a comment |
1
$begingroup$
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 $|Vsetminus{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.
$endgroup$
– Valerie Poulain
14 hours ago
$begingroup$
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.
$endgroup$
– Vince
14 hours ago
$begingroup$
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.
$endgroup$
– Quuxplusone
9 hours ago
1
1
$begingroup$
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 $|Vsetminus{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.
$endgroup$
– Valerie Poulain
14 hours ago
$begingroup$
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 $|Vsetminus{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.
$endgroup$
– Valerie Poulain
14 hours ago
$begingroup$
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.
$endgroup$
– Vince
14 hours ago
$begingroup$
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.
$endgroup$
– Vince
14 hours ago
$begingroup$
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.
$endgroup$
– Quuxplusone
9 hours ago
$begingroup$
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.
$endgroup$
– Quuxplusone
9 hours ago
add a comment |
Valerie Poulain is a new contributor. Be nice, and check out our Code of Conduct.
Valerie Poulain is a new contributor. Be nice, and check out our Code of Conduct.
Valerie Poulain is a new contributor. Be nice, and check out our Code of Conduct.
Valerie Poulain is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106420%2fis-finding-a-path-with-more-red-vertices-than-blue-vertices-np-hard%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
