<p>It is NP-hard to decide whether your problem is soluble. That's bad news from a theoretical point of view, but in practice it is possible that a heuristic algorithm will fare quite well. Also, you're (possibly) dealing with the "promise" variant of the problem, that is, you assume that a solution exists, and want to find it.</p>

<p>To see that the problem is NP-hard, we reduce Hamiltonian cycle to it. All the edges are always open, and they always have unit weight. The windows for each non-zero vertex are $[1,n-1]$ and $[n+1,2n-1]$; for vertex zero they are $\{0\}$ and $\{n\}$. These constraints are satisfiable only via a Hamiltonian cycle, and the converse is also true.</p>

CC BY-SA 3.0
2012-09-18T05:29:26.303Z
OK so using a computational approach how can you solve this problem ?
hDan
CC BY-SA 3.0
2012-09-18T13:30:27.107Z
That's your question.
Yuval Filmus
CC BY-SA 3.0
2012-09-19T06:09:13.833Z
What I mean if there is a better solution than the one I am currently using.
hDan
CC BY-SA 3.0
2012-09-21T10:29:06.730Z
I don't understand the reduction. Is the set of vertices $\{0,1,\ldots,n\}$? Are the windows for $1$ supposed to be empty? If a vertex has two windows then it will be visited twice, which makes the path non-hamiltonian. What am I missing?
Radu GRIGore
CC BY-SA 3.0
2012-09-21T13:29:23.347Z
The set of vertices is $\{0,1,\ldots,n-1\}$. The windows for $0$ are singletons. The first $n$ edges of the path will form a Hamiltonian cycle.
Yuval Filmus
CC BY-SA 3.0
2012-09-21T14:31:47.397Z
Ah, right. (I was thinking that the windows for vertex $k$ are $[1,k-1]$ and $[k+1,2k-1]$. That's why I asked about the window for $1$.)
Radu GRIGore
CC BY-SA 3.0
2012-09-17T23:19:42.710Z
2012-09-17T23:19:42.710Z
Yuval Filmus
<p>Hello the question was also posted on stackoverflow, but since this is theoretical oriented, thought I'd give it a try. I have an undirected graph similar to the one below, I need to implement a graph traversing algorithm.
<strong>Example</strong>: <br/>
<a href="https://i.sstatic.net/4sVRf.png" rel="nofollow noreferrer">https://i.sstatic.net/4sVRf.png</a></p>

<p>The idea is that each vertex is a city, and each edge is a road.<br/>
The weight of an edge represents the time needed to traverse the specified edge.<br/>
The conditions are: <br/></p>

<ol>
<li>Each edge is open for traversal in a specified time window: Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to traverse the edge.<br/></li>
<li>Only some vertices must be visited. The vertices must be visited at leas once in the specified time window for each one:  Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to mark the vertex as visited.<br/></li>
<li>The starting point is always vertex 0 <br/></li>
</ol>

<p>For <strong>my example</strong> I have: <br/>
Vertices that must be visited and their time window (values with -1 are not taken into consideration): <br/></p>

<pre><code>Vertex To1  Tc1  To2  Tc2
  1    0    260  340  770
  4    0    240  -1   -1 
  5    170  450  -1   -1 
</code></pre>

<p>Edges are open in the following time window (values with -1 are not taken into 
consideration):</p>

<pre><code>Edge To1  Tc1  To2  Tc2
0-1  0    770  -1   -1 
0-4  0    210  230  770
0-5  0    260  -1   -1 
1-2  0    160  230  770
1-5  40   770  -1   -1 
2-4  80   500  -1   -1 
3-4  60   770  -1   -1 
3-5  0    770  -1   -1 
</code></pre>

<p>So the basic idea is to start with vertex 0 and find the shortest route to traverse
vertices 1, 4 and 5 taking in consideration the specified time. <br/>
Also if for example you have done 0-1 but you can't use 1-5 you can do 0-1-0-1-5.<br/></p>

<p>I start with vertex 0, end with one target vertex while I have visited all other target vertices at least once respecting the conditions imposed on the edges and target vertices. <br/>
For example: <br/>
A possible solution is 0 - 4 - 3 - 5 - 1 with a total time of 60+50+60+50=220 <br/>
From 0 I can also go directly to 5 but as stated in conditions in order to mark vertex 5 
I must have a cumulative time between 170 and 450. Also if I go 0-4 I can't use edge 4-2 because it opens at 80 and my cumulative time is 60. Note I can use 0-4-3 because 4-3 opens at 60 and to do 0-4 it takes a time equal to 60. 
So is there a way to solve this using dijkstra or other path finding algorithms ?</p>

<p>Thanks in advance for any help!</p>

<p><strong>Edit</strong> <br/></p>

<p>My solution for now is something like this</p>

<pre><code>         0    
  1      4      5
0 2 5  0 2 3  0 1 3 
</code></pre>

<p>Basically I try all possibilities. The conditions for stopping in expanding a branch are: <br/>
1. I have too many duplicates like I have 0 1 0 4 0 1 0 - so I stop because I have a set number of duplicate 0 values which is 4<br/>
2. I find a road that contains all the vertices to mark<br/>
3. I find a road that takes longer than another complete road<br/></p>

CC BY-SA 3.0
2012-09-17T19:45:38.530Z
so if I understand you correctly, you have a graph with edge and vertex windows, and edge weights. Your goal is to visit each of a specified set of target vertices at least once for each time window that it's open using a path of minimum weight ? What happens if the windows for a vertex overlap ? Then would one visit cover both occurrences, or should we assume that no windows overlap. Also, is the "vistor" allowed to stand still, or must it constantly be moving ?
Suresh Venkat
CC BY-SA 3.0
2012-09-18T05:16:24.120Z
There is no problem if the windows overlap. Also the time passes only when you pass an edge. For example if you are in 2 and you need to use 2-4 but it is closed you can do 2-1-2 then you may use 2-4 if it becomes available. It doesn't how many vertices you use you can do even something like 0-1-5-1-4-0-4-3-5-1-5-1-0-4, so any combination as long as it takes the shortest possible time.
hDan
<ds.algorithms><graph-theory><graph-algorithms><application-of-theory>
Graph traversal with vertex and edge deadlines/windows
hDan
# Graph traversal with vertex and edge deadlines/windows

(Asked by: username_0 on 2012-09-17)

Hello the question was also posted on stackoverflow, but since this is theoretical oriented, thought I'd give it a try. I have an undirected graph similar to the one below, I need to implement a graph traversing algorithm.
Example: 
https://i.sstatic.net/4sVRf.png
The idea is that each vertex is a city, and each edge is a road.
The weight of an edge represents the time needed to traverse the specified edge.
The conditions are: 

Each edge is open for traversal in a specified time window: Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to traverse the edge.
Only some vertices must be visited. The vertices must be visited at leas once in the specified time window for each one:  Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to mark the vertex as visited.
The starting point is always vertex 0 

For my example I have: 
Vertices that must be visited and their time window (values with -1 are not taken into consideration): 
Vertex To1  Tc1  To2  Tc2
  1    0    260  340  770
  4    0    240  -1   -1 
  5    170  450  -1   -1 

Edges are open in the following time window (values with -1 are not taken into 
consideration):
Edge To1  Tc1  To2  Tc2
0-1  0    770  -1   -1 
0-4  0    210  230  770
0-5  0    260  -1   -1 
1-2  0    160  230  770
1-5  40   770  -1   -1 
2-4  80   500  -1   -1 
3-4  60   770  -1   -1 
3-5  0    770  -1   -1 

So the basic idea is to start with vertex 0 and find the shortest route to traverse
vertices 1, 4 and 5 taking in consideration the specified time. 
Also if for example you have done 0-1 but you can't use 1-5 you can do 0-1-0-1-5.
I start with vertex 0, end with one target vertex while I have visited all other target vertices at least once respecting the conditions imposed on the edges and target vertices. 
For example: 
A possible solution is 0 - 4 - 3 - 5 - 1 with a total time of 60+50+60+50=220 
From 0 I can also go directly to 5 but as stated in conditions in order to mark vertex 5 
I must have a cumulative time between 170 and 450. Also if I go 0-4 I can't use edge 4-2 because it opens at 80 and my cumulative time is 60. Note I can use 0-4-3 because 4-3 opens at 60 and to do 0-4 it takes a time equal to 60. 
So is there a way to solve this using dijkstra or other path finding algorithms ?
Thanks in advance for any help!
Edit 
My solution for now is something like this
         0    
  1      4      5
0 2 5  0 2 3  0 1 3 

Basically I try all possibilities. The conditions for stopping in expanding a branch are: 
1. I have too many duplicates like I have 0 1 0 4 0 1 0 - so I stop because I have a set number of duplicate 0 values which is 4
2. I find a road that contains all the vertices to mark
3. I find a road that takes longer than another complete road

**Tags:** ds.algorithms, graph-theory, graph-algorithms, application-of-theory

> **Comments:**
> **username_1**: so if I understand you correctly, you have a graph with edge and vertex windows, and edge weights. Your goal is to visit each of a specified set of target vertices at least once for each time window that it's open using a path of minimum weight ? What happens if the windows for a vertex overlap ? Then would one visit cover both occurrences, or should we assume that no windows overlap. Also, is the "vistor" allowed to stand still, or must it constantly be moving ?  
> **username_0**: There is no problem if the windows overlap. Also the time passes only when you pass an edge. For example if you are in 2 and you need to use 2-4 but it is closed you can do 2-1-2 then you may use 2-4 if it becomes available. It doesn't how many vertices you use you can do even something like 0-1-5-1-4-0-4-3-5-1-5-1-0-4, so any combination as long as it takes the shortest possible time.  

---

## 1 answers

### Answer by username_2 on 2012-09-17. Score: 6

It is NP-hard to decide whether your problem is soluble. That's bad news from a theoretical point of view, but in practice it is possible that a heuristic algorithm will fare quite well. Also, you're (possibly) dealing with the "promise" variant of the problem, that is, you assume that a solution exists, and want to find it.

To see that the problem is NP-hard, we reduce Hamiltonian cycle to it. All the edges are always open, and they always have unit weight. The windows for each non-zero vertex are $[1,n-1]$ and $[n+1,2n-1]$; for vertex zero they are $\{0\}$ and $\{n\}$. These constraints are satisfiable only via a Hamiltonian cycle, and the converse is also true.

> **Comments:**
> **username_0**: OK so using a computational approach how can you solve this problem ?  
> **username_2**: That's your question.  
> **username_0**: What I mean if there is a better solution than the one I am currently using.  
> **username_3**: I don't understand the reduction. Is the set of vertices $\{0,1,\ldots,n\}$? Are the windows for $1$ supposed to be empty? If a vertex has two windows then it will be visited twice, which makes the path non-hamiltonian. What am I missing?  
> **username_2**: The set of vertices is $\{0,1,\ldots,n-1\}$. The windows for $0$ are singletons. The first $n$ edges of the path will form a Hamiltonian cycle.  
> **username_3**: Ah, right. (I was thinking that the windows for vertex $k$ are $[1,k-1]$ and $[k+1,2k-1]$. That's why I asked about the window for $1$.)  

---

