In this talk I present several results obtained during my PhD studies.

We first present the model of dynamic and fault-tolerant graph algorithms. We then focus on variants of shortest path algorithms and data-structures in setting with failures. In particular, we study the following problems.

Distance Sensitivity Oracles. An f-Sensitive Distance Oracle (f-DSO) with stretch \(\alpha\) preprocesses a graph \(G(V,E)\) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set \(F \subset E\) of at most \(f\) edges, and vertices s and t. The oracle answers a query \((F,s,t)\) by returning a value \(\tilde{d}\) which is equal to the length of some path between \(s\) and \(t\) in the graph \(G\setminus F\) (the graph obtained from \(G\) by discarding all edges in \(F\)). Moreover, \(\tilde{d}\) is at most \(\alpha\) times the length of the shortest path between \(s\) and \(t\) in \(G\setminus F\). The oracle can also construct a path between \(s\) and \(t\) in \(G\setminus F\) of length \(\tilde{d}\).

Here we present several results regarding distance sensitivity oracles. First, in a joint work with Shiri Chechik, Amos Fiat and Haim Kaplan [SODA 2017] we presented, to the best of our knowledge the first nontrivial \(f\)-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any \(f = o(\frac{\log n}{\log \log n})\) and a fixed \(\varepsilon > 0\) our oracle answers queries \((F,s,t)\) in time \(\widetilde{O}(1)\) with \((1+\varepsilon)\) stretch using a data structure of size \(n^{2+o(1)}\). For comparison, the naive alternative requires \(m^fn^2\) space for sublinear query time.

Second, in a joint work with Shiri Checik [STOC 2020], we presented the first distance sensitivity oracle with subcubic preprocessing time and very fast query time for directed graphs with integer weights in the range \([-M,M]\). Our distance sensitive oracle supports a single vertex/edge failure in subcubic \(\tilde{O}(Mn^{\omega+1/2}) = \tilde{O}(Mn^{2.873})\) preprocessing time for \(\omega=2.373\), and near optimal query time of \(\tilde{O}(1)\). For comparison, with the same \(\tilde{O}(Mn^{2.873})\) preprocessing time the DSO of Grandoni and Vassilevska Williams [FOCS 12] has \(\tilde{O}(n^{0.693})\) query time. In fact, the best query time their algorithm can obtain is \(\tilde{O}(Mn^{0.385})\) (with \(\tilde{O}(Mn^3)\) preprocessing time).

The Replacement Paths problem. Let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from \(s\) to \(t\) in \(G\). The {\sl replacement paths} problem is to find for every edge \(e \in P\) the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of \(\tilde{O}(m \sqrt{n})\).

In a joint work with Shiri Chechik and Noga Alon we presented the first deterministic algorithm for this problem [ICALP 2019], with the same \(\tilde{O}(m \sqrt{n})\) time. Due to matching conditional lower bounds of Williams {\sl et. al.} [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of \(\tilde{O}(mn)\) for the combinatorial boolean matrix multiplication can be improved).

The Single Source Replacement Paths Problem. Given a graph \(G=(V,E)\) with n vertices and m edges, a source vertex \(s\) and a shortest paths tree \(T_s\) rooted in \(s\), output for every vertex \(t \in V\) and for every edge \(e\) in \(T_s\) the length of the shortest path from \(s\) to \(t\) avoiding \(e\).

In a joint work with Shiri Chechik [SODA 2019], we presented near optimal upper bounds, by providing \(\tilde{O}(m\sqrt{n} +n^2)\) time randomized combinatorial algorithm for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.

The Young Physicists Tournament is an established team-oriented scientific competition between high school students from 37 countries on 5 continents. The competition consists of scientific discussions called Fights. Three or four teams participate in each Fight, each of whom presents a problem while rotating the roles of Presenter, Opponent, Reviewer, and Observer among them.

The rules of a few countries require that each team announce in advance 3 problems they will present at the national tournament. The task of the organizers is to choose the composition of Fights in such a way that each team presents each of its chosen problems exactly once and within a single Fight no problem is presented more than once. Besides formalizing these feasibility conditions, in this paper we formulate several additional fairness conditions for tournament schedules. We show that the fulfillment of some of them can be ensured by constructing suitable edge colorings in bipartite graphs. To find fair schedules, we propose integer linear programs and test them on real as well as randomly generated data.

In this work, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the multiflow-multicut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a 1/4-approximation algorithm for maximum integer multiflows (and hence the edge disjoint paths problem), and an integer-multiflow-multicut gap of 8.

Submodular functions capture the notion of diminishing returns. This notion occurs frequently in the real world, thus, the problem of maximizing a submodular function finds applicability in a plethora of scenarios. While being NP-hard and APX-hard, submodular maximization problems admit non-trivial approximation algorithms.

In this talk, I will discuss how submodularity can be used to design efficient algorithms to tackle real-world optimization problems. I will describe three relevant AI problems and, for each one of them, I will give an approximation algorithm. I will show how the notion of submodularity pertains each problem, and how it was used to design the corresponding approximation algorithms.

This talk deals with graph embeddings into spaces of non-constant curvature. I will at first review applications of graph embeddings, their advantages and flaws. These comprise in particular dealing with structures of non-hierarchical fashion, i.e. structures which do not fit in spaces of constant curvature. Without delving too much into mathematical detail, I will point out the benefits which symmetric spaces provide. I will then present some experimental results which originate in my masters thesis. These results show obstacles, which I will then discuss.

Suppose you are given a road network with n traffic signals such that the amount of traffic on each road varies as a linear function of time. Then, the shortest path from a source s to a destination t might be different at different points of time. It was well known (Gusfield, 1980) that the number of different shortest s-t paths is at most \(n^{O(\log n)}\).

In this talk, we will show that there are road networks sans bridges (planar road network) for which the number of different shortest s-t paths is at least \(n^{\Omega(\log n)}\), refuting a conjecture of Nikolova (2009). This is joint work with Jaikumar Radhakrishnan (TIFR). We will also see a variant of this problem, which is part of an ongoing work with Prerona Chatterjee (TIFR) and Girish Varma (IIITH).

Many NP-hard graph problems can be solved in polynomial time if the input instance is a tree. The same holds for input graphs that have small treewidth, a parameter describing how tree-like a graph is. While many graph problems are fixed-parameter tractable when parametrized by treewidth, in most cases this requires the computation of a tree decomposition of the input graph, which is NP-hard as well.

By contrast, an algorithm (PID-BT), submitted to the PACE Challenge 2017 achieved surprisingly fast running times on real-world networks despite the problem's hardness. This points at a big gap between the theoretical understanding of the problem and the practical performance of the algorithm.

In this thesis, we work towards reducing this gap, focussing on hyperbolic random graphs (HRGs) as a realistic model of real-world networks. On the theoretical side, we start by giving an intuitive presentation of the algorithm and show a super-polynomial lower bound on its expected running time on HRGs. This indicates that the observed performance in practice might be due to the implementation's preprocessing. We confirm this via empirical experiments, that show that the employed greedy heuristics discard a large linear part of the graph. We also explain this theoretically, by proving the existence of a linear expected number of simplicial vertices in HRGs.

In this talk, we introduce the multimodal optimization problem EqualBlocksOneMax (EBOM), which has an exponential number of optima (measured in the dimension of the problem). While all optima follow a simple pattern, EAs fail to provide a satisfactory explanation to this pattern, due to the sheer size of the set of optima, and EDAs whose models do not capture dependencies fail to reflect this pattern, due to the low complexity of their model. Consequently, we focus on EDAs with more elaborate models. We show that the arguably easiest EDA that uses dependencies in its model – the mutual-information-maximizing input clustering (MIMIC) – quickly produces a model that behaves empirically almost identically to an ideal model for EBOM. This highlights the benefit of a more complex EDA for a rather simple function when interested in explainability.

In non-uniform hypergraphs there exists a phenomenon unknown to graphs: some edge may be contained in another, with edges even forming chains of inclusions. In many algorithmic applications we are only interested in the collection of inclusion-wise minimal edges, called the minimization of the hypergraph.

In the video we highlight our recent results on the minization of maximum-entropy hypergraphs with a prescribed number of edges and expected edge size. We give tigh bounds on the expected number of minimal edges and briefly touch on the tools used in the proofs. The most important technical contribution is an improvement of the Chernoff-Hoeffding theorem on the tail of the binomial distribution. In particular, we show that for a random variable \(X \sim \mathrm{Bin}(n,p)\) and any \(0 < x < p\), it holds that \(\mathrm{P}[X \le xn] = \Theta( 2^{-\mathrm{D}(x \,{\|}\, p) n}/\sqrt{n})\), where \(\mathrm{D}\) is the Kullback-Leibler divergence from information theory.

This is joined work with Thomas Bläsius and Tobias Friedrich.

Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. In this video, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs.In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.

This is joined work with Johann Birnick, Tobias Friedrich, Felix Naumann, Thorsten Papenbrock, and Martin Schirneck.