~~NOCACHE~~ /* DO NOT EDIT THIS FILE */ [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Friday December 8, 2023, 3PM, 1007\\ **Pierre Aboulker** (ENS-Paris) //Clique number of tournaments// \\ the dichromatic number of a digraph is the minimum integer k such that the set of vertices of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is the same as the dichromatic of the digraph obtained from G by replacing each edge by a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerned with chromatic number of undirected graphs have been generalised to digraphs via the dichromatic number. However, no concept of clique number for digraphs was available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and chromatic number in undirected graphs. We will focus on studying the notion of chi-boundedness in particular. This is a joint work with Guillaume Aubian, Pierre Charbit and Raul Lopes. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Friday November 10, 2023, 3PM, 1007\\ **Pournajafi Pegah** (College de France) //Scott's conjecture for complete graphs// \\ The connection between excluding complete graphs (for different notions of exclusion) and the chromatic number of graphs is about a century old. In the 1940s, Hadwiger conjectured that a graph with no Kn minor is (n-1)-colorable. Later, in the 1950s, Hajós made a strengthening this conjecture, that every graph that contains no subdivision of Kn as a subgraph, is (n-1)-colorable. While both conjectures still have open cases, the existence of a bound c=c(n) instead of n-1 for the chromatic number is known for both conjectures. An attempt to strengthen this result would be to ask whether there exists a constant c=c(n) such that every graph with no subdivision of Kn as an induced subgraph is c-colorable. This question is a special case of Scott's conjecture from the 1990s. The only known cases of Scott's conjecture for complete graphs Kn was for n at most 4, where a constant bound exists (a result by Lévêque, Maffray, and Trotignon). With Nicolas Trotignon, we proved that no such bound exists for n at least 5. In this talk, I present the techniques used to prove this result as well as some other applications of the technique in chi-boundedness. This result is from arXiv:2112.11970. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Friday October 20, 2023, 3PM, 1007\\ **Allen Ibiapina** //Menger's Theorem and Related Problems in Temporal Graph// \\ Temporal graphs model time-varying relationships in dynamic systems. Key problems include paths and connectivity. In static graphs Menger's Theorem states the maximum number of internally disjoint paths between non-adjacent vertices equals the minimum vertices needed to cut all paths. This combined with flow techniques also leads to polynomial time algorithms to compute disjoint paths and cuts. A natural question is therefore whether such results carry over to temporal graphs, where the paths/walks between a pair of vertices must respect the flow of time. The first obstacle in such question is the definition of robustness in this context, i.e., how are the paths/walks to be disjoint. We discuss three possible types of robustness, each of which leading to the definition of two optimization parameters, one concerning the maximum number of disjoint paths, and the other the minimum size of a cut. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday September 26, 2023, 3:30PM, 3052 Sophie Germain\\ **Binh-Minh Bui-Xuan** (CNRS, LIP6, UPMC) //Efficient algorithms using temporality and geometry on graphs.// \\ In graph theory, a dynamic network can be understood as a global underlying graph whose edges are allowed to become temporarily unavailable at times. Extending Courcelle-like meta theorems to such a temporal setting is an important and challenging open question. Without the consideration of temporality, a good number of width parameters has been introduced in the effort to better understand what lies between cliquewidth (number of different neighbourhoods) and treewidth (total size of neighbourhoods). We can cite rankwidth, bimodule-width, booleanwidth, and matching-width for the first category; and minor-based parameters such as Hajos/Hadwiger number and twinwidth for the second one. However, attempts in extending those parameters to temporal graphs are still scarce in the literature. Twins in a temporal context would refer to vertices which are substitutes for each other in the solution of a number of classical graph problems, e.g. matching, epidemic spreading, journeys of optimal (temporal) length, and so on. Although most of these problems become NP-hard to optimise on an arbitrary input, we present in this talk an example where reducing a spatiotemporal input into a timeless graph and using both geometric and decomposition properties help in obtaining a PTAS solution. We hope this kind of technique could help in solving problems beyond first order logic when exploiting the conformist nature of twins. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday September 19, 2023, 4PM, 3052\\ **Feodor Dragan And Guillaume Ducoffe** //alpha_i-Metric Graphs: Radius, Diameter and all Eccentricities// \\ We extend known properties of chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called alpha_i-metric (i in N) if it satisfies the following alpha_i-metric property for every vertices u,w,v and x: if a shortest path between u and w and a shortest path between x and v share the terminal edge vw, then d(u,x) >= d(u,v) + d(v,x)-i. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a ,,near-shortest'' path with defect at most i. It is known that alpha_0-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are alpha_i-metric for i=1 and i=2, respectively. We show that an additive O(i)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an alpha_i-metric graph can be computed in total linear time. Our strongest results are obtained for alpha_1-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called (alpha_1,Delta)-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers to a question raised in (Dragan, IPL, 2020). Our algorithms follow from new results on centers and metric intervals of alpha_i-metric graphs. In particular, we prove that the diameter of the center is at most 3i+2 (at most 3, if i=1). The latter partly answers to a question raised in (Yushmanov & Chepoi, Mathematical Problems in Cybernetics, 1991). [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday September 12, 2023, 3PM, 147 Olympe de Gouges\\ **Éric Colin De Verdière** (CNRS, LIGM, Marne-la-Vallée) //Embedding graphs into 2-dimensional simplicial complexes// \\ The graph planarity testing problem asks whether we can draw an input graph in the plane in such a way that it is actually crossing-free (or embedded). In a seminal paper from 1974, Hopcroft and Tarjan gave a linear-time algorithm for this problem, initiating a long series of variations and generalizations. One of them is to make the target space more general, namely, to consider embeddings not into the plane, but into a more general surface. It is known that the problem of deciding the embeddability of a graph into a surface is NP-hard, but Mohar (1999) and Kawarabayashi, Mohar, and Reed (2008) gave algorithms that are linear in the size of the graph (and exponential in the genus of the surface). In this talk, we consider an even more general case, in which the target space is a 2-dimensional simplicial complex (a topological space obtained from a graph by attaching a solid triangle to some of its 3-cycles). It turns out that this generalization encompasses some other well known problems, such as the crossing number problem and the planarity number problem (and their generalizations to surfaces). We give an algorithm that is quadratic in the size of the input graph (and exponential in the size of the input complex), independent from the previous algorithms to embed graphs into surfaces. The techniques mix graph theory (branchwidth, excluded grid theorem, dynamic programming) with topology (combinatorial maps of graphs on surfaces). This is joint work with Thomas Magnard. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday July 11, 2023, 3PM, 146 Olympe de Gouge\\ **Andrea Jimenez** (University of Valparaiso, Chile) //UPPER BOUND FOR THE CONFLICT-FREE CHROMATIC NUMBER ON CLAW-FREE GRAPHS// \\ A proper vertex coloring of a graph is said to be odd if for each non-isolated vertex there is a color appearing an odd number of times among its neighbors. It is said to be conflict-free if for each non-isolated vertex there is a color appearing exactly once among its neighbors. In [Caro et al., Remarks on proper conflict-free coloring of graphs, Discrete Mathematics 346 (2023) 113221] it was proved that any claw-free graph with maximum degree k has a conflict-free coloring with at most 2k +1 colors. In this talk we show that this upper bound can be improved to k + 6, and to k + 4, for quasi-line graphs, a proper subclass of claw-free graphs. Our result relies on a recoloring technique which could be useful to derive similar results for other families of graphs and for odd colorings as well. Joint work with: Martin Matamala (Universidad de Chile). [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday June 13, 2023, 3PM, 147 Olympe de Gouges\\ **Anna Gujgiczer** (Budapest University of Technology and Economics, Hungary) //Circular chromatic number of generalised Mycielski graphs on odd cycles and other quadrangulations of the projective plane// \\ Generalised Mycielskians of odd cycles are relatively small graphs with high odd girth and chromatic number 4. In the literature there are many proofs using different techniques, like methods from algebraic topology, to show the second property. It is also proven by DeVos et al that these graphs have circular chromatic number 4. Using a result from about the same time of Simonyi and Tardos, namely that for a "topologically t-chromatic" graph $G$, where $t$ is even we have $\chi_c(G) = \chi(G) = t$, one can also get this strengthened statement. In this talk we present a new, relatively short direct proof for the circular chromatic number, using only a basic notion of algebraic topology, namely the winding number. Then we present another graph family with high odd girth and circular chromatic number 4. This construction is very similar to the generalized Mycielski, but on its first two layers it forms a M$\ddot{o}$bius ladder. We prove the statement about their circular chromatic number with similar techniques. Moreover we present a similar result for a family of signed graphs. This talk is based on a joint work with Reza Naserasr (Universit´e de Paris, IRIF, CNRS, F-75006, Paris, France), S Rohini (Indian Institute of Technology Madras, India) and S Taruni (Indian Institute of Technology Dharwad, India). [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday May 16, 2023, 2PM, 147 Olympe de Gouges\\ **Frédéric Meunier** (CERMICS) //Coloring complements of line graphs.// \\ A first objective of this talk is to show that complements of line graphs enjoy nice coloring properties. For instance, all complements of line graphs have their local chromatic number equal to their (usual) chromatic number. There is also an elementary sufficient condition for their chromatic number to be equal to a natural upper bound, with various consequences such as a complete characterization of all induced subgraphs of the Kneser graph KG(n, 2) that have a chromatic number equal to its chromatic number, namely n − 2. A second objective is to take this topic as an opportunity to discuss the limits of the topological method. This latter is especially suitable for the study of coloring properties of complements of line graphs. Nevertheless, there are clues showing that most of our results cannot be obtained by the topological method. Joint work with Hamid Reza Daneshpajouh and Guilhem Mizrahi. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday May 9, 2023, 3PM, 147, Salles Olympe de Gouge\\ **Sebastiano Vigna** (Università degli Studi di Milano) //Monotonicity on undirected networks.// \\ Is it always beneficial to create a new relationship (have a new follower/friend) in a social network? This question can be formally stated as a property of the centrality measure that defines the importance of the actors of the network. Score monotonicity means that adding an arc increases the centrality score of the target of the arc; rank monotonicity means that adding an arc improves the importance of the target of the arc relatively to the remaining nodes. It is known that most centralities are both score and rank monotone on directed, strongly connected graphs. In this paper, we study the problem of score and rank monotonicity for classical centrality measures in the case of undirected networks: in this case, we require that score, or relative importance, improve at both endpoints of the new edge. We show that, surprisingly, the situation in the undirected case is very different, and in particular that closeness, harmonic centrality, betweenness, eigenvector centrality, Seeley's index, Katz's index, and PageRank are not rank monotone; betweenness and PageRank are not even score monotone. In other words, while it is always a good thing to get a new follower, it is not always beneficial to get a new friend. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday May 2, 2023, 3:30PM, [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09|ZOOM]]\\ **Cléophée Robin** (Wilfrid Laurier University Waterloo, Canada) //A Closure Lemma for tough graphs and Hamiltonian degree conditions// \\ A graph G is Hamiltonian if it exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G − S is at most |S| / t. We extended the Theorem of Hoàng by proving the following : Let G be a graph with degree sequence d_1,d_2,…,d_n and let t be a positive integer at most 4. If G is t-tough and if. ∀ i, t ≤ i [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Wednesday April 26, 2023, 3PM, 147, Salles Olympe de Gouge [[https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09|zoom]]\\ **Monika Csikos** (IRIF) //An introduction to VC-dimension// \\ Since the seminal work of Vapnik and Chervonenkis (1971), one of the basic quantities describing the complexity of a set system is the VC-dimension. As such, VC-dimension is the foundation of many theoretical results in learning theory, in computational geometry, and recently, in graph theory. While for simple geometric set systems (e.g. ones induced by half-spaces), one can bound the VC-dimension using elementary arguments, many applications require more complex set systems. A long standing central open problem since 1989 was bounding the VC-dimension of unions and intersections of half-spaces in high dimensions. In collaboration with A. Kupavskii and N. Mustafa, we resolved this problem by providing a tight lower bound in dimensions at least 4. In this talk, I give an introduction to the notion of VC-dimension, present our bounds on the VC-dimension of unions and intersections of half-spaces, then discuss some results on graphs with bounded VC-dimension. No prior knowledge of computational geometry or learning theory is required. A part of the talk is based on the paper M. Csikós, A. Kupavskii, N. H. Mustafa — Tight Lower Bounds on the VC-dimension of Geometric Set Systems (Journal of Machine Learning Research, 2019) The talk will also be available on zoom. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday April 25, 2023, 3PM, 147, Salles Olympe de Gouge\\ **Sagar Sawant** (IIT Madras, Chennai, India) //Digraph analogue of Stanley's Tree Conjecture,// \\ The $B$-polynomial defined by J. Awan and O. Bernardi is a generalization of Tutte Polynomial to digraphs. In this paper, we solve an open question raised by J. Awan and O. Bernardi regarding the expansion of $B$-polynomial in elementary symmetric polynomials. We show that the quasisymmetric generalization of the $B$-polynomial distinguishes a certain class of oriented proper caterpillars, and the class of oriented paths. We present a recurrence relation for the quasisymmetric $B$-polynomial involving deletion of a source or a sink. As a consequence, we prove that a class of digraph $\mathcal{D}$ is distinguishable if and only if the class $\mathcal{D}^{\vee}$ obtained by taking directed join of $K_1$ with each digraph in $\mathcal{D}$ is distinguishable, which concludes that the digraph analogue of Stanley's Tree conjecture holds for a large class of acyclic digraphs. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday April 11, 2023, 3PM, 1007\\ **Maud Szusterman** (IMJ-PRG) //Extended formulations of spanning tree polytopes// \\ A convex polytope $P \subset \R^d$, i.e. the convex hull of finitely many points in $\R^d$, can always be described by finitely many affine (in)equalities. The minimal number of inequalities needed for a description via affine constraints, is the number of facets of the polytope, we call it the size of the polytope. If $Q \subset \R^{d+r}$ is a polytope, and $\pi : \R^{d+r} \to \R^d$ an affine map such that $\pi(Q)=P$, one says that $Q$ is a (linear) lift of $P$. Some combinatorial polytopes $P_n$ admit a \emph{compact formulation}, meaning there exists a lift $Q_n$ of $P_n$, whose size is poly$(n)$. The search for compact formulation(s) is motivated by (linear) optimization problems. In this talk, we will introduce the spanning tree polytope $P_{SpT}(G)$ of a graph $G$, and present a compact formulation of $P_{SpT}(G)$, whose size is less than $n^3$ (where $n$ denotes the number of vertices of $G$). We will further discuss the case when $G=K_n$ is the complete graph on $n$ vertices, and the case of planar graphs. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Wednesday March 29, 2023, 2PM, 3052\\ **Valentin Bartier** (LIRIS) //Independent set reconfiguration in sparse graphs// \\ The problem of reconfiguring independent sets belongs to the broader field of combinatorial reconfiguration problems. It can be formulated as follows: given a collection of tokens placed on the vertices of an independent set of a graph, is it possible to move one by one these tokens to another target independent set, such that two tokens are never neighbors throughout the transformation? After a general introduction to combinatorial reconfiguration and the independent set reconfiguration problem, we will focus on the "Token Sliding" variant. In this variant, one step of the transformation consists in moving a token from a vertex to a neighboring vertex. We will focus on the parameterized complexity of this problem in sparse classes of graphs and on the new tools we have recently designed for the development of FPT algorithms. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday March 14, 2023, 3PM, 1007\\ **Antoine Dailly** (LIMOS Clermont Auvergne) //Algorithms for the Metric Dimension problem on directed graphs// \\ In graph theory, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices, such that for any pair of vertices of the graph, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem has mainly been studied on undirected graphs, and has gained a lot of attention in recent years, mainly because of its difficulty: it is NP-complete and has a best polynomial-time approximation factor of log(n) even on very restricted graph classes. We focus our study on directed and oriented graphs (the difference is that directed graphs may contain 2-cycles, unlike oriented graphs), for which the Metric Dimension has been recently studied. We prove that Metric Dimension remains NP-hard, even on planar DAGs of maximum degree 6. However, we find linear-time algorithms solving the problem on directed trees (directed graphs whose underlying graph is a tree) and on orientations of unicyclic graphs. Finally, we give a fixed-parameter-tractable algorithm for directed graphs when parameterized by modular-width. [[en:seminaires:adg:index|Distributed algorithms and graphs]]\\ Tuesday January 10, 2023, 3PM, Salle 1007\\ **Nacim Oijid** (LIRIS) //On the complexity of Avoidance positionnal games// \\ Avoidance games are games in which two players claim vertices of a hypergraph and try to avoid some structures. These games have been studied since the introduction of the game of SIM in 1968, but only few complexity results have been found out about them. In 2001, Slany proved some partial results on Avoider-Avoider games complexity, and in 2017 Bonnet et al. proved that short Avoider-Enforcer games are Co-W[1]-hard. More recently, in 2022, Miltzow and Stojaković proved that these games are NP-hard. As these games correspond to the misère version of the well-known Maker-Breaker games, introduced in 1963 and proven PSPACE-complete in 1978, one could expect these games to be PSPACE-complete too, but the question has remained open since then. During this talk, we will show that both Avoider-Avoider and Avoider-Enforcer conventions are PSPACE-complete, and that consequently, some particular Avoider-Enforcer games also are.