4th Combinatorial Algorithms Day

Abstract:
We will look at so-called Box Games, which are Maker-Breaker games with a simple structure, namely all of the winning sets are mutually disjoint. These games often arise in the analysis of more complex positional games. Chvátal and Erdős in 1978 resolved the question of who wins the Box Game if all winning sets are of the same size, and we will continue in this direction - looking at arbitrary Box Games, trying to determine their outcome and winning strategies for both players.
Joint work with Dan Hefetz, Michael Krivelevich and Tibor Szabó.

Abstract:
We propose a simple method to encode a reduced tree that is a rooted tree with no children ordering and has no internal vertex with one child. The bound of the code length derives a tighter bound on the number of co-graphs. We also show a modification to encode a series-parallel graphs and a bound on their number.

Abstract:
Let R₁ (resp. R₂) denote the set of graphs that have a drawing in the plane such that the edges are represented by polygonal arcs with at most 1 (resp. 2) bends and any two edges can cross only at a right angle. We show that all graphs in R₁ and R₂ have O(n) edges.

Abstract:
The PPAD complexity class was introduced by Papadimitriou and received much attention recently due to the fact that NASH was shown to be PPAD-complete. We start with basic definitions and argue why the name of this class should be something else. Then we focus on combinatorial problems that are complete for this class, like SPERNER, TUCKER and END-OF-THE-LINE for directed planar graphs. For example, the 2-dimensional Tucker-lemma states that if we triangulate the unit disc centered at the origin and color the vertices with {1,-1,2,-2} in an antipodal way (if |z|=1, then the sum of the colors of z and -z is zero), then there must be an edge for which the sum of the colors of its endpoints is zero. But how hard is it to find such an edge? We show that if the triangulation is exponentially large and the coloring is determined by a deterministic Turing-machine, then this problem is PPAD-complete.

Abstract:
A regular edge labeling (REL) of an irreducible triangulation G uniquely defines a rectangular dual of G. Rectangular duals find applications in various areas: as floor plans of electronic chips, in architectural designs, as rectangular cartograms, or as treemaps. An irreducible triangulation can have many RELs and hence many rectangular duals. Depending on the specific application different duals might be desirable. We consider optimization problems on RELs and show how to find optimal or near-optimal RELs for various quality criteria. Along the way we give upper and lower bounds on the number of RELs.

Abstract:
We deal with a Turán-type problem: given a positive integer n and a forbidden graph H, how many edges can there be in a graph on n vertices without a subgraph H? And how does a graph look like, if it has this extremal edge number? The forbidden graph in this talk is a clique-path, that is a k-path, where each edge is blown up to an r-clique, r≥3. We determine both the extremal number and the extremal graphs for sufficiently large n.

Abstract:
This work studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h=0), it is known that the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time. For general polygonal domains with h≥1, however, no algorithm for computing the geodesic diameter was known prior to this work. In this work, we present the first algorithm that computes the geodesic diameter of a given polygonal domain in worst-case time O(n^7.73) or O(n⁷ (log n + h)). Among other results, we show the following geometric observation: the geodesic diameter can be determined by two points in its interior. In such a case, there are at least five shortest paths between the points.
Joint work with Sang Won Bae and Matias Korman.

Abstract:
Given a hypergraph H=(V,E), a coloring of its vertices is said to be conflict-free if for every hyperedge S∈E there is at least one vertex whose color is distinct from the colors of all other vertices in S. The study of this notion is motivated by frequency assignment problems in wireless networks. We introduce and study the list-coloring (or choice) version of this notion.
Joint work with Panagiotis Cheilaris.

Abstract:
One of the best known problems in discrete geometry is Erdős' unit distances problem: what is the maximum number of unit distances determined by n points in the plane? The conjecture is that the number of unit distances is not more than n^1+o(1). We will show that the upper bound n^1+o(1) holds if we only consider unit distances that have rational angle, by which we mean that the line through the pair of points makes a rational angle in degrees with the x-axis.

Abstract:
The (k,s)-SAT problem involves SAT formulas where each clause has k distinct literals and each variable appears in at most s clauses. The maximum value f(k) for which every (k,f(k))-SAT formula is satisfiable has very interesting properties and it is widely studied. The Local Lemma can be used to give a lower bound on f(k). Recently Gebauer showed that this bound is correct up to a constant factor. In the talk we indicate the construction of an unsatisfiable (k,s)-SAT formula, which shows that the lower bound provided by the Local Lemma is asymptotically tight.
Joint work with Heidi Gebauer and Gabor Tardos.