Chromatic Correlation Clustering (CCC) models clustering of objects with categorical pairwise relationships. The model can be viewed as clustering the vertices of a graph with edge-labels (colors). Bonchi et al. [KDD 2012] introduced it as a natural generalization of the well studied problem Correlation Clustering (CC), also known as Cluster Editing.

Our main theoretical contribution is an alternative analysis of the famous Pivot algorithm for CC. We show that, when simply run color-blind, Pivot is also a linear time 3-approximation for CCC. The previous best theoretical results for CCC were a 4-approximation with a high-degree polynomial runtime and a linear time 11-approximation, both by Anava et al. [WWW 2015].

While this theoretical result justifies Pivot as a baseline comparison for other heuristics, its blunt color-blindness performs poorly in practice. We develop a color-sensitive, practical heuristic we call Greedy Expansion that empirically outperforms all heuristics proposed for CCC so far, both on real-world and synthetic instances.

Further, we propose a novel generalization of CCC allowing for multi-labelled edges. We argue that it is more suitable for many of the real-world applications and show that running the color blind algorithm does still result in a 3-approximation.

We consider two types of controlled random walks on graphs. In the choice random walk, the controller chooses between two random neighbours at each step; in the epsilon-biased random walk the controller instead has a small probability at each step of a free choice of neighbour. We consider the problem of finding optimal strategies for the controller minimising the expected time to hit a given vertex or visit (cover) all vertices.

Using a general framework for boosting the probabilities of rare events, we show a significant speed-up over the simple random walk for graphs with good expansion properties. We also establish a complexity dichotomy for making optimal choices, which are tractable for hitting times but NP-hard for cover times on undirected graphs (PSPACE-complete for directed graphs). We shall also discuss some recent new results.

This is joint work with Agelos Georgakopoulos, John Haslegrave, Sam Olesker-Taylor and Thomas Sauerwald.

There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan (2019), and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh (2017). To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain constant-factor pseudo-approximations. In this work, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful k-Center with constantly many colors---settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan---and a 4-approximation for Fair Robust k-Center, for which the existence of a (true) constant-factor approximation was also open. We complement our results by showing that if one allows an unbounded number of colors, then Colorful k-Center admits no approximation algorithm with finite approximation guarantee, assuming that P is not equal to NP. Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set.

This is joint work with Georg Anegg, Adam Kurpisz, and Rico Zenklusen.

The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in d dimensions. The runtime of our algorithm is polynomial in the volume of the system for the entire known real-valued regime for the uniqueness of the Gibbs measure.

Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.

In this talk, I will share the new trends in the storage/memory field, focusing on Persistent Memory. We will overview the storage stack and the gap between volatile Memory (DRAM) and persistent storage (SSD). After more than a decade of research, in 2015 Intel closed this gap by announcing a new persistent memory media called 3D Xpoint. This media is closing the gap by being persistent like SSD, fast almost like DRAM, and costs slightly less than DRAM. The first commercial product called Optane DC was out in 2019. In this talk, we will deep dive into the challenges of adopting this technology and explore the research opportunities in this area.

Force-directed drawing algorithms are the most commonly used approach to visualize networks. While they are usually very robust, the performance of Euclidean spring embedders decreases if the graph exhibits the high level of heterogeneity that typically occurs in scale-free real-world networks. As heterogeneity naturally emerges from hyperbolic geometry (in fact, scale-free networks are often perceived to have an underlying hyperbolic geometry), it is natural to embed them into the hyperbolic plane instead. Previous techniques that produce hyperbolic embeddings usually make assumptions about the given network, which (if not met) impairs the quality of the embedding. It is still an open problem to adapt force-directed embedding algorithms to make use of the heterogeneity of the hyperbolic plane, while also preserving their robustness. We identify fundamental differences between the behavior of spring embedders in Euclidean and hyperbolic space, and adapt the technique to take advantage of the heterogeneity of the hyperbolic plane.

The contact process models the spread of an infection in a network. If the infection rate is high enough, the infection can survive exponentially long in the size of the network. This effect even occurs on simple sub structures such as big stars, that can be found in many real world networks. We analyze thresholds for the infection rate above which the infection becomes epidemic on these structures.

Fault tolerant algorithms reflect the error-proneness of many real-world systems. If the system is modelled as a graph, errors might represent failing edges or vertices, depending on the problem. We usually assume that only up to \(k\in\mathbb N\) vertices/edges will fail at the same time. Given \(k\), the task is to preprocess the original graph into a data structure that efficiently answers queries that include a set \(F, |F|\le k\) of failing vertices/edges.

For the Fault Tolerant Reachability problem, we are given a directed graph \(G=(V,E), s\in V\) and \(k\in\mathbb N\). The computed data structure has to answer given \(F\subseteq E, v\in V\), whether \(v\) is reachable from \(s\) in \(G-F\). The presented algorithm uses a useful graph structure called important separators to build a subgraph of \(G\), which is then used to answer the queries.

Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and destination and aims at finding up to n different routes that the drivers strategically disperse over, minimizing the overall travel time of the system.

Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case n=2, we compare our MREA to the highly tailored optimal solver by Bläsius et al. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least 99.69% of an optimal solution while only requiring 40% of the time.

An \(f\)-edge fault-tolerant diameter oracle (\(f\)-FDO) preprocesses a given graph \(G\) and, when queried with a set \(F\) of at most \(f\) edges, returns the approximate diameter of the graph \(G - F\). Such data structures need to strike a balance between the time they take for preprocessing and answering queries, the occupied space, and the stretch of the approximation.

For the single-failure case (\(f = 1\)) on directed \(n\)-vertex, \(m\)-edge graphs with diameter \(D\), Henzinger et al. [ITCS 2017] presented an \((1+\varepsilon)\)-approximate 1-FDO with \(\widetilde{O}(mn + n^{1.5} \sqrt{Dm/\varepsilon})\) preprocessing time, constant query time, and \(O(m)\) space. They also showed that any combinatorial 1-FDO requires \(n^{3-o(1)}\) preprocessing time, unless the Boolean Matrix Multiplication conjecture fails. We improve the preprocessing to \(\widetilde{O}(mn + n^2/\varepsilon)\) keeping the same stretch, query time, and space. When using fast matrix multiplication, this reduces to \(\widetilde{O}(n^{2.5794} + n^2/\varepsilon)\), breaking the cubic barrier. We further give an unconditional space lower bound, showing that any 1-FDO with stretch better than \(3/2\) requires \(\Omega(m)\) bits of space.

For multiple failures (\(f > 1\)) on undirected graphs, we present an \((f+2)\)-approximate \(f\)-FDO, with preprocessing time \(\widetilde{O}(fm)\), query time \(\widetilde{O}(f^2)\), taking \(\widetilde{O}(fn)\) space. This refines an analysis by Bilò et al. [STACS 2016]. We also show that the space requirement is tight up to polylogarithmic factors, provided that the oracle can also be queried with non-edges. Finally, we discuss how we can swap the need of approximation for a slightly larger query time in networks with a polylogarithmic diameter.

This is joint work with Davide Bilò, Sarel Cohen, and Tobias Friedrich.

Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between theory and practice when it comes to understanding this tradeoff. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of √2. On the other hand, a simple greedy algorithm yields close to optimal approximations in practice.

A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we close the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a (1 + o(1))-approximation, asymptotically almost surely, and has a running time of O(m log(n)).

The proposed algorithm is an adaption of the successful greedy approach, enhanced with a procedure that improves on parts of the graph where greedy is not optimal. This makes it possible to introduce a parameter that can be used to tune the tradeoff between approximation performance and running time. Our empirical evaluation on real-world networks shows that this allows for improving over the near-optimal results of the greedy approach.

An additive +β spanner of a graph G is a subgraph which preserves all distances in G up to an additive +β error. Additive spanners are well-studied in unweighted graphs but have only recently received attention in weighted graphs [Elkin et al. 2019 and 2020, Ahmed et al. 2020]. In this talk, we discuss algorithms which construct sparse additive spanners with error +cW(.,.), where W(u,v) is the maximum edge weight of a shortest u-v path in G. These include a pairwise +(6+ε)W(.,.) spanner over G and vertex pairs P on \(O_ε(n|P|^{1/4})\) edges and a pairwise +(2+ε)W(.,.) spanner on \(O_ε(n|P|^{1/3})\) edges, nearly matching the unweighted case.

Besides sparsity, another common way to measure the quality of a spanner in weighted graphs is by its lightness, defined as the total edge weight of the spanner divided by the weight of an MST of G. We provide the first known lightness results for additive spanners: an all-pairs +εW(.,.) spanner with \(O_ε(n)\) lightness, and a +(4+ε) W(.,.) spanner with \(O_ε(n^{2/3})\) lightness. All of the above spanners can be constructed in polynomial time.

A single-source distance sensitivity oracle (single-source DSO) preprocesses a given graph \(G\) with a distinguished source vertex \(s\) into a data structure. When queried with a target vertex \(t\) and an edge \(e\), the structure reports the replacement distance \(d_{G-e}(s,t)\) in case \(e\) fails. In the closely related single-source replacement paths (SSRP) problem, we are given \(G\) and \(s\) and have to enumerate all distances \(d_{G-e}(s,t)\).

We present deterministic single-source DSOs for undirected graphs with \(\widetilde{O}(1)\) query time. For unweighted graphs, we give a combinatorial preprocessing algorithm running in time \(\widetilde{O}(m \sqrt{n} + n^2)\), resulting in a data structure taking \(O(n^{3/2})\) space. For graphs with integer edge weights in the range \([1,M]\) and when using fast matrix multiplication, we get a preprocessing time of \(\widetilde{O}(Mn^{\omega})\), and the oracle takes \(O(M^{1/2}n^{3/2})\) space. Here, \(\omega < 2.373\) denotes the matrix multiplication exponent. Both preprocessing times improve over previous constructions by polynomial factors. We further show that the space requirement is optimal up to the size of a machine word. Finally, we give a randomized preprocessing algorithm that breaks the quadratic barrier on sufficiently sparse graphs.

We obtain our oracles by derandomizing known SSRP algorithms by Chechik & Cohen [SODA'19] as well as Grandoni & Vassilevska Williams [FOCS'12] and combining them with a novel compression scheme for replacement distances.

This is joint work with Davide Bilò, Sarel Cohen, and Tobias Friedrich.

Routing is a method of sending messages in a network by successively forwarding them to a neighbor until they reach the target. This is done by assigning to every vertex a coordinate that stores some structural information. Most routing schemes show a trade-off between length of routed paths and memory required per coordinate. In this talk, we present a routing scheme such that in the worst case, every path it chooses is only five times longer than the shortest path. Further, we prove that in a hyperbolic random graph \(G\), the coordinates of our routing scheme are encoded using \(O(log^3 n·diam(n))\) bits. These graphs are of special interest as they are assumed to be a model which approximates real-world graphs. Our findings greatly improve upon the previous best known results for hyperbolic random graphs, which guarantee on average short paths only asymptotically almost surely and make no statements about coordinate size.

We evaluate our routing scheme on multiple generated and real-world networks. Our experiments show, that the coordinates in these networks all require little memory, while most paths used for routing match the shortest paths in length. In networks that are assumed to have an underlying hyperbolic geometry, for example the Internet graph, the resulting paths of our scheme are on average only 5% longer than the shortest paths.

The formal study of coalition formation in multiagent systems is typically realized using so-called hedonic games, which originate from economic theory. The main focus of this branch of research has been on the existence and the computational complexity of deciding the existence of coalition structures that satisfy various stability criteria. The actual process of forming coalitions based on individual behavior has received considerably less attention. In this talk, we study the convergence of simple dynamics based on single-agent deviations in hedonic games. We consider various strategies for proving convergence of the dynamics based on potential functions. In particular, we showcase methods for dealing with non-monotonic potential functions. On the other hand, it is a challenging task to pinpoint the boundary of tractability of stable states. We show how to construct complicated counterexamples with the aid of linear programs. These counterexamples can usually be used to prove computational intractabilities.