# Bi-Weekly Talk: Janosch Fuchs: Graph Exploration Revisited

### Wednesday, August 12, 2020, 10:30am

Location: Online session

Speaker: Janosch Fuchs

Abstract:

Graph Exploration is an online variation of the famous traveling

salesman problem. In contrast to the offline version, visiting a vertex

multiple times is allowed. So, the task is to compute the shortest

cyclic tour that visits every vertex at least once. We use the, so

called, fixed graph scenario, which defines how the graph is revealed in

the online setting. That means, that the algorithm moves an explorer

from vertex to vertex along the edges and knows only the already visited

vertices, their (outgoing) edges and the adjacent vertices.

In this online setting it is impossible for a deterministic online

algorithm to compute the optimal tour. Thus, we focus on the required

amount of information about the future such that a deterministic

algorithm can compute the optimal solution of the graph exploration

problem. We measure this amount in form of the length of a binary string

that must be communicated to the algorithm. The number of needed bits is

called the advice complexity.

We improve the lower and upper bounds from previous research by

improving the structural analysis of the graph induced by an optimal

tour. The new algorithm works on directed graphs with outgoing degree of

two. With additional advice, this algorithm can be extended to general

graphs without bounded outdegree. We also introduce specialized

algorithms that solve the graph exploration problem with advice on

special graph classes.