5th Combinatorial Algorithms Day

Session 1 (ML E12)

Abstract:
We introduce a new variant of the geometric Steiner arborescence problem, motivated by the layout of flow maps. Flow maps show the movement of objects between places. They reduce visual clutter by bundling lines smoothly and avoiding self-intersections. To capture these properties, our angle-restricted Steiner arborescences, or flux trees, connect several targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source. We study the properties of optimal flux trees and show that they are planar and consist of logarithmic spirals and straight lines. Computing optimal flux trees is NP-hard. Hence we consider a variant of flux trees which uses only logarithmic spirals. Spiral trees approximate flux trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NP-hard, but we present an efficient 2-approximation, which can be extended to avoid "positive monotone" obstacles.
Joint work with Kevin Buchin and Kevin Verbeek.

Abstract:
In the early 60's Paul Erdős asked the following question about point-line incidences in the plane: Is it possible that a planar point set contains many collinear four-tuples, but it contains no five points on a line? There are various constructions for n-element point sets with n²/6 - O(n) collinear triples with no four on a line, but no similar construction is known for larger numbers. To formulate the problem more precisely, given positive integers k and n, let t_k(n) be the number of lines containing exactly k points from P, maximized over all planar n point sets P that do not contain k+1 collinear points. We are concerned about bounding t_k(n) from below for k>3. Erdős conjectured that t_k(n)=o(n²) for k>3 and offered $100 for a proof or disproof. We prove that the conjecture, if true, is sharp --- for any k>3, one can not replace the exponent 2 by a smaller constant. Indeed, our construction shows that for any k>3 and ε>0 we have t_k(n)> n^2-ε when n is large. We note that the exponents of all previously known lower bounds were going to 1 as k went to infinity.
Joint work with József Solymosi.

Abstract:
Given d+1 hyperplanes h₁,...,h_d+1 in general position in R^d, there is a unique bounded simplex, to be denoted by Δ(h₁,...,h_d+1), enclosed by them. The main result is that there exists a constant c(d)>0 such that given finite families H₁,...,H_d+1 of hyperplanes in R^d, there are subfamilies H_i^* ⊂ H_i with |H_i^*|≥ c(d)|H_i| and a point p ∈R^d with the property that p ∈ Δ(h₁,...,h_d+1) for all h_i ∈ H_i^*.
Joint work with János Pach.

Abstract:
Let G = (V,E) denote a simple graph with the vertex set V and the edge set E. The profile of a vertex set V' ⊆ V denotes the multiset of pairwise distances between the vertices of V'. Two disjoint subsets of V are homometric, if their profiles are the same. If G is a tree on n vertices we prove that its vertex sets contains a pair of disjoint homometric subsets of size at least √ n/2  - 1. Previously it was known that such a pair of size at least roughly n^1/3 exists. We get a better result in case of haircomb trees, in which we are able to find a pair of disjoint homometric sets of size at least cn^2/3 for a constant c>0.
Joint work with Slobodan Mitrovic.

Abstract:
Given a set of points and a set of objects, both in the plane, we wish to find a subset of the objects that maximizes the number of points contained in exactly one object in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave polynomial-time approximation algorithms. Their approximation ratios were 18 when the objects were unit disks, and 4 when the objects were axis-parallel unit squares (which was later improved to 2 by van Leeuwen). We improve the approximation ratios to 4+ε for unit disks and 1+ε for axis-parallel unit squares.
Joint work with Takehiro Ito, Shin-ichi Nakano, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno.

Abstract:
Given an edge-colored multihypergraph we investigate the problem of finding a large rainbow matching, that is, a family of pairwise disjoint edges colored with distinct colors. This general scenario was raised with some applications in extremal hypergraph theory in mind, however some versions are also of independent interest. In the talk we investigate the smallest number f=f(r,t) of colors such that any properly f-colored r-uniform multihypergraph where each color class is a matching of size t, contains a rainbow matching of size t. Aharoni and Berger conjectured that for every fixed r, the answer should be linear in t. Alon disproved the precise version of their conjecture and gave a superexponential upper bound. Here we give an upper bound on f that is polynomial in t for every fixed r.
Joint work with Roman Glebov and Benny Sudakov.

Abstract:
Consider a connected subdivision of the plane into n convex faces where exactly k faces are unbounded. Then there is a path with at least Omega(log(n/k) / log log(n/k)) edges that is monotone in some direction. This bound is the best possible. Our methods are constructive and lead to efficient algorithms for computing monotone paths of the length specified above. We also construct a polytope Q with n vertices and triangular faces (with unbounded degree however), such that every monotone path on the 1-skeleton of Q has at most O(log n) edges.
Joint work with Adrian Dumitrescu and Günter Rote.

Session 2 (ML E12)

Abstract:
Two players, called Maker and Breaker, play the following game. Given a tournament T (an orientation of the complete graph) on k vertices, the players claim edges alternately from the complete graph K_n on n vertices, with Maker also choosing a direction for her edge. Maker wins the game if her digraph contains a copy of T. In 2008, Beck showed that the largest undirected clique Maker can build is of order k_c = (2-o(1))log n. Given n large enough, we show that Maker is able to build a tournament of order k = (2-o(1)) log n = k_c - 10. That is, building a tournament is almost as easy for Maker as building an undirected clique. This improves the lower bound of 0.5log n (Beck 2008) and log n (Gebauer 2010). In particular, our result shows that the "random graph intuition" fails for the tournament game.
Joint work with Dennis Clemens and Heidi Gebauer.

Abstract:
The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to ``natural'' matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such matching exists for two polygonal curves and give an O(N³ log N) algorithm to compute it, where N is the total number of edges in both curves. We also present an O(N²) algorithm to compute a locally correct discrete Fréchet matching.
Joint work with Maike Buchin, Wouter Meulemans and Bettina Speckmann.

Abstract:
Given a graph G=(V,E), a vertex ranking is a numbering (i.e., a coloring) of the vertices such that if u and v get the same color then every simple path between u and v contains a vertex with a higher color. This notion has been studied extensively. In this talk we present and study a relaxed notion where we consider only path's of bounded length. The first non-trivial case is when we only consider paths of length at most two. That is, we are interested in a proper coloring with the additional constraint that if u and v have the same color then for any simple path uwv we have that the color of w is greater than that of u. We show asymptotically tight bounds on this chromatic number for some families of graphs.
Joint work with Ilan Karpas.

Abstract:
The diameter graph D(X) of a finite set of points X in a metric space is the graph whose vertices are the points of X, where two vertices are adjacent if and only if their distance is the diameter of X. We will talk about some properties of Euclidean diameter graphs.

Abstract:
Kalai and Ziegler asked the following problem: What is the maximum number of triangles spanned by n points in the 3-space such that the triangles are pairwise disjoint (i.e., their intersection is empty or a common vertex). There is a construction for cn^3/2 such triangles, however it is not known if this number should be o(n²) or not. In this talk we show that cn² fat six-gons spanned by n points should always determine many intersections.

Session 3 (Kino Bergün)

Abstract:
We survey recent results on combinatorial optimization problems in which the objective function is the entropy of a discrete distribution. These include the minimum entropy set cover, minimum entropy orientation, and minimum entropy coloring problems. We examine their approximability properties, and some of their applications, such as haplotype phasing, source coding, and sorting algorithms.
Joint work with S. Fiorini and G. Joret.

Abstract:
A degenerate tangle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either touch at a common vertex or touch in an interior point. A tangle follows the same definition and further requires that every pair of edges that touch do so in a point where only those two edges pass. Pach, Radoičić, and Tóth coined this term to further the understanding surrounding the famous thrackle conjecture of Conway. We show that a degenerate tangle with n vertices has at most n edges. We characterize both tangles and degenerate tangles.