Seminár z teoretickej informatiky - Stefan Dobrev (19.5.2017)

v piatok 19.5.2017, 11:00 hod. v miestnosti M/213

16. 05. 2017 12.57 hod.
Od: Rastislav Kralovič

Prednášajúci: Stefan Dobrev

Názov: Efficient Periodic Traversal on Graphs with Given Rotation Systems

Termín: 19.5.2017, 11:00 hod., M/213

We consider periodic graph traversal in anonymous undirected graphs by a finite state Mealy automaton (agent). The nodes are anonymous, but the ports in each node have unique (within the node) labels. The problem is to design an automaton A and a port re-labeling scheme L such that A performs on L(G) an infinite walk w, periodically visiting all nodes. The goal is to minimize the revisit time (traversal period) pi of w.
If L cannot change the input labels, it has been shown by Budach that the problem is unsolvable. If L can in node v use deg(v)+1 labels, it can encode a spanning tree and traversal with period 2n-2 is trivial even with an oblivious agent. The problem is interesting when L is limited to be a permutation.
The best known upper bound on the traversal period in such case is 3.5n - 2 by Czyzowicz et al., where n is the number of nodes of G. It is an open problem whether it is possible to achieve traversal period 2n-2.
In this paper, we answer this question affirmatively under the assumption that that the input graph G is given with a rotation system. A rotation system of a graph is a combinatorial encoding of graph's embedding into an orientable surface. This encoding can be described by specifying a circular ordering of edges around each node.
While this is clearly an additional information, it appears to be barely sufficient to solve the problem with the optimal period 2n-2: Several aspects of the construction need to fit 'just right' to solve all the technical issues, especially in graphs with small maximal degree (3 or 4).