Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Program — Combinatorial Algorithms Day 2012

5th Combinatorial Algorithms Day

Monday, June 4th 2012

The first two sessions are in room ML E12. The last session is at "Kino" in Bergün.
Here is a PDF-map of ETH Zentrum.

Session 1 (ML E12)

08:40-08:45 Opening: Emo Welzl
08:45-09:05 Angle-Restricted Steiner Arborescences for Flow Map Layout
Bettina Speckmann, TU Eindhoven
(GREMO Oct 1, 2001 - May 31, 2003)

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.

09:05-09:25 Many Collinear k-tuples with no k+1 Collinear Points
Miloš Stojaković, University of Novi Sad
(GREMO May 15, 2002 - Sept 30, 2005)

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 n2/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 tk(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 tk(n) from below for k>3. Erdős conjectured that tk(n)=o(n2) 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 tk(n)> n2-ε 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.

09:25-09:45 Homogeneous Selections from Hyperplanes
Imre Bárány, Rényi Institute and UCL

Given d+1 hyperplanes h1,...,hd+1 in general position in Rd, there is a unique bounded simplex, to be denoted by Δ(h1,...,hd+1), enclosed by them. The main result is that there exists a constant c(d)>0 such that given finite families H1,...,Hd+1 of hyperplanes in Rd, there are subfamilies Hi* ⊂ Hi with |Hi*|≥ c(d)|Hi| and a point p ∈Rd with the property that p ∈ Δ(h1,...,hd+1) for all hi ∈ Hi*.
Joint work with János Pach.

09:45-10:05 Homometric Sets in Trees
Radoslav Fulek, EPF Lausanne

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 n1/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 cn2/3 for a constant c>0.
Joint work with Slobodan Mitrovic.

10:05-10:25 Improved Approximation for Geometric Unique Coverage Problems
Yoshio Okamoto, UEC Tokyo and JAIST
(GREMO Apr 1, 2002 - Mar 31, 2005)

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.

10:25-10:45 On Rainbow Matchings in Hypergraphs
Tibor Szabó, FU Berlin
(GREMO Sep 1, 2000 - Aug 31, 2008)

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.

10:45-11:05 Monotone Paths in Planar Convex Subdivisions and Polytopes
Csaba Dávid Tóth, University of Calgary
(GREMO from Mar 1, 2000 - Aug 31, 2002)

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.

11:05-11:25 Coffee Break

Session 2 (ML E12)

11:25-11:45 On the Largest Tournament Maker Can Build
Anita Liebenau, FU Berlin

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 Kn 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 kc = (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 = kc - 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.

11:45-12:05 Locally Correct Fréchet Matchings
Kevin Buchin, TU Eindhoven
(GREMO Jan 31, 2005 - Mar 13, 2005)

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(N3 log N) algorithm to compute it, where N is the total number of edges in both curves. We also present an O(N2) algorithm to compute a locally correct discrete Fréchet matching.
Joint work with Maike Buchin, Wouter Meulemans and Bettina Speckmann.

12:05-12:25 On Vertex Ranking of Graphs and its Relatives
Shakhar Smorodinsky, Ben Gurion University
(GREMO Feb 15, 2004 - Oct 31, 2004)

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.

12:25-12:45 A few Comments on Diameter Graphs
Filip Morić, EPF Lausanne

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.

12:45-13:05 Fat Six-gons in the Space
József Solymosi, University of British Columbia
(GREMO Jan 1, 2000 - Mar 31, 2001)

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 cn3/2 such triangles, however it is not known if this number should be o(n2) or not. In this talk we show that cn2 fat six-gons spanned by n points should always determine many intersections.

13:05-13:10 Organizational Remarks: Michael Hoffmann

Session 3 (Kino Bergün)

18:00-18:20 Minimum Entropy Combinatorial Optimization Problems
Jean Cardinal, UL Bruxelles
(GREMO April 1, 2012 - May 31, 2012)

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.

18:20-18:40 Tangles and Degenerate Tangles
Andres Ruiz Vargas, EPF Lausanne

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.

Valid HTML 4.01!