==== AGaPe mini-workshop ==== // 10 December 2024, IRIF, Paris // The next event of [[http://gdrro.lip6.fr/?q=node/55|AGaPe]] (Algorithms with Performance Guarantees) will take place on December 10th 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 == Registration is free but mandatory and is done at the following [[https://framaforms.org/agape-2024-1730997749|link]]. The registration deadline is **November 28th**. == Confirmed Speakers == * [[https://webia.lip6.fr/~bellitto/|Thomas Bellito]] (LIP6, Sorbonne Université) * [[https://perso.isima.fr/~piberge/|Pierre Bergé]] (LIMOS, Université Clermont Auvergne) * Caroline Brosse (LIFO, Université d'Orléans) * [[https://sites.google.com/view/hoang-la|Hoang La]] (LISN, Université Paris-Saclay) * [[http://people.eecs.berkeley.edu/~orrp/|Orr Paradise]] (UC Berkeley) - in coordination with [[https://www.irif.fr/en/seminaires/algocomp/index|IRIF's Algorithms and Complexity group seminar]] * [[https://www.normalesup.org/~saulpic/|David Saulpic]] (IRIF) == Program == * 10h20-11h: David Saulpic: //Making Old Things New: A Unified Algorithm for Differentially Private Clustering// \\ As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithms: the landscape of private clustering algorithms is therefore quite intricate. With Max Dupré la Tour and Monika Henzinger, we showed that a 20-year-old greedy algorithm can be slightly modified to work for any of these models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them and extend it to some recent privacy models. * 11h-12h: Orr Paradise: //Models that prove their own correctness// \\ This talk introduces Self-Proving models, a new class of models that formally prove the correctness of their outputs via an Interactive Proof system. After reviewing some related literature, I will formally define Self-Proving models and their per-input (worst-case) guarantees. I will then present algorithms for learning these models and explain how the complexity of the proof system affects the complexity of the learning algorithms. Finally, I will show experiments where Self-Proving models are trained to compute the Greatest Common Divisor of two integers, and to prove the correctness of their results to a simple verifier. 12h-13h30: Lunch * 13h30 - 14h10 Pierre Bergé: //Computing the diameter efficiently : the case of median graphs// \\ A longstanding and challenging question in algorithmics is the computation of distances in graphs, in particular of the diameter and all eccentricities. A first approach for tackling these problems consists in launching a BFS from each vertex of the input graph: this allows to retrieve all distances in time O(mn), where n (resp. m) is the number of vertices (resp. edges). Unless SETH fails, on sparse graphs, the diameter cannot be approximated within a factor of 3/2 in subquadratic time, which makes multiple BFS a straightforward but efficient method in general. During the last decade, many subquadratic-time algorithms were proposed for the computation of diameter/eccentricities on well-known families of sparse graphs, for example on bounded-treewidth graphs (Abboud et al., 2016) but also on planar (Cabello, 2018). Certain of these results even highlight exact algorithms running in quasilinear time, i.e. linear time if we neglect poly-logarithmic factors. We present our exact quasilinear-time algorithm dedicated to median graphs for these problems. Median graphs arise in phylogenetics (representation of mitochondrial DNA), geometric group theory (1-skeletons of CAT(0) cube complexes) and logic (model for solutions of 2-SAT). * 14h10 - 14h50 Caroline Brosse //Output-sensitive enumeration in polynomial space: the case of Potential Maximal Cliques // \\ A set of vertices in a graph forms a potential maximal clique if there exists a minimal chordal completion in which it is a maximal clique. Potential maximal cliques were first introduced as a key tool to obtain an efficient, though exponential-time algorithm to compute the treewidth of a graph. As a byproduct, this allowed to compute the treewidth of various graph classes in polynomial time. In recent years, the concept of potential maximal cliques regained interest as it proved to be useful for a handful of graph algorithmic problems. In particular, it turned out to be a key tool to obtain a polynomial time algorithm for computing maximum weight independent sets in P5-free and P6-free graphs (Lokshtanov et al., SODA'14 and Grzeskik et al., SODA'19). In most of their applications, obtaining all the potential maximal cliques constitutes an algorithmic bottleneck, thus motivating the question of how to efficiently enumerate all the potential maximal cliques in a graph G. The state-of-the-art algorithm by Bouchitté & Todinca can enumerate potential maximal cliques in output-polynomial time by using exponential space, a significant limitation for the size of feasible instances. We revisit this algorithm and design an enumeration algorithm that preserves an output-polynomial time complexity while only requiring polynomial space. 14h50 - 15h30 Coffee * 15h30 - 16h10 Thomas Bellitto: //Canadian Traveller Problems in Temporal Graphs// \\ In the Canadian Traveller Problem, a traveller wants to travel from a vertex s to a vertex t in a graph where up to k edges can be blocked. However, the traveller only finds out whether an edge is blocked when he reaches one of the edge's endpoints. The aim is to find a robust strategy that guarantees the best possible upper bound on the length of the travel. Together with Johanne Cohen, Bruno Escoffier, Minh Hang Nguyen and Mikael Rabie, we studied this problem in temporal graphs. A temporal graph is a graph where each edge is only present at certain given times, such as a train network for example. This leads to several variants, such as latest departure path, earliest arrival path or shortest duration path, but also variants depending on when the traveler learns whether an edge is blocked. In what we call the locally-informed variant, the traveller learns if an edge is blocked as soon as he reaches one of its endpoints, while in the uninformed variant, they have to wait until the edge is supposed to appear. We provided a polynomial algorithm for each shortest path variant in the uninformed case. This algorithm also solves the case of directed acyclic non-temporal graphs. In the locally-informed case, we proved that finding a winning strategy is PSPACE-complete. Moreover, we established that the problem is polynomial-time solvable when k=1 but NP-hard for k≥2. Additionally, we showed that the standard (non-temporal) Canadian Traveller Problem is NP-hard when there are k≥4 blocked edges, which is, to the best of our knowledge, the first hardness result for CTP for a constant number of blocked edges. * 16h10 - 16h50 Hoang La: //Uniform domination in graphs: a probabilistic approach to deterministic coloring// \\ The problem of finding the size of a minimum dominating set in a graph is well-known to be NP-complete. Intuitively, graphs with smaller minimum degree require larger dominating sets. In this talk, we investigates the extremal size of a minimum dominating set in the class of graphs of minimum degree d. Using a probabilistic approach, we design a polynomial-time algorithm that constructs a random dominating set D, where each vertex belongs to D with probability r. This guarantees the existence of a dominating set whose size is at most r times the number of vertices of the graph. We establish an asymptotically tight bound on r of order (log d)/d and for d=2, we prove a tight bound of r=2/5 with the specific exception of 8 specific graphs. Our result is equivalent to the existence of a vertex coloring of the graph with p colors, where each vertex is assigned at most q colors, each color class forms a dominating set, and the ratio q/p is at most r. This strengthens prior results by demonstrating not only the existence of a small dominating set but also a structured coloring of the whole graph. In this sense, our result for d=2 is optimal and improves upon four previous results. Furthermore, our probabilistic algorithm can be derandomized to produce a deterministic coloring. == Organizing Committee == * Evripidis Bampis, LIP6, Sorbonne Université * Monika Csikos, IRIF, Univesité Paris Cité * Valia Mitsou, IRIF, Univesité Paris Cité * Alantha Newman, G-SCOP, Université Grenoble Alpes * Michele Orrù, IRIF