# AGaPe

https://www.irif.fr/~vmitsou/agape-dec22.html

After a long pause due to the COVID pandemic, the working group AGaPe (Algorithms with Performance Guarantees) finally resumes its meetings. The next installement of AGaPe will take place on **December 12th from 2pm to 6pm at the IRIF laboratory**. Topics include (but are not limited to):

- exact and parameterized resolution
- approximation (polynomial, moderately exponential, subexponential and parameterized)
- algorithms on evolving instances (online, temporal graphs, ...)
- combinatoral optimization
- algorithmic games

### Registration

Please use this link to register for the event.

### Information

All talks will take place in room 3052 (3rd floor of the IRIF laboratory). You need a badge in order to use the elevators; you can ask for one at the information desk in the ground floor (you need an ID). If you use the stairs you don't need a badge to enter the lab.

A light lunch will be served before the start of the workshop at 1pm.

### Program

Click on the link in order to read the title and abstract.

1:00-2:00 Lunch

2:00-2:45 Laurent Feuilloley

2:45-3:10 Niklas Hahn

3:10-3:55 Laurent Viennot

3:55-4:25 Coffee break

4:25-5:10 Stéphan Thomassé

5:10-4:35 Daniel Vaz

5:35-6:00 Mónika Csikós

**Confirmed speakers:**

### Titles and Abstracts

**Monika Csikós:** *An improved algorithm to create matchings with low crossing numbers.* Given a hypergraph H = (V, E), we consider the problem is to find a perfect matching of V such that each hyper-edge in E crosses few edges of the matching. This structure was originally introduced for geometric range searching in the 1980s and since then, it has found applications in various fields, including algorithmic graph theory and combinatorial data approximation.

The seminal work of Chazelle and Welzl provided an algorithm that for any hypergraph with n vertices, m edges, and dual VC-dimension d, constructs a matching with crossing number O(n^{1−1/d}) in time O(n^{3}m). Since then, despite several advances for geometric hypergraphs, the general algorithm for abstract hypergraphs remained unimproved.

We propose a new sampling-based algorithm which is applicable to any finite hypergraph with dual VC-dimension d and provides a matching with expected crossing number O(n^{1−1/d}) in time O(n^{1/d}m + n^{2+1/d}) resulting in an n^{2−1/d} factor speedup on the construction time (assuming m ≥ n). Joint work with Nabil H. Mustafa.

**Laurent Feuilloley:** *The Secretary Problem with Independent Sampling.* The secretary problem is a classic online decision problem. In this problem, an adversary first chooses some n numbers, then these numbers are shuffled at random and presented to the player one by one. For each number, the player has two options: discard the number and continue, or keep the number and stop the game. The player wins if she kept the highest number of the whole set. It is clearly not possible to win all the time: when one decides to stop there might be a higher number in the rest of the sequence, and when one discards a number, it might actually be the highest of the sequence. But surprisingly one can win with probability 1/e.

An issue with the secretary problem is that it assumes that the player has absolutely no information about the numbers, which reduces its applicability. A recent research direction is to understand what happens when one knows a distribution or samples etc. We study a simple such setting for which we prove tight results. Interestingly, some of the lower bound techniques we use are inspired by ideas from distributed graph algorithms.

Based on: The Secretary Problem with Independent Sampling (SODA 2021). Joint work with José Correa, Andrés Cristi, Tim Oosterwijk, and Alexandros Tsigonias-Dimitriadis. Arxiv.

**Niklas Hahn:** *Online TSP with Known Locations.* In this talk, we will revisit the classic traveling salesperson problem (TSP) in an online model with unknown release times but known locations of the requests. We will present an algorithm that leverages this additional information to achieve an optimal competitive ratio of 3/2. This bounds holds for both the closed as well as the open variant of TSP, and we will see matching lower bounds. Further, we consider different metric spaces, and discuss competitive poly-time algorithms as well as lower bounds for these.

**Stéphan Thomassé:** *Combinatorial optimization under bounded twin-width* While twin-width is easily defined on graphs via contraction sequences, a deeper insight is obtained if we consider the following measure of complexity of a matrix:

- A matrix M has a "rank k grid" if we can partition M into kxk blocks each of them having rank at least k
- The grid rank of a matrix M, gr(M), is the maximum k for which a rank k grid exists in M

We have shown in TWW4 that a graph has bounded twin-width if and only if it has an adjacency matrix with bounded grid rank. The (big!) subtelty is that G has bounded twin-width iff we can order its vertices in such a way that the adjacency matrix has bounded grid rank. The two notions are therefore equivalent in theory, but in practice, we have no efficient algorithm to find such an order.In what follows, we assume that matrices are given with an order achieving bounded grid rank.

A very natural question is then: whenever a structural/algorithmic question involves matrices, can we do it better/faster when assuming that the matrices have bounded grid-rank.

On these lines, we showed in TWW5 that matrix multiplication in finite fields of two nxn matrices can be done in time O(n), when the decomposition is known. Another natural area to investigate is combinatorial optimization: What about linear programs involving a bounded twin-width matrix? which amount to the exciting (and virtually non investigated) question: What is a bounded twin-width polyhedron?

One of the first case to consider is: Minimize 1.x Subject to Ax<=1, x>=0 when A is the adjacency matrix of a graph G. This is the fractional relaxation of the minimum dominating set (if we assume a_ii=1), and its dual is the fractional relaxation of the maximum size of a distance 2 independent set (vertices have pairwise distance at least 3).

We have shown in TWW3 that we can bridge the duality gap:

Th: If G has twin width t, there is a constant c_t such that minimum dominating set<= c_t.(maximum 2-independent set)

This linear duality gap also holds when A is a 01-matrix with bounded grid-rank.

I will overview in this talk the material needed to fully cover these results

The two very natural questions "What if A is a real matrix?" and "What if A has an ordering with bounded grid rank, but we do not know it?" are work-in-progress and hopefully subject to future expositions...

Joint work with: É. Bonnet, C. Geniet, U. Giocanti, E.J. Kim, P. Ossona de Mendez, P. Simon, S. Toruńczyk, R. Watrigant

**Daniel Vaz:** *Vertex Sparsification for Edge Connectivity.* Graph compression or sparsification is a fundamental question in information theory and computer science. Given a graph with a special set of vertices called terminals, we ask if it is possible to find a smaller graph, named sparsifier, which preserves some property of the graph with respect to the terminals. A major open problem in this area is to find small sparsifiers which preserve cuts between sets of terminals, that is, sparsifiers in which the minimum cut separating any two sets of terminals is the same as in the original graph.

In this talk, we look at sparsifiers for the closely related setting of c-connectivity. For a fixed value of c, a c-connectivity sparsifier preserves the number of edge-disjoint paths between any two sets of terminals, unless the number of such paths is at least c in both the original graph and the sparsifier. We show that c-connectivity sparsifiers with O(kc^4) edges exist, where k is the number of terminals, and describe two algorithms for this problem: the first algorithm finds a sparsifier with O(kc^4) edges in time O(m(c \log n)^O(c)), while the second finds a slightly worse sparsifier with k O(c)^2c edges, in time O(m c^O(c) log^O(1) n).

Our results lead to new data structures for dynamic c-connectivity problems, as well as more efficient algorithms for network design problems.

**Laurent Viennot:** *Walk temporalisation*. In a temporal graph, each edge appears and can be traversed at specific points in time. In such a graph, temporal reachability of one node from another is naturally captured by the existence of a temporal path where edges appear in chronological order. Inspired by the optimisation of bus/metro/tramway schedules in a public transport network, we consider the problem of turning a collection of walks (called trips) in a directed graph into a temporal graph by assigning a starting time to each trip so as to maximise the reachability among pairs of nodes. Each trip represents the trajectory of a vehicle and its edges must be scheduled one right after another. Setting a starting time to the trip thus forces the appearing time of all its edges. We call such a starting time assignment a trip temporalisation.

We obtain several results about the complexity of maximising reachability via trip temporalisation. Among them, we show that maximising reachability via trip temporalisation is hard to approximate within a factor $\sqrt{n}/12$ in an $n$-vertex digraph, even if we assume that for each pair of nodes, there exists a trip temporalisation connecting them. On the positive side, we show that there must exist a trip temporalisation connecting a constant fraction of all pairs if we additionally assume symmetry, that is, when the collection of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order.

### Organizing Committee

Evripidis Bampis, LIP6, Sorbonne Université (Evripidis.Bampis@lip6.fr)

Valia Mitsou, IRIF, Univesité Paris Cité (vmitsou@irif.fr)

Alantha Newman, G-SCOP, Université Grenoble Alpes (alantha.newman@grenoble-inp.fr)