11th Combinatorial Algorithms Day

Session 1

Abstract:
We propose a new combinatorial optimization problem that we call the submodular reassignment problem. We are given k submodular functions over the same ground set, and we want to find a set that minimizes the sum of the distances to the sets of minimizers of all functions. The problem is motivated by a two-stage stochastic optimization problem with recourse summarized as follows. We are given two tasks to be processed and want to assign a set of workers to maximize the sum of profits. However, we do not know the value functions exactly, but only know a finite number of possible scenarios. Our goal is to determine the first-stage allocation of workers to minimize the expected number of reallocated workers after a scenario is realized at the second stage. This problem can be modeled by the submodular reassignment problem.
We prove that the submodular reassignment problem can be solved in strongly polynomial time via submodular function minimization. We further provide a maximum-flow formulation of the problem that enables us to solve the problem without using a general submodular function minimization algorithm, and more efficiently both in theory and in practice. In our algorithm, we make use of Birkhoff's representation theorem for distributive lattices.
This is joint work with Naoyuki Kamiyama, Naonori Kakimura and Yusuke Kobayashi.

Abstract:
We say that an algorithm is stable if small changes in the input result in small changes in the output. This kind of algorithm stability is particularly relevant when analyzing and visualizing time-varying data. Stability in general plays an important role in a wide variety of areas, such as numerical analysis, machine learning, and topology, but is poorly understood in the context of (combinatorial) algorithms. We present a framework for analyzing the stability of algorithms and focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees.
This is joint work with Wouter Meulemans, Kevin Verbeek, und Jules Wulms.

Abstract:
The concept of biased Maker-Breaker games, introduced by Chvátal and Erdős, is a central topic in the field of positional games, with deep connections to the theory of random structures. For any given hypergraph ℋ the main questions is to determine the smallest bias q(ℋ) that allows Breaker to force that Maker ends up with an independent set of ℋ. In the talk we discuss recent joint work with Chris Kusch, Juanjo Rue, and Christoph Spiegel, about matching general winning criteria for Maker and Breaker when the game hypergraph satisfies a couple of natural “container-type” regularity conditions about the degree of subsets of its vertices. These enable us to derive a hypergraph generalization of the ℋ-building games, studied for graphs by Bednarska and Łuczak. Furthermore, we investigate the biased version of generalizations of the van der Waerden games introduced by Beck. We refer to these generalizations as Rado games and determine their threshold bias up to constant factor by applying our general criteria. We find it quite remarkable that a purely game theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, when the generalizations to hypergraphs in the analogous setup of sparse random discrete structures are usually quite challenging.

Abstract:
Say that a family of sets satisfy the (p,q)-property for some fixed integers P ≥ q ≥ 2 if out of every p members some q have a non-empty intersection. Wegner and (independently) Dol'nikov (almost 50 years ago) used a (p,2)-theorem for axis-parallel rectangles to prove the following tight (p,q)-theorem for q>√2p: If a family of axis-parallel rectangles in the plane satisfy the (p,q)-property, then the family can be pierced by p-q+1 points. It is easily seen that the value p-q+1 is best possible for any family satisfying the (p,q)-property. These were the only values of q (in the range q>√2p ) that such a tight bound on the piercing number was known.
In this talk we present a general method which allows using a (p,2)-theorem as a bootstrapping to obtain a tight (p,q)-theorem, for families with Helly number 2, even without assuming that the sets in the family are convex or compact. To demonstrate the strength of this method, we obtain an improvement of Wegner and Dol'nikov's result. Namely, we show that the bound p-q+1 above holds for all q ≥ 7 log p (compared to q ≥ √2p of Wegner and Dol'nikov).
This is joint work with Chaya Keller.

Session 2

Abstract:
In the Planar 3-SAT problem, we are given a 3-SAT formula together with its incidence graph, which is planar, and are asked whether this formula is satisfiable. Since Lichtenstein's proof that this problem is NP-complete, it has been used as a starting point for a large number of reductions. In the course of this research, different restrictions on the incidence graph of the formula have been devised, for which the problem also remains hard. We investigate the restriction in which we require that the incidence graph is augmented by the edges of a Hamiltonian cycle that first passes through all variables and then through all clauses, in a way that the resulting graph is still planar. The problem of deciding satisfiability of a 3-SAT formula turns out to remain NP-complete even if the incidence graph is restricted in that way and the Hamiltonian cycle is given. This complements previous results demanding cycles only through either the variables or clauses. In contrast to that, some other restricted versions of planar 3-SAT turn out to be always satisfiable.

Abstract:
A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z₂-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective (t x t)-grid or one of the following so-called t-Kuratowski graphs: K_3,t, or t copies of K₅ or K_3,3 sharing at most two common vertices. We show that the Z₂-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z₂-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani–Tutte theorem on orientable surfaces.
This is joint work with Jan Kynčl.

Abstract:
Background to several open problems related to the Erdős-Szekeres (Happy Ending) Theorem will be outlined. The open problems include the following questions in ℝ³:

1. For a given k>0, what is the minimum integer n>0 such that every set of n points in general position in ℝ³ contains k convexly independent points. In particular, does n=n(k) grow exponentially with k?
2. Is there a positive integer n such that any set P of n points in general position in ℝ³ contains an 8-hole, that is, a set of 8 convexly independent points such that the interior of their convex hull contains no point of P?

Abstract:
We introduce and study a novel semi-random graph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v.
For various natural monotone increasing graph properties P, we give tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies P. Along the way, we show that the process is general enough to approximate (using suitable strategies) several well-studied random graph models.
This is joint work with Omri Ben-Eliezer, Dan Hefetz, Gal Kronenberg, Olaf Parczyk and Clara Shikhelman.