# 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, Thomas Dissaux (PhD student, since Oct. 2020), 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

He gave a seminar on “Weighted proper orientations of trees and graphs of bounded treewidth”, Dec. 10th, 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

He gave a seminar on “Fault Tolerant Complete Matchings in Bipartite Graphs and Related Problems”, Dec. 17th, 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)(canceled due to strikes in Chile)

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

## Publications of (or related to) the Project

### International journals

- Fionn Mc Inerney, N. Nisse, and Stéphane Pérennes. Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between.

Algorithmica, 83(5): 1459-1492 (2021). - Hernan Lespay and Karol Suchan. A case study of Consistent Vehicle Routing Problem with Time Windows. International Transactions in Operational Research 28(3):1135–1163, 2021.
- Eurinardo R. Costa, Victor Lage Pessoa, Rudini M. Sampaio, Ronan Soares. PSPACE-completeness of two graph coloring games. Theoretical Computer Science, 2020.
- M. Kanté, T. Marcilon and R.M. Sampaio. On the parameterized complexity of the geodesic hull number. Theoretical Computer Science, v. 791, p. 10-27, 2019.
- Julien Bensmail, Fionn Mc Inerney and Nicolas Nisse. Metric Dimension: from Graphs to Oriented Graphs. Accepted in Discrete Applied Maths, 2021.
- J. Araujo and P. Arraes. Hull and geodetic numbers for some classes of oriented graphs. Accepted in Discrete Applied Mathematics.

### International conferences

- Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, and N. Nisse. The Largest Connected Subgraph Game.

In Proceedings of 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), to appear, 2021. -
Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle. Treelength of Series-parallel graphs.

To appear in Proceedings of 11th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2021. - Cláudio Carvalho, Jonas Costa, Cláudia Sales, Raul Lopes, Ana Karolinna Maia de Oliveira, Nicolas Nisse. On the characterization of networks with multiple arc-disjoint branching flows. In Anais do Encontro de Teoria da Computacao (ETC), Brazil, 2020.
- 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, Ana Karolinna Maia de Oliveira, Nicolas Nisse, Ana Silva. On finding the best and worst orientations for the metric dimension. Research rep., 2020. Submitted.
- Fabricio Benevides, Jean-Claude Bermond, Hicham Lesfari, Nicolas Nisse. Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation. Research Report, 2021. Submitted.
- S. Cichacz and Karol Suchan. Vertex-Fault Tolerant Complete Matching in Bipartite graphs: the Biregular Case. Submitted.
- T.H. Le, Brigitte Jaumard and Karol Suchan. Efficient Car Sorting in a Flat Yard. Submitted.
- Hernan Lespay and Karol Suchan. Territory Design for Dynamic Multi-Period Vehicle Routing Problem with Time Windows. Submitted.
- J. Araujo, A. Cezar, C.V.G.C Lima, V.F. dos Santos, A.S. Silva. On the proper orientation number of chordal graphs. Submitted.
- J. Araujo, M. Bougeret, V. Campos and I. Sau. Kernelization of Maximum Minimal Vertex Cover. Submitted.
- J. Araujo, M. Bougeret, V. Campos and I. Sau. Parameterized complexity of computing maximum minimal blocking and hitting sets. Submitted.
- Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Nicolas Nisse, and Karol Suchan. Semi-proper orientations of chordal graphs. In preparation.
- Julien Bensmail, Victor Campos, Matheus Correia, Ana Karolina Maia, Nicolas Nisse, Ana Silva. Characterizing butterfly minors of cylindrical grids. In preparation.

### Theses

- Hernán Lespay. Consistent Vehicle Routing. Ph.D. thesis, Universidad Adolfo Ibáñez, Chile, January 22nd, 2021.
- Fionn McInerney. Domination and Identification Games in Graphs. Ph.D. thesis, Univ. Côte d’Azur, July 8th, 2019.
- Camila Sena Araújo. Colorações backbone em grafos com galáxias backbone. Master’s in Mathematics – Universidade Federal do Ceará. 2021.
- Pedro Santos Mota e Arraes. Números de envoltória e geodético em classes de grafos orientados. Master’s in Mathematics – Universidade Federal do Ceará. 2020.
- Thomas Dissaux. Graph Decompositions and treelength. M2 internship (March-August 2020), Univ. Côte d’Azur.
- Pedro Paulo de Medeiros. Coloração Acíclica. Master’s in Mathematics – Universidade Federal do Ceará, 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.