11ème Journée d'Optimisation dans les Réseaux
Onglets principaux
Intitulé:
Graphes et Réseaux
Date:
Vendredi, 28 Septembre, 2018
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 second part, we investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network G admits a core,
thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by
Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset X of n
vertices of a graph G with delta-thin geodesic triangles there exists a vertex m of G such that the ball B(m,4delta) of radius 4delta centered at m intercepts at least one half of the
total flow between all pairs of vertices of X, where the flow between two vertices x,y of X is carried by geodesic (or quasi-geodesic) (x,y)-paths. We show that the point
m can be constructed in the following way: take a median point m* of X (a point minimizing the sum of distances to the points of X) in the injective hull of G and then a closest to m* point in G.
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).
The talk is based on the papers
[1] V. Chepoi, F. Dragan, and Y. Vaxès, Core congestion is inherent in hyperbolic networks, SODA 2017, <http://arxiv.org/abs/1605.03059> .
[2] J. Chalopin, V. Chepoi, F. Dragan, G. Ducoffe, A. Mohammed, and Y. Vaxès, Fast approximation and exact computation of negative curvature parameters of graphs, SoCG 2018, <https://arxiv.org/abs/1803.06324>.
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
Recent developments in mathematical epidemiology have identified a relationship between the time to extinction of an epidemic spreading over a network and the spectral radius of the underlying graph i.e. the largest eigenvalue of its adjacency matrix.
At the same time, new generation networking technologies such as NFV (network function virtualization) and SDN (software-defined networking) have enabled real-time reconfiguration of network topology.
In this context, we introduce the maximum spectral subgraph problem: given an undirected graph and a threshold value, the task is to find a partial subgraph with the maximum number of edges such that its spectral radius is bounded above by the threshold. Solving this problem would prescribe an inexpensive network topology reconfiguration which guarantees that a malware epidemic would disappear in a short amount of time.
Unfortunately, the maximum spectral subgraph problem is NP-hard which motivates us to study whether it can be approximated in polynomial time.
In this talk, we will present a simple randomized (log^2 n)-approximation algorithm based on the relaxation and rounding framework and give experimental evidence that it is competitive with heuristics and algorithms for related variants of the problem.
The analysis of the approximation algorithm is based on the paper:
C. Bazgan, P. Beaujean, and E. Gourdin, Relaxation and matrix randomized rounding for the maximum spectral subgraph problem, COCOA 2018