10th Combinatorial Algorithms Day

Session 1

Abstract:
In the picture-hanging puzzle we are to hang a picture so that the string loops around n nails and the removal of any nail results in a fall of the picture. We show that the length of a sequence representing an element in the free group with n generators that corresponds to a solution of the picture-hanging puzzle must be at least n2^{√ log₂n}.
In other words, this is a lower bound on the length of a sequence representing a non-trivial element in the free group with n generators such that if we replace any of the generators by the identity the sequence becomes trivial.

Abstract:
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, introduced in 1973 by Viktor Klee. 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 ∈ P is seen by at least one guard g ∈ 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 a myriad of research in geometry and in algorithms. However, despite extensive research, the complexity status of the art gallery problem has not been resolved. It has long been known that the problem is NP-hard, but no one has been able to show that it lies in NP. Recently, the computational geometry community became more aware of the complexity class ∃R. The class ∃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 NP ⊆ ∃R.
We prove that the art gallery problem is ∃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 NP unless NP=∃R.
As a corollary of our construction, we prove that for any real algebraic number α there is an instance of the art gallery problem where one of the coordinates of the guards equals α in any guard set of minimum cardinality.
That rules out many geometric approaches to the problem.
This is joint work with Mikkel Abrahamsen and Anna Adamaszek.

Abstract:
The server allocation problem is a facility location problem for a distributed processing scheme on a real-time network. In this problem, we are given a set of users and a set of servers. Then, we consider the following communication process between users and servers. First a user sends his/her request to the nearest server. After receiving all the requests from users, the servers share the requests. A user will then receive the data processed from the nearest server. The goal of this problem is to choose a subset of servers so that the total delay of the above process is minimized. We prove the following approximability and inapproximability results. We first show that the server allocation problem has no polynomial-time approximation algorithm unless P = NP. However, assuming that the delays satisfy the triangle inequality, we design a polynomial-time 3/2-approximation algorithm. When we assume the triangle inequality only among servers, we propose a polynomial-time 2-approximation algorithm. Both of the algorithms are tight in the sense that we cannot obtain better polynomial-time approximation algorithms unless P = NP. Furthermore, we evaluate the practical performance of our algorithms through computational experiments, and show that our algorithms scale better and produce comparable solutions than the previously proposed method based on integer linear programming.
This is joint work with Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Taichi Shiitada.

Session 2

Abstract:
Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are δ-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum δ-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.
This is joint work with Maarten Kleinhans, Marc van Kreveld, Tim Ophelders, Willem Sonke, and Kevin Verbeek.

Abstract:
We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG G=(V,E) in general position can be augmented to a 2-connected PSLG (V,E ∪ E⁺) by adding new edges of total Euclidean length |E⁺| ≤ 2|E|, and this bound is the best possible. An optimal edge set E⁺ can be computed in O(|V|⁴) time; however the problem becomes NP-hard when G is disconnected. Further, there is a sequence of edge insertions and deletions that transforms a connected PSLG G=(V,E) into a plane cycle G'=(V,E') such that |E'| ≤ 2|MST(V)|, and the graph remains connected with edge length below |E|+|MST(V)| at all stages. These bounds are the best possible.
This is joint work with H. Akitaya, R. Inkulu, T. Nichols, D. Souvaine, and C. Winston.

Abstract:
In 1982, Papaioannou posed the question of finding the smallest integer n such that Maker wins the unbiased Maker-Breaker Hamiltonicity game played on edges of K_n, conjecturing it to be n=8. Our goal is to first introduce this problem in more detail, with its history and connections to related positional games. Then we show how we can settle Papaioannou's conjecture in affirmative, along with some of the implications.
This is joint work with Nikola Trkulja.