Algorithms: Efficiently find a path containing at least $k$ nodes of some given colors. The Next CEO of Stack OverflowDirected Graph, shortest path algorithm. I don't even understand what this question is asking. Is it a trick question or just Dijkstra's?Finding the longest path in an undirected weighted treeProving Vizing's Theorem using InductionShortest acyclical path between two nodes, negative weights allowedThe graph which has the least edges while satisfying this propertyModified Shortest Path ProblemTest question regarding graph theory - please check my workWeak, Regular, and Strong connectivity in directed graphsQuestion about a proof of “Graph $G$ has no odd cycles $implies$ $G$ is bipartite”Find shortest path in graph that visits 2 nodes from a certain node set
Necessary condition on homology group for a set to be contractible
Example of a Mathematician/Physicist whose Other Publications during their PhD eclipsed their PhD Thesis
A Man With a Stainless Steel Endoskeleton (like The Terminator) Fighting Cloaked Aliens Only He Can See
I believe this to be a fraud - hired, then asked to cash check and send cash as Bitcoin
Method for adding error messages to a dictionary given a key
RigExpert AA-35 - Interpreting The Information
Is it convenient to ask the journal's editor for two additional days to complete a review?
Poetry, calligrams and TikZ/PStricks challenge
A small doubt about the dominated convergence theorem
Is French Guiana a (hard) EU border?
How to edit “Name” property in GCI output?
Domestic-to-international connection at Orlando (MCO)
Why do airplanes bank sharply to the right after air-to-air refueling?
Reference request: Grassmannian and Plucker coordinates in type B, C, D
How to prove a simple equation?
Rotate a column
WOW air has ceased operation, can I get my tickets refunded?
What happened in Rome, when the western empire "fell"?
What does "Its cash flow is deeply negative" mean?
Is it my responsibility to learn a new technology in my own time my employer wants to implement?
Is the D&D universe the same as the Forgotten Realms universe?
Easy to read palindrome checker
Newlines in BSD sed vs gsed
When you upcast Blindness/Deafness, do all targets suffer the same effect?
Algorithms: Efficiently find a path containing at least $k$ nodes of some given colors.
The Next CEO of Stack OverflowDirected Graph, shortest path algorithm. I don't even understand what this question is asking. Is it a trick question or just Dijkstra's?Finding the longest path in an undirected weighted treeProving Vizing's Theorem using InductionShortest acyclical path between two nodes, negative weights allowedThe graph which has the least edges while satisfying this propertyModified Shortest Path ProblemTest question regarding graph theory - please check my workWeak, Regular, and Strong connectivity in directed graphsQuestion about a proof of “Graph $G$ has no odd cycles $implies$ $G$ is bipartite”Find shortest path in graph that visits 2 nodes from a certain node set
$begingroup$
Suppose you have a directed graph with vertices colored A, B, C, and D. One node is $s$, the start node, and another $t$, the terminal node. You want to determine two things: First, find a path from $s$ to $t$ which contain at least one vertex of colors A, B, and C, and minimize the number of vertices of color D. Paths need not be simple.
Second, for any given $k>0$ determine whether a path exists which visits $k$-many vertices of color A, and $k$-many of color B, and $k$-many of color C. Again paths need not be simple.
Solution to the first part:
For the first question, I used the following solution: If the color at $s$ is A then we look for paths that go to a vertex colored B and then C minimizing the number of vertices colored D. Then we look for paths that go C then B minimizing the vertices colored at D. Then take the minimum of these two results. As long as we can find the minimum path for some specific color ordering in linear time, then doing it twice will still take linear time.
So to do that, first give every edge of the graph which enters a D vertex weight 1 and all others weight 0. Next make three copies of the graph, so that you have G, G', and G''. In G reassign every edge coming from an A vertex to a B to map into the corresponding vertex of G'. Then do likewise mapping B to C edges into the corresponding vertex of G''.
On this new graph run Dijkstra's. Since edges are not negative and bounded by a small constant, the algorithm runs in linear time.
To reiterate, since we can do it in some particular order of colors, we can do it then on all permutations of colors and this only multiplies linear time by a constant, so the algorithm continues to run in constant time.
I think I got the first part right but am a little more hung up on the second. I've imagined trying to leverage the solution to the first part. Perhaps make $k$ copies of the graph, on each copy run the algorithm ... but that doesn't make sense, you couldn't just stitch together two such paths and be ensured that such a path exists in the original graph. I thought maybe I should make $3k$ copies of the graph but I'm not sure how I would bind them together.
Hints or advice would be welcome.
graph-theory algorithms
asked Mar 27 at 19:32
AddemAddem
1,7441429
$endgroup$
add a comment |
$begingroup$
Suppose you have a directed graph with vertices colored A, B, C, and D. One node is $s$, the start node, and another $t$, the terminal node. You want to determine two things: First, find a path from $s$ to $t$ which contain at least one vertex of colors A, B, and C, and minimize the number of vertices of color D. Paths need not be simple.
Second, for any given $k>0$ determine whether a path exists which visits $k$-many vertices of color A, and $k$-many of color B, and $k$-many of color C. Again paths need not be simple.
Solution to the first part:
For the first question, I used the following solution: If the color at $s$ is A then we look for paths that go to a vertex colored B and then C minimizing the number of vertices colored D. Then we look for paths that go C then B minimizing the vertices colored at D. Then take the minimum of these two results. As long as we can find the minimum path for some specific color ordering in linear time, then doing it twice will still take linear time.
So to do that, first give every edge of the graph which enters a D vertex weight 1 and all others weight 0. Next make three copies of the graph, so that you have G, G', and G''. In G reassign every edge coming from an A vertex to a B to map into the corresponding vertex of G'. Then do likewise mapping B to C edges into the corresponding vertex of G''.
On this new graph run Dijkstra's. Since edges are not negative and bounded by a small constant, the algorithm runs in linear time.
To reiterate, since we can do it in some particular order of colors, we can do it then on all permutations of colors and this only multiplies linear time by a constant, so the algorithm continues to run in constant time.
I think I got the first part right but am a little more hung up on the second. I've imagined trying to leverage the solution to the first part. Perhaps make $k$ copies of the graph, on each copy run the algorithm ... but that doesn't make sense, you couldn't just stitch together two such paths and be ensured that such a path exists in the original graph. I thought maybe I should make $3k$ copies of the graph but I'm not sure how I would bind them together.
Hints or advice would be welcome.
graph-theory algorithms
asked Mar 27 at 19:32
AddemAddem
1,7441429
$endgroup$
$begingroup$
What is asymptotic restriction on complexity of algorithm?
$endgroup$
– Vladislav
Mar 27 at 22:51
$begingroup$
@Vladislav $O(|V|+|E|)$
$endgroup$
– Addem
Mar 27 at 22:52
$begingroup$
Ok, maybe I am not following you but I don't get how your solution is linear. Let's suppose a has color A and T has color C. You want to find shortest (in terms of number of D) path containing B. You can find shortest path from a to any B vertex in linear time, but next you have to iterate all B vertexes (it can be O(V) of them) and find the shortest path from every B to t. So it takes O(V *(V +E)), doesn't it?
$endgroup$
– Vladislav
Mar 27 at 23:07
$begingroup$
@Vladislav So my logic is that I have reproduced the graph three times, therefore there are $3|V|$ vertices and $3|E|$ edges. Since this is linear growth, it's not important. I remap some of the edges and add some weights and run Dijkstra's. Since I'm not finding a path from every B vertex to t then I shouldn't have the time complexity you wrote, but rather $O(3|V|+3|E|) = O(|V|+|E|)$. I can try to describe again the nature of the re-mapping and edge weights if that's still not clear.
$endgroup$
– Addem
Mar 27 at 23:46
add a comment |
$begingroup$
Suppose you have a directed graph with vertices colored A, B, C, and D. One node is $s$, the start node, and another $t$, the terminal node. You want to determine two things: First, find a path from $s$ to $t$ which contain at least one vertex of colors A, B, and C, and minimize the number of vertices of color D. Paths need not be simple.
Second, for any given $k>0$ determine whether a path exists which visits $k$-many vertices of color A, and $k$-many of color B, and $k$-many of color C. Again paths need not be simple.
Solution to the first part:
For the first question, I used the following solution: If the color at $s$ is A then we look for paths that go to a vertex colored B and then C minimizing the number of vertices colored D. Then we look for paths that go C then B minimizing the vertices colored at D. Then take the minimum of these two results. As long as we can find the minimum path for some specific color ordering in linear time, then doing it twice will still take linear time.
So to do that, first give every edge of the graph which enters a D vertex weight 1 and all others weight 0. Next make three copies of the graph, so that you have G, G', and G''. In G reassign every edge coming from an A vertex to a B to map into the corresponding vertex of G'. Then do likewise mapping B to C edges into the corresponding vertex of G''.
On this new graph run Dijkstra's. Since edges are not negative and bounded by a small constant, the algorithm runs in linear time.
To reiterate, since we can do it in some particular order of colors, we can do it then on all permutations of colors and this only multiplies linear time by a constant, so the algorithm continues to run in constant time.
I think I got the first part right but am a little more hung up on the second. I've imagined trying to leverage the solution to the first part. Perhaps make $k$ copies of the graph, on each copy run the algorithm ... but that doesn't make sense, you couldn't just stitch together two such paths and be ensured that such a path exists in the original graph. I thought maybe I should make $3k$ copies of the graph but I'm not sure how I would bind them together.
Hints or advice would be welcome.
graph-theory algorithms
asked Mar 27 at 19:32
AddemAddem
1,7441429
$endgroup$
Suppose you have a directed graph with vertices colored A, B, C, and D. One node is $s$, the start node, and another $t$, the terminal node. You want to determine two things: First, find a path from $s$ to $t$ which contain at least one vertex of colors A, B, and C, and minimize the number of vertices of color D. Paths need not be simple.
Second, for any given $k>0$ determine whether a path exists which visits $k$-many vertices of color A, and $k$-many of color B, and $k$-many of color C. Again paths need not be simple.
Solution to the first part:
For the first question, I used the following solution: If the color at $s$ is A then we look for paths that go to a vertex colored B and then C minimizing the number of vertices colored D. Then we look for paths that go C then B minimizing the vertices colored at D. Then take the minimum of these two results. As long as we can find the minimum path for some specific color ordering in linear time, then doing it twice will still take linear time.
So to do that, first give every edge of the graph which enters a D vertex weight 1 and all others weight 0. Next make three copies of the graph, so that you have G, G', and G''. In G reassign every edge coming from an A vertex to a B to map into the corresponding vertex of G'. Then do likewise mapping B to C edges into the corresponding vertex of G''.
On this new graph run Dijkstra's. Since edges are not negative and bounded by a small constant, the algorithm runs in linear time.
To reiterate, since we can do it in some particular order of colors, we can do it then on all permutations of colors and this only multiplies linear time by a constant, so the algorithm continues to run in constant time.
I think I got the first part right but am a little more hung up on the second. I've imagined trying to leverage the solution to the first part. Perhaps make $k$ copies of the graph, on each copy run the algorithm ... but that doesn't make sense, you couldn't just stitch together two such paths and be ensured that such a path exists in the original graph. I thought maybe I should make $3k$ copies of the graph but I'm not sure how I would bind them together.
Hints or advice would be welcome.
graph-theory algorithms
graph-theory algorithms
asked Mar 27 at 19:32
AddemAddem
1,7441429
asked Mar 27 at 19:32
AddemAddem
1,7441429
edited Mar 27 at 20:50
Addem
asked Mar 27 at 19:32
AddemAddem
1,7441429
asked Mar 27 at 19:32
AddemAddem
1,7441429
asked Mar 27 at 19:32
AddemAddem
1,7441429
1,7441429
$begingroup$
What is asymptotic restriction on complexity of algorithm?
$endgroup$
– Vladislav
Mar 27 at 22:51
$begingroup$
@Vladislav $O(|V|+|E|)$
$endgroup$
– Addem
Mar 27 at 22:52
$begingroup$
Ok, maybe I am not following you but I don't get how your solution is linear. Let's suppose a has color A and T has color C. You want to find shortest (in terms of number of D) path containing B. You can find shortest path from a to any B vertex in linear time, but next you have to iterate all B vertexes (it can be O(V) of them) and find the shortest path from every B to t. So it takes O(V *(V +E)), doesn't it?
$endgroup$
– Vladislav
Mar 27 at 23:07
$begingroup$
@Vladislav So my logic is that I have reproduced the graph three times, therefore there are $3|V|$ vertices and $3|E|$ edges. Since this is linear growth, it's not important. I remap some of the edges and add some weights and run Dijkstra's. Since I'm not finding a path from every B vertex to t then I shouldn't have the time complexity you wrote, but rather $O(3|V|+3|E|) = O(|V|+|E|)$. I can try to describe again the nature of the re-mapping and edge weights if that's still not clear.
$endgroup$
– Addem
Mar 27 at 23:46
add a comment |
$begingroup$
What is asymptotic restriction on complexity of algorithm?
$endgroup$
– Vladislav
Mar 27 at 22:51
$begingroup$
@Vladislav $O(|V|+|E|)$
$endgroup$
– Addem
Mar 27 at 22:52
$begingroup$
Ok, maybe I am not following you but I don't get how your solution is linear. Let's suppose a has color A and T has color C. You want to find shortest (in terms of number of D) path containing B. You can find shortest path from a to any B vertex in linear time, but next you have to iterate all B vertexes (it can be O(V) of them) and find the shortest path from every B to t. So it takes O(V *(V +E)), doesn't it?
$endgroup$
– Vladislav
Mar 27 at 23:07
$begingroup$
@Vladislav So my logic is that I have reproduced the graph three times, therefore there are $3|V|$ vertices and $3|E|$ edges. Since this is linear growth, it's not important. I remap some of the edges and add some weights and run Dijkstra's. Since I'm not finding a path from every B vertex to t then I shouldn't have the time complexity you wrote, but rather $O(3|V|+3|E|) = O(|V|+|E|)$. I can try to describe again the nature of the re-mapping and edge weights if that's still not clear.
$endgroup$
– Addem
Mar 27 at 23:46
$begingroup$
What is asymptotic restriction on complexity of algorithm?
$endgroup$
– Vladislav
Mar 27 at 22:51
$begingroup$
What is asymptotic restriction on complexity of algorithm?
$endgroup$
– Vladislav
Mar 27 at 22:51
$begingroup$
@Vladislav $O(|V|+|E|)$
$endgroup$
– Addem
Mar 27 at 22:52
$begingroup$
@Vladislav $O(|V|+|E|)$
$endgroup$
– Addem
Mar 27 at 22:52
$begingroup$
Ok, maybe I am not following you but I don't get how your solution is linear. Let's suppose a has color A and T has color C. You want to find shortest (in terms of number of D) path containing B. You can find shortest path from a to any B vertex in linear time, but next you have to iterate all B vertexes (it can be O(V) of them) and find the shortest path from every B to t. So it takes O(V *(V +E)), doesn't it?
$endgroup$
– Vladislav
Mar 27 at 23:07
$begingroup$
Ok, maybe I am not following you but I don't get how your solution is linear. Let's suppose a has color A and T has color C. You want to find shortest (in terms of number of D) path containing B. You can find shortest path from a to any B vertex in linear time, but next you have to iterate all B vertexes (it can be O(V) of them) and find the shortest path from every B to t. So it takes O(V *(V +E)), doesn't it?
$endgroup$
– Vladislav
Mar 27 at 23:07
$begingroup$
@Vladislav So my logic is that I have reproduced the graph three times, therefore there are $3|V|$ vertices and $3|E|$ edges. Since this is linear growth, it's not important. I remap some of the edges and add some weights and run Dijkstra's. Since I'm not finding a path from every B vertex to t then I shouldn't have the time complexity you wrote, but rather $O(3|V|+3|E|) = O(|V|+|E|)$. I can try to describe again the nature of the re-mapping and edge weights if that's still not clear.
$endgroup$
– Addem
Mar 27 at 23:46
$begingroup$
@Vladislav So my logic is that I have reproduced the graph three times, therefore there are $3|V|$ vertices and $3|E|$ edges. Since this is linear growth, it's not important. I remap some of the edges and add some weights and run Dijkstra's. Since I'm not finding a path from every B vertex to t then I shouldn't have the time complexity you wrote, but rather $O(3|V|+3|E|) = O(|V|+|E|)$. I can try to describe again the nature of the re-mapping and edge weights if that's still not clear.
$endgroup$
– Addem
Mar 27 at 23:46
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I don't think I understood your solution, but I can provide an easy one for the first.
Let's build a new graph $G'=(V', E')$ where $V' = v in V$
In other words, vertexes of $G'$ are pairs of an original vertex and bitmask of visited colors. For instance, $(3, 011)$ means vertex $3$ of $G$ and $A$ has not been visited, $B$ and $C$ has been visited).
$E'$ contains an edge $(v, mask1) rightarrow(u, mask2)$ iff the original graph has the edge $u rightarrow v$ and $mask2$ is $mask1$ with the bit corresponding to color of $u$ set to $1$.
Clearly, all you left to do is to find the shortest path (in terms of number of $D$'s) from $(s, 100)$ (if $s$ has color $A$, if $s$ has color $B$ it will be $010$ and so on) to $(t, 111)$.
Clearly, this new graph has $8|V|$ vertexes and $8|E|$ edges, so it linearly depends on the size of the original one.
On minimization the number of $D$'s: it is a good idea to set edge's weight $0$ or $1$ but it is kind of overkill to run Dijkstra on this graph. In order to find the shortest path on $0,1$ graph you just need to slightly modify breadth-first search. If you explore $1$-weighted edge you add the vertex in the end of the queue (as usual in breadth-first search), but to the beginning of queue if you explore $0$-weighted edge. This algorithm will give us the shortest path.
Unfortunately, this algorithm can not be generalized for an arbitrary $k$ with linear complexity as $G'$ will have $k^3|V|$ vertexes.
answered Mar 27 at 23:43
VladislavVladislav
1015
$endgroup$
$begingroup$
I'm not certain whether I need to treat $k$ as a variable for the growth of the algorithm or not. I've been assuming that I only need to treat it as a fixed parameter. Otherwise, I am pretty skeptical anything could be linear with a growing $k$.
$endgroup$
– Addem
Mar 27 at 23:48
$begingroup$
In this case, you've got a linear solution for an arbitrarily fixed k.
$endgroup$
– Vladislav
Mar 27 at 23:50
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: "69"
;
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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%2fmath.stackexchange.com%2fquestions%2f3165007%2falgorithms-efficiently-find-a-path-containing-at-least-k-nodes-of-some-given%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$
I don't think I understood your solution, but I can provide an easy one for the first.
Let's build a new graph $G'=(V', E')$ where $V' = v in V$
In other words, vertexes of $G'$ are pairs of an original vertex and bitmask of visited colors. For instance, $(3, 011)$ means vertex $3$ of $G$ and $A$ has not been visited, $B$ and $C$ has been visited).
$E'$ contains an edge $(v, mask1) rightarrow(u, mask2)$ iff the original graph has the edge $u rightarrow v$ and $mask2$ is $mask1$ with the bit corresponding to color of $u$ set to $1$.
Clearly, all you left to do is to find the shortest path (in terms of number of $D$'s) from $(s, 100)$ (if $s$ has color $A$, if $s$ has color $B$ it will be $010$ and so on) to $(t, 111)$.
Clearly, this new graph has $8|V|$ vertexes and $8|E|$ edges, so it linearly depends on the size of the original one.
On minimization the number of $D$'s: it is a good idea to set edge's weight $0$ or $1$ but it is kind of overkill to run Dijkstra on this graph. In order to find the shortest path on $0,1$ graph you just need to slightly modify breadth-first search. If you explore $1$-weighted edge you add the vertex in the end of the queue (as usual in breadth-first search), but to the beginning of queue if you explore $0$-weighted edge. This algorithm will give us the shortest path.
Unfortunately, this algorithm can not be generalized for an arbitrary $k$ with linear complexity as $G'$ will have $k^3|V|$ vertexes.
answered Mar 27 at 23:43
VladislavVladislav
1015
$endgroup$
$begingroup$
I'm not certain whether I need to treat $k$ as a variable for the growth of the algorithm or not. I've been assuming that I only need to treat it as a fixed parameter. Otherwise, I am pretty skeptical anything could be linear with a growing $k$.
$endgroup$
– Addem
Mar 27 at 23:48
$begingroup$
In this case, you've got a linear solution for an arbitrarily fixed k.
$endgroup$
– Vladislav
Mar 27 at 23:50
add a comment |
$begingroup$
I don't think I understood your solution, but I can provide an easy one for the first.
Let's build a new graph $G'=(V', E')$ where $V' = v in V$
In other words, vertexes of $G'$ are pairs of an original vertex and bitmask of visited colors. For instance, $(3, 011)$ means vertex $3$ of $G$ and $A$ has not been visited, $B$ and $C$ has been visited).
$E'$ contains an edge $(v, mask1) rightarrow(u, mask2)$ iff the original graph has the edge $u rightarrow v$ and $mask2$ is $mask1$ with the bit corresponding to color of $u$ set to $1$.
Clearly, all you left to do is to find the shortest path (in terms of number of $D$'s) from $(s, 100)$ (if $s$ has color $A$, if $s$ has color $B$ it will be $010$ and so on) to $(t, 111)$.
Clearly, this new graph has $8|V|$ vertexes and $8|E|$ edges, so it linearly depends on the size of the original one.
On minimization the number of $D$'s: it is a good idea to set edge's weight $0$ or $1$ but it is kind of overkill to run Dijkstra on this graph. In order to find the shortest path on $0,1$ graph you just need to slightly modify breadth-first search. If you explore $1$-weighted edge you add the vertex in the end of the queue (as usual in breadth-first search), but to the beginning of queue if you explore $0$-weighted edge. This algorithm will give us the shortest path.
Unfortunately, this algorithm can not be generalized for an arbitrary $k$ with linear complexity as $G'$ will have $k^3|V|$ vertexes.
answered Mar 27 at 23:43
VladislavVladislav
1015
$endgroup$
$begingroup$
I'm not certain whether I need to treat $k$ as a variable for the growth of the algorithm or not. I've been assuming that I only need to treat it as a fixed parameter. Otherwise, I am pretty skeptical anything could be linear with a growing $k$.
$endgroup$
– Addem
Mar 27 at 23:48
$begingroup$
In this case, you've got a linear solution for an arbitrarily fixed k.
$endgroup$
– Vladislav
Mar 27 at 23:50
add a comment |
$begingroup$
I don't think I understood your solution, but I can provide an easy one for the first.
Let's build a new graph $G'=(V', E')$ where $V' = v in V$
In other words, vertexes of $G'$ are pairs of an original vertex and bitmask of visited colors. For instance, $(3, 011)$ means vertex $3$ of $G$ and $A$ has not been visited, $B$ and $C$ has been visited).
$E'$ contains an edge $(v, mask1) rightarrow(u, mask2)$ iff the original graph has the edge $u rightarrow v$ and $mask2$ is $mask1$ with the bit corresponding to color of $u$ set to $1$.
Clearly, all you left to do is to find the shortest path (in terms of number of $D$'s) from $(s, 100)$ (if $s$ has color $A$, if $s$ has color $B$ it will be $010$ and so on) to $(t, 111)$.
Clearly, this new graph has $8|V|$ vertexes and $8|E|$ edges, so it linearly depends on the size of the original one.
On minimization the number of $D$'s: it is a good idea to set edge's weight $0$ or $1$ but it is kind of overkill to run Dijkstra on this graph. In order to find the shortest path on $0,1$ graph you just need to slightly modify breadth-first search. If you explore $1$-weighted edge you add the vertex in the end of the queue (as usual in breadth-first search), but to the beginning of queue if you explore $0$-weighted edge. This algorithm will give us the shortest path.
Unfortunately, this algorithm can not be generalized for an arbitrary $k$ with linear complexity as $G'$ will have $k^3|V|$ vertexes.
answered Mar 27 at 23:43
VladislavVladislav
1015
$endgroup$
I don't think I understood your solution, but I can provide an easy one for the first.
Let's build a new graph $G'=(V', E')$ where $V' = v in V$
In other words, vertexes of $G'$ are pairs of an original vertex and bitmask of visited colors. For instance, $(3, 011)$ means vertex $3$ of $G$ and $A$ has not been visited, $B$ and $C$ has been visited).
$E'$ contains an edge $(v, mask1) rightarrow(u, mask2)$ iff the original graph has the edge $u rightarrow v$ and $mask2$ is $mask1$ with the bit corresponding to color of $u$ set to $1$.
Clearly, all you left to do is to find the shortest path (in terms of number of $D$'s) from $(s, 100)$ (if $s$ has color $A$, if $s$ has color $B$ it will be $010$ and so on) to $(t, 111)$.
Clearly, this new graph has $8|V|$ vertexes and $8|E|$ edges, so it linearly depends on the size of the original one.
On minimization the number of $D$'s: it is a good idea to set edge's weight $0$ or $1$ but it is kind of overkill to run Dijkstra on this graph. In order to find the shortest path on $0,1$ graph you just need to slightly modify breadth-first search. If you explore $1$-weighted edge you add the vertex in the end of the queue (as usual in breadth-first search), but to the beginning of queue if you explore $0$-weighted edge. This algorithm will give us the shortest path.
Unfortunately, this algorithm can not be generalized for an arbitrary $k$ with linear complexity as $G'$ will have $k^3|V|$ vertexes.
answered Mar 27 at 23:43
VladislavVladislav
1015
edited 2 days ago
answered Mar 27 at 23:43
VladislavVladislav
1015
answered Mar 27 at 23:43
VladislavVladislav
1015
answered Mar 27 at 23:43
VladislavVladislav
1015
1015
$begingroup$
I'm not certain whether I need to treat $k$ as a variable for the growth of the algorithm or not. I've been assuming that I only need to treat it as a fixed parameter. Otherwise, I am pretty skeptical anything could be linear with a growing $k$.
$endgroup$
– Addem
Mar 27 at 23:48
$begingroup$
In this case, you've got a linear solution for an arbitrarily fixed k.
$endgroup$
– Vladislav
Mar 27 at 23:50
add a comment |
$begingroup$
I'm not certain whether I need to treat $k$ as a variable for the growth of the algorithm or not. I've been assuming that I only need to treat it as a fixed parameter. Otherwise, I am pretty skeptical anything could be linear with a growing $k$.
$endgroup$
– Addem
Mar 27 at 23:48
$begingroup$
In this case, you've got a linear solution for an arbitrarily fixed k.
$endgroup$
– Vladislav
Mar 27 at 23:50
$begingroup$
I'm not certain whether I need to treat $k$ as a variable for the growth of the algorithm or not. I've been assuming that I only need to treat it as a fixed parameter. Otherwise, I am pretty skeptical anything could be linear with a growing $k$.
$endgroup$
– Addem
Mar 27 at 23:48
$begingroup$
I'm not certain whether I need to treat $k$ as a variable for the growth of the algorithm or not. I've been assuming that I only need to treat it as a fixed parameter. Otherwise, I am pretty skeptical anything could be linear with a growing $k$.
$endgroup$
– Addem
Mar 27 at 23:48
$begingroup$
In this case, you've got a linear solution for an arbitrarily fixed k.
$endgroup$
– Vladislav
Mar 27 at 23:50
$begingroup$
In this case, you've got a linear solution for an arbitrarily fixed k.
$endgroup$
– Vladislav
Mar 27 at 23:50
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3165007%2falgorithms-efficiently-find-a-path-containing-at-least-k-nodes-of-some-given%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
$begingroup$
What is asymptotic restriction on complexity of algorithm?
$endgroup$
– Vladislav
Mar 27 at 22:51
$begingroup$
@Vladislav $O(|V|+|E|)$
$endgroup$
– Addem
Mar 27 at 22:52
$begingroup$
Ok, maybe I am not following you but I don't get how your solution is linear. Let's suppose a has color A and T has color C. You want to find shortest (in terms of number of D) path containing B. You can find shortest path from a to any B vertex in linear time, but next you have to iterate all B vertexes (it can be O(V) of them) and find the shortest path from every B to t. So it takes O(V *(V +E)), doesn't it?
$endgroup$
– Vladislav
Mar 27 at 23:07
$begingroup$
@Vladislav So my logic is that I have reproduced the graph three times, therefore there are $3|V|$ vertices and $3|E|$ edges. Since this is linear growth, it's not important. I remap some of the edges and add some weights and run Dijkstra's. Since I'm not finding a path from every B vertex to t then I shouldn't have the time complexity you wrote, but rather $O(3|V|+3|E|) = O(|V|+|E|)$. I can try to describe again the nature of the re-mapping and edge weights if that's still not clear.
$endgroup$
– Addem
Mar 27 at 23:46