# GALOP

## Graphs ALgorithms for Optimization Problems

### Programme STIC-AmSud 2019-2020

###
- Centre de recherche INRIA Sophia Antipolis — Méditerranée, Team project COATI, France
- Universidade Federal do Ceara, Fortaleza, Brazil
- Universidad Diego Portales (UDP), Santiago, Chile

International coordinator | Brazilian coordinator | Chilean coordinator | |
---|---|---|---|

Name, surname | Nicolas Nisse | Julio Araujo | Karol Suchan |

Title | Chargé de recherche Inria (Research officer) | Associated professor | Associated professor |

Institution | team-project COATI, common team INRIA Sophia Antipolis – I3S (UMR 7271 of the CNRS and the University of Nice-Sophia Antipolis) |
Departamento de Matemática Universidade Federal do Ceará. ParGO Research Group, Fortaleza Brazil. |
Universidad Diego Portales, Facultad de Ingeniería y Ciencias Santiago, Chile. |

Address |
Projet COATI, commun Inria, I3S(CNRS/UNSA)
INRIA Sophia-Antipolis 2004, route des Lucioles — B.P. 93 06902 Sophia-Antipolis Cedex France |
Universidade Federal do Ceará
Departamento de Matemática – bloco 914. Av. Humberto Monte, s/n, Campus do Pici. CEP 60440-900. Fortaleza, CE Brazil. |
Universidad Diego Portales,
Facultad de Ingeniería y Ciencias Av. Ejército Libertador 441, Santiago, Chile |

URL | http://www-sop.inria.fr/members/Nicolas.Nisse/ | http://www.mat.ufc.br/~julio/ | http://udp.academia.edu/KarolSuchan |

Phone | +33 4 97 15 53 28 | +55 (85) 33 66 93 13 | +56 9 57 76 57 79 |

name dot surname arobase inria dot fr | name arobase mat dot ufc dot br | name dot surname arobase mail dot udp dot cl |

## Activity reports

## Participants

- France: Julien Bensmail, David Coudert, Foivos Fioravantes (PhD student, since Oct. 2019), Frédéric Giroire, Frédéric Havet, Fionn Mc Inerney (former Ph.D. student, defended July 8th 2019), Nicolas Nisse, Stéphane Pérennes.
- Brazil: Julio ARAUJO, Fabricio Siqueira BENEVIDES, Victor CAMPOS, Ana Karolinna MAIA de OLIVEIRA, Rudini SAMPAIO, Claudia Linhares SALES, Raul LOPEZ (PhD student), Ana Shirley Ferreira da SILVA, Jonas Costa Ferreira da Silva (PhD student), Ronan Pardo SOARES.
- Chile: Hernán LESPAY (PhD student, since 2017), Pedro MONTEALEGRE, Eduardo Moreno, Sebastián MUÑOZ (PhD student, since 2018), Karol Suchan.

## Documents

## Visits in 2019

- To Inria
- R. Lopez, 1 month, July 2019
- F. Benevides, invited Professor, 11 months, September 2019- July 2020
- J. Araujo, 2 weeks, December 4-20th 2019
- A. K. Maia, 2 weeks, December 4-20th 2019
- C. Linhares Sales, 2 weeks, December 4-20th 2019
- J. Costa, PhD thesis “sandwich”, 1 year, December 2019- November 2020
- K. Suchan, 2 weeks, December 8-21th 2019

- To UFC
- J. Bensmail, 2 weeks, May 4-18 2019

He gave a seminar on « 1-2-3 conjecture », May 6th 2019. - N. Nisse, 2 weeks, May 4-18 2019

He gave a seminar on «Recovery of disrupted airline operations andconstrained matchings», May 10th 2019. - K. Suchan, 1.5 weeks, August 10-19 2019

He gave a seminar on “Vertex-Fault Tolerant Complete Matching in Bipartite graphs: the Biregular Case” (August 13th 2019) during the Workhop organized for the 20 years of the team Pargo,

- J. Bensmail, 2 weeks, May 4-18 2019
- To UDP
- F. Havet, 2 weeks, October 30th-10th November 2019

Invited speaker at French-latin American conference on new trends in Applied Mathematics (Flacam)

- F. Havet, 2 weeks, October 30th-10th November 2019

## Publications of (or related to) the Project

### International conferences

- J. Bensmail, F. Mc Inerney, N. Nisse. Metric Dimension: from Graphs to Oriented Graphs. In Proceedings of the 10th Latin & American Algorithms, Graphs and Optimization Symposium (LAGOS 2019). Belo Horizonte, Brazil, 2019.

### Research Reports

- Julio Araujo, Julien Bensmail, Victor Campos, Frédéric Havet, Karol Maia, Nicolas Nisse, Ana Silva. On finding the best and worst orientations for the metric dimension. Work in progress.
- Sylwia Cichacz, Karol Suchan: Vertex-Fault Tolerant Complete Matching in Bipartite graphs: the Biregular Case. CoRR abs/1907.04844 (2019)

### Theses

- Fionn McInerney. Domination and Identification Games in Graphs. Ph.D. thesis, Univ. Côte d’Azur, July 8th, 2019.

## Related Links

Workhop organized for the 20 years of the team Pargo: http://dc.ufc.br/~pargo_20_50/

## Scientific programme and objectives

Our goal is to study the Computational Complexity of several important problems arising in

networks. In particular, we will focus on the computation of metric or structural properties and

parameters of large networks. We plan to design efficient exact algorithms for solving these

problems or to theoretically prove that such algorithms cannot exist. In the latter case, we will then

design approximation algorithms, or prove that none exists. In all cases, we aim at implementing

our algorithms and use them on real-world instances such as large road networks or huge social

networks.

## Work-program

In this project, we will mainly tackle three kinds of network problems that are naturally modeled as

graph-theoretical problems.

- First, we will consider graph decompositions: how to efficiently compute “good”

decompositions (e.g., tree-decompositions) and how such decompositions (e.g.,

decompositions with clique-separators) can be used to speed-up the actual running time of

algorithms for computing various graph metrics. As an example of application, we will

consider road-networks for which new usages (e.g. multi-modal transportation) require

algorithms to compute shortest paths more efficiently and in a dynamic setting. - Second, we will study combinatorial games in graphs because they naturally model many

network problems in different contexts. For instance, localization games are a gametheoretic

way to handle the detection of faults in multiprocessor networks (e.g., via

identifying codes or metric dimension). Another example is the surveillance game that is a

nice theoretical model for data prefetching. - Last but not least, we will obtain new results in two graph optimization problems: graph

colorings that naturally model various allocation problems (e.g., resource assignment, like

channel assignment in radio networks, personnel assignment, etc.), and graph convexity that

may be seen as a model of diffusion in a network (e.g., spreading opinions/innovations,

propagating diseases/faults, logical inference, etc.). An objective of particular interest is to

study propagation of information in real social networks.

Since all these problems are complex, we will start by considering simpler models or hypothesis

(for instance, consider a problem on a more restricted graph class) and then obtain results in a more

refined setting. For instance, we will first focus on the case of undirected graphs, which is generally

easier than that of directed graphs. After getting some understanding of the undirected case, we will

then consider the directed one.