1
$\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.

$\endgroup$
4
  • $\begingroup$ What is asymptotic restriction on complexity of algorithm? $\endgroup$ Commented Mar 27, 2019 at 22:51
  • $\begingroup$ @Vladislav $O(|V|+|E|)$ $\endgroup$ Commented Mar 27, 2019 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$ Commented Mar 27, 2019 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$ Commented Mar 27, 2019 at 23:46

1 Answer 1

Reset to default
0
$\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, \{0, 1\} ^3) \ | 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.

$\endgroup$
2
  • $\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$ Commented Mar 27, 2019 at 23:48
  • $\begingroup$ In this case, you've got a linear solution for an arbitrarily fixed k. $\endgroup$ Commented Mar 27, 2019 at 23:50

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.