# 11ème Journée d'Optimisation dans les Réseaux

## Onglets principaux

La 11ème journée d'Automne organisée par le groupe de travail d'Optimisation des Réseaux du GDR-RO aura lieu dans l'amphi Hermitte à l'Institut Henri Poincaré (IHP) le 28 Septembre 2018.

L'adresse de l'IHP est au 11 Rue Pierre et Marie Curie, 75005 Paris

L'inscription est gratuite mais à effectuer dans l'onglet "Register" de cette page.

**Le programme de la journée du Vendredi 28/09/2018:**

9h00- 9h30 accueil

9h30-10h30 **Michel Habib (IRIF - Université Paris Diderot)** *Graph searches and geometric convexities in graphs* - Joint work with Feodor Dragan and Lalla Mouatadid

Graph convexities or discrete convexities has been studied for a while and has many applications, see for example Farmer and Jamison (1987), Duchet (1988), Chv\'atal (2008), Doignon (2017) ....

After an introduction to these notions, we focuse on the relationships between graph searches and geometric graph convexities. Geometric convexities are of special interest since they are related to antimatroids and therefore to greedy algorithms. Nearly every graph search produces a convex geometry, i.e. every set of visited vertices is convex for some convex geometry. Many convex geometries have been defined on graphs using an interval definition: geodesic, monophonic . . . . We recall that the Lexicographic Breadth First Search (LexBFS) captures these convex geometries on many graph classes and we finish with some new properties on AT-free graphs.

We hope to convince that convex geometries are the good framework to understand the greedy properties of graph searches, such as BFS, DFDS, LexBFS and LexDFS.

10h30 - 11h00 Pause café

11h00 - 12h00* ***Yannis Manoussakis (LRI - Université Paris Sud)** *Subgraphs with specified color properties in vertex- or edge-colored graphs*

In general, graphs are divided in two important classes, directed and undirected ones. However, because of recent technological developments, these two classes of graphs are not powerful enough to model all existing real-life constraints. For example, if one wants to differentiate highways from national roads, and main from secondary roads, a good idea would be to use colors. As another example, the Web graph may be considered as a vertex-colored graph where the color of a vertex represents the content of the corresponding page (red for mathematics, yellow for physics, etc.). When the edges/vertices of graphs are colored, then we talk about c-edge/vertex colored graphs (c is the number of colors), models which in fact generalize various classes of graphs. In general, one can observe that problems related to colored graphs often consist in finding subgraphs such as paths, cycles and trees, with, in addition, specified constraints on colors.

In the case of c-edge-colored graphs, one such natural constraint is the proper coloring one, i.e., any two adjacent edges differ on colors. Given such an edge-colored graph, original problems correspond to extracting subgraphs, for example, Hamiltonian and Eulerian paths or cycles, trees, etc., colored in this specified pattern. Although a large body of work has already been done, in the most of these researches the number of colors is restricted to two. For instance, while it is well known how to find efficiency a properly edge colored Hamiltonian cycle in a 2-edge colored complete graph, it is a long-standing question how to find such cycles in complete graphs whose edges are colored by any number of colors. Here we survey a series of results concerning proper subgraphs in c-colored graphs, for arbitrarily c.

In the case of vertex-colored graphs, we deal with tropical subgraphs, a concept with direct applications to the web graph and in bioinformatics (Multiple Sequence Alignment Pipeline or for multiple protein-protein Interaction networks). More precisely, given a vertex-colored graph, a tropical subgraph (induced or otherwise) is defined to be a subgraph where each color of the initial graph appears at least once. Notice that in a tropical subgraph, adjacent vertices can receive the same color, thus a tropical subgraph may not be properly colored. Potentially, many graph invariants, such as the domination number, the vertex cover number, maximum matchings, independent sets, connected components, shortest paths, etc. can be studied in their tropical version. This notion is close to, but somewhat different from the colorful concept (all colors of the subgraph are different) used for paths and elsewhere in vertex-colored graphs. It is also related to the concepts of color patterns (the subgraph has fixed color patterns) used in bio-informatics. Here we explain some results on our ongoing work on tropical dominating sets, vertex covers, connected subgraphs, maximum matchings and tropical homomorphisms.

12h00 - 12h30 **Admed Mabrouk (Engie)** *Proposition d’un système d'aide au suivi de l'état de santé des éoliennes : une approche à base de réseaux bayésiens*

12h30-13h30 buffet déjeuner offert

13h30-14h30 **Yann Vaxes (LIS- Université Aix-Marseille)** *Au coeur des réseaux hyperboliques*

In the first part of the talk, we will introduce Gromov hyperbolicity and recall several characterizations of delta-hyperbolic geodesic metric spaces and graphs.

In the third part of the talk, (and if the time will permit), we will describe a simple factor 8 approximation algorithm for optimal hyperbolicity of an n-vertex graph in optimal O(n^{^2}) time (assuming that the input is the distance matrix of the graph).

14h30-15h30 : **Mourad Baiou (LIMOS - Université de Clermont Auvergne)** *Sparsest Cut via Max Cut*

We study the sparsest cut problem when the ”capacity-demand” graph is pla-

nar, and give a combinatorial algorithm. In this type of graphs there is an edge for each

positive capacity and also an edge for each positive demand. We extend this result to

graphs with no K5 minor. We also show how to find a maximum concurrent flow in these

two cases. We use ideas that had been developed for the max-cut problem, and show how

to exploit the connections among these problems.

15h30-16h00 pause café

16h00-16h30 **Dimitri Watel (Samovar -ENSIIE)** *Maximum Residual Flow Problem with Arc Destruction*

The maximum Residual Flow Problem with Arc Destruction is posed as follows. Given a directed network G, find a maximum flow such that when k arcs are deleted from G the value of a maximum flow in the residual network is maximum. It is proved that the problem is polynomial time solvable for k = 1 whereas it shown to be NP-hard for k = 2. The Adaptative Maximum Flow Problem was first adressed as an alternative to the robust maximum flow problem. In this model, the flow can be adjusted after the arc failures occurred. In this presentation, we are concerned with the Adaptative Maximum Residual Flow Problem, that is the maximum Residual Flow Problem with Arc Destruction when the flow can be reoriented. We focus on three variants of the problem : the original problem in which the attacker may destroy a given number k of arcs ; a variant where some of the arcs cannot be destroyed ; and a last variant where each destruction is associated to a given cost and where the attacker has a given destruction budget. For each of the three problems, we focus on complexity results. Those results depend on the maximum number of destructible arcs that can be found on a single path from the source to the sink. It has been proven that all the three problems are NP-Complete when this parameter is greater or equal to 4. We complete the results when we restrict the problem to instances where this parameter equals 2 or 3.

16h30-17h00 **Paul Beaujean (LAMSADE - Université Paris-Dauphine & Orange Labs)** *Fighting epidemics in networks with the maximum spectral subgraph - *Joint work with Cristina Bazgan and Eric Gourdin