# Foremost Walks and Paths in Interval Temporal Graphs +
## 1 Introduction
[12] present a new data structure for contact-sequence graphs that results in faster algorithms for many of the path problems studied in [8]. While [9] focuses on interval-temporal graphs, refs. [8; 10] use the contact-sequence model. Ref. [10] presents an algorithm for finding walks that optimize any linear combination of eight different optimization criteria \((foremost,reverse_{foremost},fastest,shortest,cheapest,most_{likely},min_{ hop},min_{wait})\). In our earlier paper [13], we developed algorithms to find optimal foremost and min-hop paths in interval-temporal graphs. These algorithms were demonstrated experimentally to run faster than earlier algorithms for these problems. A temporal graph may have many walks/paths that optimize a criterion such as foremost. In some applications, it is required to find a walk/path that optimizes a secondary criterion from among all walks/paths that optimize a primary criterion. For example, we may desire a min-wait foremost path (i.e., a foremost path in which the sum of the wait times at intermediate vertices is minimized) or a min-hop foremost path (a foremost path that goes through the fewest number of edges). For example, when selecting flights to go from \(A\) to \(B\) one may wish to use a min-wait foremost path (a route that minimizes the total wait time at intermediate airports while getting to the destination at the earliest possible time) or a min-hop foremost path (a route that involves the fewest number of connections while guaranteeing the earliest possible arrival time). In this paper, we examine the min-wait, min-hop, and min-cost (each edge or edge interval has an additional attribute, its cost), foremost walks/paths problems. As discussed in Section 6, the algorithm by [PERSON] et al. can be tuned by carefully choosing the coefficients for different optimization criteria to find min-hop foremost paths and min-wait foremost walks in contact-sequence temporal graphs. We use this method to benchmark our algorithms against the algorithm by [PERSON] et al. and show that we perform about 207.5 times faster for finding min-hop foremost paths and up to 23.3 times faster for finding min-wait foremost walks. Further, we solve these problems on the interval-temporal graphs that can represent a wider problem space for temporal graphs, as opposed to the contact-sequence temporal graphs. Our main contributions in this paper are:  
1. We show that the problems for finding min-cost foremost and min-wait foremost paths and walks in interval temporal graphs are NP-hard. 2. We develop a polynomial time algorithm for the single-source all-destinations min-hop foremost paths problem in interval-temporal graphs. 3. We develop a pseudopolynomial time algorithm for the single-source all-destinations min-wait foremost walks problem in interval-temporal graphs. 4. We show that the problem of finding min-hop foremost paths and min-wait foremost walks can be modeled using the linear combination formulation employed in Section 6 when the optimization criteria are discrete (e.g., time is discrete). Our modeling methodology readily extends to other primary and secondary criteria as well as to multiple levels of secondary criteria (e.g., shortest min-hop foremost path). 5. We benchmark our algorithms against the algorithm of [PERSON] et al. [10] using datasets for which the preceding modeling can be used. On these datasets, our algorithm is up to 207.5 times faster for finding min-hop foremost paths and up to 23.3 faster for finding min-wait foremost walks. The roadmap of this paper is as follows. In Section 2, we describe the problems of finding min-hop foremost paths (\(mhf\) paths), min-wait foremost walks (\(mwf\) walks), and min-cost foremost paths (\(mcf\) paths). In Section 3, we show that the problems of finding \(mwf\) paths and walks and the problem for finding \(mcf\) paths in interval temporal graphs are NP-hard. In Section 4, we present theorems that describe the properties of min-hop foremost paths in temporal graphs.