Geometric covers, graph orientations, counter games

Research output: ResearchPh.D. thesis


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
Number of pages81
StateSubmitted - 13 Sep 2017

See relations at Aarhus University Citationformats

ID: 117024138