For fixed $h \geq 2$, we consider the task of adding to a graph $G$ a set of weighted shortcut edges on the same vertex set, such that the length of a shortest $h$-hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in $G$. A set of shortcut edges with this property is called an \emph{exact $h$-hopset} and may be applied in processing distance queries on graph $G$. In particular, a $2$-hopset directly corresponds to a distributed distance oracle known as a \emph{hub labeling}. In this work, we explore centralized distance oracles based on $3$-hopsets and display their advantages in several practical scenarios. In particular, for graphs of constant highway dimension, and more generally for graphs of constant skeleton dimension, we show that $3$-hopsets require \emph{exponentially} fewer shortcuts per node than any previously described distance oracle, while incurring only a \emph{quadratic} increase in the query decoding time, and also offer a speedup in query time when compared to simple oracles based on a direct application of $2$-hopsets. Finally, we consider the problem of computing minimum-size $h$-hopset (for any $h \geq 2$) for a given graph $G$, showing a polylogarithmic-factor approximation for the case of unique shortest path graphs. When $h=3$, for a given bound on the space used by the distance oracle, we provide a construction of hopset achieving polylog approximation both for space and query time compared to the optimal $3$-hopset oracle given the space bound.

Joint work with Siddharth Gupta and Adrian Kosowski

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. One of the important problems is finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmic size. In this talk, I will present a distance labeling scheme for cube-free median graphs on n nodes with labels of O(log^3 n) bits.

Joint work with Victor Chepoi and Arnaud Labourel

Slides : DistanciaRatel.pdf

The diameter of a non-complete split graph can only be either 2 or 3. Yet, under the Strong Exponential-Time Hypothesis (SETH), we cannot compute the diameter of a split graph in less than quadratic time. Therefore it is worth to study the complexity of diameter computation on subclasses of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded 'clique-interval number', with the latter being a natural variation of the concept of interval number for split graphs that we introduce in this paper. Our main result is that for k = o(log{n}) we can compute the diameter of a k-clique-interval split graph in quasi linear time, whereas for k = omega(log{n}) this cannot be done in subquadratic time under SETH. We further prove that many interesting subclasses such as bounded-treewidth split graphs, threshold graphs and comparability split graphs are k-clique-interval for some bounded k. For some of these subclasses, we propose improved algorithms for diameter computation. Finally, we prove that 1-clique-interval split graphs can be recognized in linear time.

Joint work with G. Ducoffe and L. Viennot

Slides : DistanciaHabib.pdf

We investigate the Minimum Eccentricity Isometric Cycle (MEIC) problem. Given a graph, this problem consists in finding an isometric cycle with smallest possible eccentricity k. We show that this problem is NP-Hard and we propose a 3-approximation algorithm running in O(n(m+kn)) time.

We will discuss three negative curvature parameters of graphs such as hyperbolicity, slimness, and thinness. Recent empirical and theoretical work has suggested that these parameters are very small in many real-world complex networks and graphs, arising in Internet applications, in biological and social sciences, in chemistry and physics. We will discuss algorithmic implications of negative curvature as well as the impact of this intrinsic geometric and topological feature of large-scale networks on their performance, reliability and security. The talk is mostly based on recent works with Chepoi, Habib, Vaxes, Viennot.

Slides : DistanciaDragan.pdf

Using a Helly theorem for quasiconvex sets and a primal-dual approach, we show algorithmically that the minimum number of balls of radius 2ε+5δ intersecting all sets of a family Q of ε-quasiconvex sets of a δ-hyperbolic graph does not exceed the packing number of Q. We extend this covering and packing result to set-families in which each set is a union of ε-quasiconvex sets of a δ-hyperbolic graph G.

Joint work with Victor Chepoi and Feodor Dragan

Slides : DistanciaVaxes.pdf

We will present counterexamples to Thaigarajan's conjectures that (1) regular event structures are trace regular (alias, unfoldings of finite 1-safe Petri nets) and (2) that the MSO logic of a trace regular event structure is decidable iff it is grid-free. Among many other things, one of the main ingredients in our results is the striking bijection between three objects occurring completely different domains: the domains of event structures (the basic abstract model of concurrent computation), median graphs (one of the most important classes of graphs in metric graph theory), and CAT(0) cube complexes (central objects in geometric group theory).

We will also present positive results. In particular, we will show that Conjecture 1 of Thiagarajan holds for regular event structures whose domains are principal filters of universal covers of virtually special NPC complexes. We also establish a correspondence between finite 1-safe Petri nets (alias trace regular event structures) and finite special NPC complexes.

Content:
1. Event structures and 1-safe Petri nets
2. Bijections
->2.1. Domains of event structures, (directed) median graphs, and CAT(0) cube complexes
->2.2. NPC complexes and coverings
3. Thiagarajan's conjectures
->3.1. Conjecture 1: each regular event structure is trace regular (unfolding of a finite 1-safe Petri net)
->3.2. Conjecture 2: the MSO logic of a trace regular event structure is decidable iff it is grid-free
4. Counterexample to Conjecture 1. The special and hyperbolic cases.
5. Correspondence between finite 1-safe Petri nets and special NPC complexes.
6. Decidability of the MSO theories, bounded treewidth, and context-free property
7. Counterexample to Conjecture 2.

Slides : DistanciaChalopin.pdf

The complexity of finding a largest clique in a disk intersection graph is a notorious open question in computational geometry. A polynomial algorithm is known since 1990 for unit disks, and a 2-approximation for general disks is immediate from a structural result known since the fifties. For unit ball (i.e., in a 3-dimensional space) graph, there is a 2.553-approximation due to Ashfani and Chan, and the problem is also not known to be NP-hard. We prove the first EPTAS (Polynomial Time Approximation Scheme in time f(eps)nO(1)) for computing Max Clique on those two classes. One key ingredient is that (for non apparent common reason) both these classes share a common forbidden induced subgraph : they don’t contain the disjoint union of two odd cycles as an induced subgraph in their complement. It was proven by [Bonnet, Giannopoulos, Kim, Rzazewski, Sikora; SoCG ’18] for disk graphs and we proved it for unit ball graphs. In sharp contrast, we prove that Max Clique is APX-hard (i.e., unlikely to admit a PTAS) and ETH-hard (i.e., unlikely to admit a subexponential algorithm) in ball graphs, unit 4-dimensional graphs, and intersection graphs of ellipses with arbitrary low eccentricity.

This is joint work with Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, and Stéphan Thomassé.

Slides : DistanciaCharbit.pdf