Bi-Weekly Talk: Janosch Fuchs: Graph Exploration Revisited

Mittwoch, 12.08.2020, 10.30 Uhr

Ort: Online session

Vortragender: 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.