Graph exploration with advice and online crossing minimization

Fuchs, Janosch; Unger, Walter (Thesis advisor); Komm, Dennis (Thesis advisor); Rossmanith, Peter (Thesis advisor)

Aachen : RWTH Aachen University (2022)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2022

Abstract

Online problems reveal their input instance piece by piece and require an irrevocable decision each time a new piece is revealed. This scenario models critical applications where a decision, once it is made, cannot be changed afterwards which also influences future decisions. Like for classical offline problems, it is common to make a worst-case analysis to give a guarantee on the performance of algorithms in this setting, which are called online algorithms. This is achieved by assuming that a malicious adversary, knowing the behavior of the online algorithm, creates the input. Due to the nature of uncertainty online algorithms rarely compute an optimal solution. Thus, their performance is measured in terms of the competitive ratio, which compares the solution computed by the online algorithm to the optimal solution achievable when the whole instance is known beforehand. To measure the impact of the missing knowledge about the future the classical online setting was extended with a helpful oracle providing information about the future input. The online algorithm receives the information by accessing a tape containing a binary bit string prepared by the oracle. The number of bits that the algorithm reads during its computation is called its advice complexity. Bounds on the advice complexity of an online algorithm that optimally solves an online problem show how much information about the future is needed to avoid any mistake. An obvious upper bound for the advice complexity of all online problems is the size of the binary encoding of the input instance or the optimal solution using self-delimiting encoding. But most of the time it is possible to derive better bounds by encoding only critical decisions which then reveals the core difficulty of an online problem. Thus, the advice complexity strongly correlates to the difficulty of an online problem and it can be used to measure the difficulty of different online problems. The first technical part of this thesis considers an online graph drawing problem on degree-bounded bipartite graphs, the so-called online slotted One-Sided Crossing Minimization Problem (online slotted OSCM-$k$). One set of vertices together with a total ordering is fixed on a line and known to the online algorithm. In each step a vertex, which is incident to $k$ vertices of the already known set, needs to be placed on a free placeholder, which we call a slot. The slots are also arranged on a line parallel to the known vertex set. The task is to place the vertices such that the number of edge crossings is minimized, when all edges are drawn as straight lines. Note that the slots make the problem harder to solve for an online algorithm but in the offline case it is equivalent to the version without slots. We prove that the online slotted OSCM-$k$ has no constant competitive ratio. Thus, we look at the problem on $2$-regular graphs and derive constant upper and lower bounds for this restricted graph class. The second part analyzes the advice complexity of a graph exploration problem. Here, an algorithm has to move an agent through a graph from vertex to vertex using the edges such that the agent traverses the cheapest or shortest tour that visits every vertex at least once. The algorithm does not know the graph beforehand and each time the agent is located at a new vertex the reachable neighborhood is revealed together with the cost to reach all neighboring vertices from the current location. Already seen or visited vertices are recognizable. Due to the already known tight upper bound of $n\log(n)$ for the advice complexity of the graph exploration problem on dense graphs, we focus on sparse graphs. We show that the number of advice bits which is sufficient and also necessary to solve the graph exploration problem on directed and undirected graphs is linear in the number of edges. We also investigate how much advice can be saved when the graph structure is known beforehand and only the traveling cost of the edges is unknown.

Institutions

• Department of Computer Science [120000]
• Chair of Computer Science 1 (Algorithms and Complexity) [121110]
• UnRAVeL Research Training Group [080060]