
The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of
each tree T of order n can be injectively labelled by using the numbers
{1,2,...,n} in such a way that the absolute differences induced on the edges
are pairwise distinct.
We prove the following relaxation of the conjecture for each c>0 and for all
n>n_0(c). Suppose that (i) the maximum degree of T is bounded by O(n/log n),
and (ii) the vertex labels are chosen from the set {1,2,..., (1+c)n}. Then
there is an injective labelling of V(T) such that the absolute differences on
the edges are pairwise distinct. In particular, asymptotically almost all trees
on n vertices admit such a labelling.
As a consequence, for any such tree T we can pack (2+2c)n1 copies of T into
the complete graph of order (2+2c)n1 cyclically. This proves an approximate
version of the RingelKotzig conjecture (which asserts the existence of a
cyclic packing of 2n1 copies of any T into the complete graph of order 2n1)
for these trees.
The proof proceeds by showing that a certain very natural randomized
algorithm produces a desired labelling with high probability.

We prove that the art gallery problem is equivalent under polynomial time
reductions to deciding whether a system of polynomial equations over the real
numbers has a solution. The art gallery problem is a classical problem in
computational geometry. Given a simple polygon $P$ and an integer $k$, the goal
is to decide if there exists a set $G$ of $k$ guards within $P$ such that every
point $p\in P$ is seen by at least one guard $g\in G$. Each guard corresponds
to a point in the polygon $P$, and we say that a guard $g$ sees a point $p$ if
the line segment $pg$ is contained in $P$.
The art gallery problem has stimulated extensive research in geometry and in
algorithms. However, the complexity status of the art gallery problem has not
been resolved. It has long been known that the problem is $\text{NP}$hard, but
no one has been able to show that it lies in $\text{NP}$. Recently, the
computational geometry community became more aware of the complexity class
$\exists \mathbb{R}$. The class $\exists \mathbb{R}$ consists of problems that
can be reduced in polynomial time to the problem of deciding whether a system
of polynomial equations with integer coefficients and any number of real
variables has a solution. It can be easily seen that $\text{NP}\subseteq
\exists \mathbb{R}$. We prove that the art gallery problem is $\exists
\mathbb{R}$complete, implying that (1) any system of polynomial equations over
the real numbers can be encoded as an instance of the art gallery problem, and
(2) the art gallery problem is not in the complexity class $\text{NP}$ unless
$\text{NP}=\exists \mathbb{R}$. As a corollary of our construction, we prove
that for any real algebraic number $\alpha$ there is an instance of the art
gallery problem where one of the coordinates of the guards equals $\alpha$ in
any guard set of minimum cardinality. That rules out many geometric approaches
to the problem.

We consider very natural "fence enclosure" problems studied by Capoyleas,
Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a
set $S$ of $n$ points in the plane, we aim at finding a set of closed curves
such that (1) each point is enclosed by a curve and (2) the total length of the
curves is minimized. We consider two main variants. In the first variant, we
pay a unit cost per curve in addition to the total length of the curves. An
equivalent formulation of this version is that we have to enclose $n$ unit
disks, paying only the total length of the enclosing curves. In the other
variant, we are allowed to use at most $k$ closed curves and pay no cost per
curve.
For the variant with at most $k$ closed curves, we present an algorithm that
is polynomial in both $n$ and $k$. For the variant with unit cost per curve, or
unit disks, we present a nearlinear time algorithm.
Capoyleas, Rote, and Woeginger solved the problem with at most $k$ curves in
$n^{O(k)}$ time. Arkin, Khuller, and Mitchell used this to solve the unit cost
per curve version in exponential time. At the time, they conjectured that the
problem with $k$ curves is NPhard for general $k$. Our polynomial time
algorithm refutes this unless P equals NP.

We present an $(1+\varepsilon)$approximation algorithm with quasipolynomial
running time for computing the maximum weight independent set of polygons out
of a given set of polygons in the plane (specifically, the running time is
$n^{O( \mathrm{poly}( \log n, 1/\varepsilon))}$). Contrasting this, the best
known polynomial time algorithm for the problem has an approximation ratio
of~$n^{\varepsilon}$. Surprisingly, we can extend the algorithm to the problem
of computing the maximum weight subset of the given set of polygons whose
intersection graph fulfills some sparsity condition. For example, we show that
one can approximate the maximum weight subset of polygons, such that the
intersection graph of the subset is planar or does not contain a cycle of
length $4$ (i.e., $K_{2,2}$). Our algorithm relies on a recursive partitioning
scheme, whose backbone is the existence of balanced cuts with small complexity
that intersect polygons from the optimal solution of a small total weight.
For the case of large axisparallel rectangles, we provide a polynomial time
$(1+\varepsilon)$approximation for the maximum weight independent set.
Specifically, we consider the problem where each rectangle has one edge whose
length is at least a constant fraction of the length of the corresponding edge
of the bounding box of all the input elements. This is now the most general
case for which a PTAS is known, and it requires a new and involved partitioning
scheme, which should be of independent interest.

In this paper we study the art gallery problem, which is one of the
fundamental problems in computational geometry. The objective is to place a
minimum number of guards inside a simple polygon such that the guards together
can see the whole polygon. We say that a guard at position $x$ sees a point $y$
if the line segment $xy$ is fully contained in the polygon.
Despite an extensive study of the art gallery problem, it remained an open
question whether there are polygons given by integer coordinates that require
guard positions with irrational coordinates in any optimal solution. We give a
positive answer to this question by constructing a monotone polygon with
integer coordinates that can be guarded by three guards only when we allow to
place the guards at points with irrational coordinates. Otherwise, four guards
are needed. By extending this example, we show that for every $n$, there is
polygon which can be guarded by $3n$ guards with irrational coordinates but
need $4n$ guards if the coordinates have to be rational. Subsequently, we show
that there are rectilinear polygons given by integer coordinates that require
guards with irrational coordinates in any optimal solution.

Strip packing is a classical packing problem, where the goal is to pack a set
of rectangular objects into a strip of a given width, while minimizing the
total height of the packing. The problem has multiple applications, e.g. in
scheduling and stockcutting, and has been studied extensively.
When the dimensions of objects are allowed to be exponential in the total
input size, it is known that the problem cannot be approximated within a factor
better than $3/2$, unless $\mathrm{P}=\mathrm{NP}$. However, there was no
corresponding lower bound for polynomially bounded input data. In fact,
Nadiradze and Wiese [SODA 2016] have recently proposed a $(1.4 + \epsilon)$
approximation algorithm for this variant, thus showing that strip packing with
polynomially bounded data can be approximated better than when exponentially
large values in the input data are allowed. Their result has subsequently been
improved to a $(4/3 + \epsilon)$ approximation by two independent research
groups [FSTTCS 2016, arXiv:1610.04430]. This raises a question whether strip
packing with polynomially bounded input data admits a quasipolynomial time
approximation scheme, as is the case for related twodimensional packing
problems like maximum independent set of rectangles or twodimensional
knapsack.
In this paper we answer this question in negative by proving that it is
NPhard to approximate strip packing within a factor better than $12/11$, even
when admitting only polynomially bounded input data. In particular, this shows
that the strip packing problem admits no quasipolynomial time approximation
scheme, unless $\mathrm{NP} \subseteq \mathrm{DTIME}(2^{\mathrm{polylog}(n)})$.

In this paper we investigate the colorful components framework, motivated by
applications emerging from comparative genomics. The general goal is to remove
a collection of edges from an undirected vertexcolored graph $G$ such that in
the resulting graph $G'$ all the connected components are colorful (i.e., any
two vertices of the same color belong to different connected components). We
want $G'$ to optimize an objective function, the selection of this function
being specific to each problem in the framework.
We analyze three objective functions, and thus, three different problems,
which are believed to be relevant for the biological applications: minimizing
the number of singleton vertices, maximizing the number of edges in the
transitive closure, and minimizing the number of connected components.
Our main result is a polynomial time algorithm for the first problem. This
result disproves the conjecture of Zheng et al. that the problem is $ NP$hard
(assuming $P \neq NP$). Then, we show that the second problem is $ APX$hard,
thus proving and strengthening the conjecture of Zheng et al. that the problem
is $ NP$hard. Finally, we show that the third problem does not admit
polynomial time approximation within a factor of $V^{1/14  \epsilon}$ for
any $\epsilon > 0$, assuming $P \neq NP$ (or within a factor of $V^{1/2 
\epsilon}$, assuming $ZPP \neq NP$).

The Maximum Weight Independent Set of Polygons problem is a fundamental
problem in computational geometry. Given a set of weighted polygons in the
2dimensional plane, the goal is to find a set of pairwise nonoverlapping
polygons with maximum total weight. Due to its wide range of applications, the
MWISP problem and its special cases have been extensively studied both in the
approximation algorithms and the computational geometry community. Despite a
lot of research, its general case is not wellunderstood. Currently the best
known polynomial time algorithm achieves an approximation ratio of n^(epsilon)
[Fox and Pach, SODA 2011], and it is not even clear whether the problem is
APXhard. We present a (1+epsilon)approximation algorithm, assuming that each
polygon in the input has at most a polylogarithmic number of vertices. Our
algorithm has quasipolynomial running time.
We use a recently introduced framework for approximating maximum weight
independent set in geometric intersection graphs. The framework has been used
to construct a QPTAS in the much simpler case of axisparallel rectangles. We
extend it in two ways, to adapt it to our much more general setting. First, we
show that its technical core can be reduced to the case when all input polygons
are triangles. Secondly, we replace its key technical ingredient which is a
method to partition the plane using only few edges such that the objects
stemming from the optimal solution are evenly distributed among the resulting
faces and each object is intersected only a few times. Our new procedure for
this task is not more complex than the original one, and it can handle the
arising difficulties due to the arbitrary angles of the polygons. Note that
already this obstacle makes the known analysis for the above framework fail.
Also, in general it is not well understood how to handle this difficulty by
efficient approximation algorithms.

In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are
given a set of n axisparallel rectangles in the 2Dplane, and the goal is to
select a maximum weight subset of pairwise nonoverlapping rectangles. Due to
many applications, e.g. in data mining, map labeling and admission control, the
problem has received a lot of attention by various research communities. We
present the first (1+epsilon)approximation algorithm for the MWISR problem
with quasipolynomial running time 2^{poly(log n/epsilon)}. In contrast, the
best known polynomial time approximation algorithms for the problem achieve
superconstant approximation ratios of O(log log n) (unweighted case) and O(log
n / log log n) (weighted case).
Key to our results is a new geometric dynamic program which recursively
subdivides the plane into polygons of bounded complexity. We provide the
technical tools that are needed to analyze its performance. In particular, we
present a method of partitioning the plane into small and simple areas such
that the rectangles of an optimal solution are intersected in a very controlled
manner. Together with a novel application of the weighted planar graph
separator theorem due to Arora et al. this allows us to upper bound our
approximation ratio by (1+epsilon).
Our dynamic program is very general and we believe that it will be useful for
other settings. In particular, we show that, when parametrized properly, it
provides a polynomial time (1+epsilon)approximation for the special case of
the MWISR problem when each rectangle is relatively large in at least one
dimension. Key to this analysis is a method to tile the plane in order to
approximately describe the topology of these rectangles in an optimal solution.
This technique might be a useful insight to design better polynomial time
approximation algorithms or even a PTAS for the MWISR problem.

We prove that if two graphs of girth at least 6 have isomorphic squares, then
the graphs themselves are isomorphic. This is the best possible extension of
the results of Ross and Harary on trees and the results of Farzad et al. on
graphs of girth at least 7. We also make a remark on reconstruction of graphs
from their higher powers.

We study the problem of recognizing graph powers and computing roots of
graphs. We provide a polynomial time recognition algorithm for rth powers of
graphs of girth at least 2r+3, thus improving a bound conjectured by Farzad et
al. (STACS 2009). Our algorithm also finds all rth roots of a given graph that
have girth at least 2r+3 and no degree one vertices, which is a step towards a
recent conjecture of Levenshtein that such root should be unique. On the
negative side, we prove that recognition becomes an NPcomplete problem when
the bound on girth is about twice smaller. Similar results have so far only
been attempted for r=2,3.

Let P be a set of n points in the Euclidean plane and let O be the origin
point in the plane. In the ktour cover problem (called frequently the
capacitated vehicle routing problem), the goal is to minimize the total length
of tours that cover all points in P, such that each tour starts and ends in O
and covers at most k points from P.
The ktour cover problem is known to be NPhard. It is also known to admit
constant factor approximation algorithms for all values of k and even a
polynomialtime approximation scheme (PTAS) for small values of k, i.e.,
k=O(log n / log log n).
We significantly enlarge the set of values of k for which a PTAS is provable.
We present a new PTAS for all values of k <= 2^{log^{\delta}n}, where \delta =
\delta(\epsilon). The main technical result proved in the paper is a novel
reduction of the ktour cover problem with a set of n points to a small set of
instances of the problem, each with O((k/\epsilon)^O(1)) points.