Geometric covers, graph orientations, counter games

Research output: Book/anthology/dissertation/reportPh.D. thesisResearch

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.
Original languageEnglish
Place of publicationAarhus
PublisherAarhus Universitet
Number of pages83
Publication statusPublished - 11 Dec 2017

See relations at Aarhus University Citationformats

ID: 117024138