Combinatorial Algorithms Day

Abstract:
In the picturesque maze generation problem, we are given a rectangular black-and-white raster image and want to randomly generate a maze in which the solution path fills up the black pixels. While a simple formulation of the problem faces with NP-hardness, the proposed method generates such a maze in polynomial time by appropriately changing the formulation itself. Therefore, the algorithm itself is quite simple.
Joint work with Ryuhei Uehara (JAIST, Japan)

Abstract:
The game goes as follows - two players, Maker and Breaker, alternately claim edges of a random graph G(n,p). The goal of Maker is to claim all edges of a Hamiltonian cycle, and the goal of Breaker is to prevent Maker from doing so. The question we want to address is: How small can the probability p=p(n) be, so that Maker can still win the game with high probability?
Joint work with Dan Hefetz, Michael Krivelevich and Tibor Szabó.

Abstract:
Given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing enough points contains all colors. The goal is to bound the necessary size of such a strip, as a function of k. We show that if the strip size is at least 2k-1, such a coloring can always be found. We prove that the size of the strip is also bounded in any fixed number of dimensions. In contrast to the planar case, we show that deciding whether a 3D point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. We also consider the problem of coloring a given set of axis-aligned strips, so that any sufficiently covered point in the plane is covered by k colors. We show that in d dimensions the required coverage is at most d(k-1)+1. Lower bounds are given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. Finally, we study a variant where strips are replaced by wedges.
Joint work with: G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman, O. Schwartz, and P. Taslakian.

Abstract:
Curve matching is a fundamental problem that occurs in many applications. We study the problem of measuring partial similarity between curves. Specifically, given two curves, we wish to maximize the total length of subcurves of them that are close to each other, where closeness is measured by the Fréchet distance, a common distance measure for curves. The resulting maximal length is called the partial Fréchet similarity between the two input curves. Given two polygonal curves P and Q in R^d of size n and m, respectively, we present the first exact algorithm that runs in polynomial time to compute F(P,Q), the partial Fréchet similarity between P and Q, under the L_1 and L_\infty norms. Specifically, we formulate the problem of computing F(P,Q) as a longest path problem, and show how to compute this longest path, under the L_1 and L_\infty norm, in O(nm(n+m) log(nm)) time using a ``shortest path map'' type decomposition.

Abstract:
The continuous version of Borsuk graph is roughly defined on a d-dimensional sphere S^d living in R^{d+1} as follows. The set of its vertices is simply the set S^d and two vertices are joined by an edge if they are almost antipodal. We consider a discrete cube-like analogue of Borsuk graph, for which we show a lower and upper bound on its chromatic number. Our bounds depend on a parameter of the graph, which determines at least how far in terms of Hamming distance two vertices must be if they form an edge. While the proof of the upper bound is less involved, the proof of the lower bound relies on topological Borsuk-Ulam theorem. One possible way how to improve our lower bound will be suggested.

Abstract:
A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. Rectangular layouts are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it is desirable for one rectangular layout to represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area- universal if and only if it is one-sided. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whenever such a layout exists.

Abstract:
In the necklace splitting problem, we have an open necklace with k types of beads, a_i beads of the i-th kind and p thieves want to split it by using as few cuts as possible, such that each of them gets \lfloor a_i/p \rfloor or \lceil a_i/p \rceil beads of the i-th kind. They can cut the necklace between any two beads. If the different types of beads are after each other, then it is easy to see that (p-1)k cuts are necessary. That this number is always enough was proved for p=2 by Goldberg and West. Later Alon and West gave a simpler proof using the Borsuk-Ulam theorem. This was generalized to arbitrary p, each kind having a multiple of p number of beads by Alon. I will present a new, combinatorial proof for the necklace splitting problem for two thieves and a generalization.

Abstract:
Recently Andries Brouwer discovered the theorem in the title. I plan to present my proof, and the 1-line proof of Lex Schrijver. (If you like puzzles: try to find this 1-line proof!)

Abstract:
We prove that any 3-connected planar graph on n vertices has less than 5.2852^n spanning trees. For the case that the planar graphs contains no triangle and no quadrilateral we show that the number of its spanning trees can be at most 2.7163^n. As consequence of the latter the grid size needed to realize a 3-polytope with integer coordinates can now be bounded by O(147^n). To bound the number of spanning trees, we consider the class of directed graphs obtained by taking one outgoing edge at each vertex of the original graph. We probabilistically analyze the dependencies between cycles occurring in these graphs. From this we derive a linear program with infinitely many variables that bounds the number of spanning trees in terms of the degree sequence of the graph. We show how to solve the dual program analytically to obtain the final solution.

Abstract:
It is shown that for every finite set of disjoint convex polygonal obstacles in the plane, with a total of n vertices, the free space around the obstacles can be decomposed into open convex cells whose dual graph (defined below) is 2-edge connected. Intuitively, every edge of the dual graph corresponds to a pair of adjacent cells that are both incident to the same vertex.
Joint work with Marwan Al-Jubeh, Michael Hoffmann, Mashhood Ishaque, and Diane L. Souvaine.