# Geometric covers, graph orientations, counter games

Authors:
Abstract:
Geometric Cover is a large family of NP-complete special cases of the broader Set Cover problem. Unlike the general problem, Geometric Cover involves objects that exist in a geometric setting, consequently implying that they are all restricted to obeying some inherent structure. The archetypal example is Line Cover, also known as Point-Line Cover, where a set of points in a geometric space are to be covered by placing a restricted number of lines. We present new FPT algorithms for the sub-family Curve Cover (which includes Line Cover), as well as for Hyperplane Cover restricted to R 3 (i.e. Plane Cover), with improved time complexity compared to the previous best results. Our improvements are derived from a more careful treatment of the geometric properties of the covering objects than before, and invoking incidence bounds from pure geometry. An orientation of an un-directed graph is a directed version of it, i.e. where every un-directed edge in the original graph has been replaced by a directed edge, incident on the same two vertices, in either direction. Graph orientations with low out-degree are desirable as the foundation of data structures with many applications. If the un-directed graph is dynamic (can be altered by some outside actor), some orientations may need to be reversed in order to maintain the low out-degree. We present a new algorithm that is simpler than earlier work, yet matches or outperforms the efficiency of these results with very few exceptions. Counter games are a type of abstract game played over a set of counters holding values, and these values may be moved between counters according to some set of rules. Typically they are played between two players: the adversary who tries to concentrate the greatest value possible in a single counter, and the benevolent player who tries to prevent the adversary from doing so. These counter games are sometimes used as a behind-the-scenes tool for proving the efficiency of an algorithm, i.e. proving that the adversary is unable concentrate more than some specific value in a counter, also proves that the algorithm cannot perform worse than this value. We develop a new counter game with only one player (the adversary), and use it to prove the efficiency of the graph orientation algorithm.
Type:
Thesis PhD
Language:
English
Main Research Area:
Science/technology
Publication Status:
Published
Review type:
Undetermined
Publisher:
Aarhus Universitet, 2017
Submission year:
2017
Scientific Level:
Scientific
ID:
2385983266