RESEARCH CENTRE

Inria Centre
at Université Côte d’Azur

IN PARTNERSHIP WITH:

CNRS, Université Côte d’Azur

2023
ACTIVITY REPORT

Project-Team

COATI

Combinatorics, Optimization and
Algorithms for Telecommunications

IN COLLABORATION WITH: Laboratoire informatique, signaux systèmes
de Sophia Antipolis (I3S)

DOMAIN

Networks, Systems and Services,
Distributed Computing

THEME

Networks and Telecommunications

Contents

Project-Team COATI

1 Team members, visitors, external collaborators

2 Overall objectives

3 Research program

4 Application domains

4.1 Telecommunication networks
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Other Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Social and environmental responsibility

5.1 Footprint of research activities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Highlights of the year

6.1 New team member . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Promotions

7 New software, platforms, open data

7.1 New software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 k-shortest simple paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.2 SageMath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.3 WorldDynamics.jl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.4 Idawi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.5 OnlineGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Open data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.1 Temporal brain networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.2 Labeled temporal brain networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2

4

4

5
5
5

5
5

6
6
6

6
6
6
6
7
7
8
9
9
9

8 New results

8.1 Network design and management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9
9
8.1.1 What is the carbon footprint of one hour of video streaming? . . . . . . . . . . . . . . 10
8.1.2 Machine learning for video streaming systems . . . . . . . . . . . . . . . . . . . . . . . 10
8.1.3 Learning-based packet routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
8.1.4 Modeling LoRa networks for the IoT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
8.1.5 Aerial networks for sensor coverage and energy harvesting . . . . . . . . . . . . . . . 11
8.1.6 Gossiping with interference in radio ring networks . . . . . . . . . . . . . . . . . . . . 12
8.1.7 A middleware for the experimentation on IoT mobile networks - a decentralized Web

backend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.2 Graph algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.2.1 Complexity of graph problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.2.2 Combinatorial games in graphs
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.2.3 Algorithms for social networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8.2.4 Algorithm engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8.3 Graph and digraph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8.3.1 Partitioning and labelling graphs and digraphs
. . . . . . . . . . . . . . . . . . . . . . 17
8.3.2 Structural digraph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
8.3.3 Metric dimension in oriented graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.4 Machine learning theory and algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.5 Collaborations with other fields
8.5.1 Analysis of temporal brain networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.5.2 Temporal graph neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.5.3 Distributed algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

9 Bilateral contracts and grants with industry

24
9.1 Bilateral contracts with industry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

10 Partnerships and cooperations

10.2 International research visitors

25
10.1 International initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
10.1.1 Inria associate team not involved in an IIL or an international program . . . . . . . . 25
10.1.2 Participation in other International Programs . . . . . . . . . . . . . . . . . . . . . . . 25
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10.2.1 Visits of international scientists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10.2.2 Visits to international teams
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10.3.1 Horizon Europe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10.4 National initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.4.1 GDR Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

10.3 European initiatives

11 Dissemination

33
11.1 Promoting scientific activities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.1.1 Scientific events: Steering Committees . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.1.2 Scientific events: organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.1.3 Scientific events: selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.1.4 Journal
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
11.1.5 Invited talks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
11.1.6 Leadership within the scientific community . . . . . . . . . . . . . . . . . . . . . . . . 36
11.1.7 Scientific expertise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
11.1.8 Research administration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
11.2 Teaching - Supervision - Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
11.2.1 Teaching Responsibilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
11.2.2 Teaching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
11.2.3 Supervision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
11.2.4 Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
11.3 Popularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
11.3.1 Internal or external Inria responsibilities . . . . . . . . . . . . . . . . . . . . . . . . . . 42
11.3.2 Articles and contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
11.3.3 Education . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
11.3.4 Interventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

12 Scientific production

43
12.1 Major publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
12.2 Publications of the year
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
12.3 Cited publications

Project COATI

1

Project-Team COATI

Creation of the Project-Team: 2013 January 01

Keywords

Computer sciences and digital sciences

A1.2.1. – Dynamic reconfiguration

A1.2.3. – Routing

A1.2.5. – Internet of things

A1.2.9. – Social Networks

A1.6. – Green Computing

A3.5.1. – Analysis of large graphs

A7.1. – Algorithms

A7.1.1. – Distributed algorithms

A7.1.3. – Graph algorithms

A8.1. – Discrete mathematics, combinatorics

A8.2. – Optimization

A8.2.1. – Operations research

A8.7. – Graph theory

A8.8. – Network science

A9.7. – AI algorithmics

A9.9. – Distributed AI, Multi-agent

Other research topics and application domains

B1.1.1. – Structural biology

B1.2.3. – Computational neurosciences

B6.3.3. – Network Management

B6.3.4. – Social Networks

B7.2. – Smart travel

B9.5.1. – Computer science

2

Inria Annual Report 2023

1 Team members, visitors, external collaborators

Research Scientists

• David Coudert [Team leader, Inria, Senior Researcher, HDR]

• Jean-Claude Bermond [CNRS, Emeritus, HDR]

• Frédéric Giroire [CNRS, Senior Researcher, HDR]

• Frédéric Havet [CNRS, Senior Researcher, HDR]

• Emanuele Natale [CNRS, Researcher]

• Nicolas Nisse [Inria, Senior Researcher, promoted in Oct. 2023, HDR]

• Andre Nusser [CNRS, Researcher, from Dec 2023]

• Stéphane Pérennes [CNRS, Senior Researcher, HDR]

Faculty Members

• Julien Bensmail [Université Côte d’Azur, Associate Professor, HDR]

• Christelle Caillouet [Université Côte d’Azur, Associate Professor, Delegation Inria until 31/08/2023]

• Alexandre Caminada [Université Côte d’Azur, Professor, HDR]

• Joanna Moulierac [Université Côte d’Azur, Associate Professor, Delegation Inria since 01/09/2023]

• Michel Syska [Université Côte d’Azur, Associate Professor]

• Chuan Xu [Université Côte d’Azur, Associate Professor]

Post-Doctoral Fellows

• Caroline Brosse [CNRS, Post-Doctoral Fellow, from Oct 2023]

• Nicolas De Almeida Martins [UFC Fortaleza, from Nov 2023, funded by CAPES]

• Damien Rivet [Inria, Post-Doctoral Fellow, until Jun 2023]

PhD Students

• Arthur Carvalho Walraven Da Cunha [Inria, until Sep 2023]

• Tiago Da Silva Barros [Université Côte d’Azur]

• Igor Dias Da Silva [Inria, until Sep 2023]

• Thomas Dissaux [Université Côte d’Azur, until Sep 2023]

• Ilias Driouich [Amadeus, CIFRE, until Sep 2023]

• Henrique Lovisi Ennes [Université Côte d’Azur, from Oct 2023]

• Lucas Picasarri Arrieta [Université Côte d’Azur]

• Clement Rambaud [ENS Paris, from Oct 2023]

• Aurora Rossi [Université Côte d’Azur]

Project COATI

3

Interns and Apprentices

• Justine Cauvi [Inria, Intern, from Jun 2023 until Jul 2023]

• Mael Clergue [Inria, Intern, from Jun 2023 until Aug 2023]

• Paulo Bruno De Sousa Serafim [GSSI L’Aquila, Intern, until Mar 2023]

• Davide Ferre [Inria, from Feb 2023, Relais thèse]

• Lilian Fortas [Inria, Intern, from Aug 2023]

• Clement Rambaud [ENS Paris, Intern, until Mar 2023]

• Teiki Rigaud [ENS Paris, Intern, from Jun 2023 until Aug 2023]

• Pietro Ventrella [Inria, Intern, from Mar 2023 until Aug 2023]

Administrative Assistant

• Patricia Riveill [Inria]

Visiting Scientists

• Pierre Aboulker [ENS Paris, until Mar 2023, Associate Professor]

• Joergen Bang Jensen [University of Southern Denmark, from May 2023 until May 2023, Professor]

• Zheng Chen [Linkoping University, from Jun 2023 until Jun 2023, Associate Professor]

• Pierluigi Crescenzi [GSSI L’Aquila, from Apr 2023 until Jul 2023, Professor]

• Andrea D’Ascenzo [University of L’Aquila , from Sep 2023 until Nov 2023, PhD student]

• Fabien Dufoulon [Lancaster University, from Sep 2023 until Oct 2023, Associate Professor]

• Florian Horsch [CISPA Saarbrücken , from Jun 2023 until Jun 2023, Post-doctoral fellow]

• Takako Kodate [Tokyo Woman’s Christian University, Japan, from Feb 2023 until Mar 2023]

• Amos Korman [FILOFOCS, from Aug 2023 until Aug 2023, Senior Researcher]

• Claudia Linhares Sales [UFC Fortaleza, from Dec 2023, Professor]

• William Lochet [LIRMM, until Mar 2023, CNRS]

• Ana Karolinna Maia [UFC Fortaleza, from Dec 2023, Associate Professor]

• Ido Nachum [EPFL, from Jun 2023 until Jul 2023, Post-doctoral fellow]

• André Nusser [University of Copenhagen, from Feb 2023 until Feb 2023, Postdoc]

• Malgorzata Sulkowska [University of Wroclaw, from May 2023 until May 2023, Associate Professor]

• Raul Wayne Texeira Lopes [LIRMM, until Feb 2023, Post-doctoral fellow]

External Collaborator

• Michel Cosnard [Université Côte d’Azur, Emeritus Professor, HDR]

4

Inria Annual Report 2023

2 Overall objectives

COATI is a joint team between the Inria Centre at Université Côte d’Azur and the I3S laboratory (Inform-
atique Signaux et Systèmes de Sophia Antipolis), which belongs to CNRS (Centre National de la Recherche
Scientifique) and Université Côte d’Azur. Its research fields are Algorithmics, Discrete Mathematics, and
Combinatorial Optimization, with applications mainly in telecommunication networks.

The main objectives of the COATI project-team are to design networks and communication algorithms.
In order to meet these objectives, the team studies various theoretical problems in Discrete Mathematics,
Graph Theory, Algorithmics, and Operations Research and develops applied techniques and tools, espe-
cially for Combinatorial Optimization and Computer Simulation. In particular, COATI used in the last
years both these theoretical and applied tools for the design of various networks, such as SDN (software
defined networks), WDM, wireless (radio), satellite, and peer-to-peer networks. This research has been
done within various industrial and international collaborations.

COATI also investigates other application areas such as bio-informatics and transportation networks.
The research done in COATI results in the production of prototypes and more advanced software, and

in the contribution to large open source software such as Sagemath.

3 Research program

Since its creation in 2013, the objectives of COATI are to conduct fundamental research in Discrete
Mathematics, Graph Theory, Digraph Theory, Algorithms and Operations Research, and to use these
tools for studying specific network optimization problems. Notice that we are mostly interested in
telecommunications networks. However, our expertise can be applied to solve many other problems in
various areas (transport, biology, resource allocation, social sciences, smart-grids, speleology, etc.) and
we collaborate with teams of these other domains. COATI also contributes to the development of software
components in order to validate proposed algorithms and to boost their dissemination.

The research program of COATI is therefore structured as follows.

• We conduct fundamental research in graph and digraph theory. Our goal is to better understand
the structure of (di)graphs and which particular (sub)structures make an optimization problem
on (di)graphs difficult. We are particularly interested in digraphs that are less investigated than
(undirected) graphs, although most optimization problems are naturally modeled using digraphs.
This is certainly due to the fact that several problems that can be solved in polynomial time on
graphs are hard to solve on digraphs.

• We use our knowledge to design algorithms on (di)graphs (exact, sub-exponential, parameterized,
approximation, heuristics) in order to solve various optimization problems. We also investigate
games on graphs as an algorithmic counterpart of some (di)graph theory studies to get more
insight on problems and (di)graphs properties. One of the challenges we have to face in the design
of algorithms is the increase in size of practical instances. It is difficult, if not impossible, to
optimally solve practical instances using existing tools. Therefore, we have to find new ways to
address problems using reduction and decomposition methods, characterization of polynomial
instances (which are sometimes the practical ones), or design of algorithms with acceptable
practical performances independently of the worst case time complexity.

• We study specific network optimization problems at both design and management levels such as
energy efficiency in networks, routing reconfiguration of optical and software defined networks
(SDN), placement and migration of chains of virtual functions (NFV), compact routing in large-scale
networks, deployment and management of fleet of drones, design of reliable wireless networks,
evolution of the routing in case of any kind of topological modifications (maintenance operations,
failures, capacity variations, ...), survivability to single and multiple failures, etc. These specific
problems often come from questions of our industrial partners (CIENA, Huawei, Orange labs). We
first contribute to the modeling of these problems; then we either use existing tools or develop new
tools in Operation Research and (Di)Graph Theory to solve them.

Project COATI

5

• We also investigate optimization problems in other application fields (see Section 8.5) such as
structural biology, transportation networks, economy, sociology, etc. For instance, we collaborate
with Inria project-team CRONOS (Computational modelling of brain dynamical networks) from
Sophia Antipolis in the field of computational neuro-sciences. In the area of intelligent transport
systems, we collaborate with the SMEs BeNomad and Instant-System on routing problems in multi-
modal transportation systems. We also collaborate with GREDEG (research center in economics,
law, and management) and the SKEMA business school on the analysis of the impact of competitive
funding on the evolution of scientific networks.

These collaborations benefit to the above mentioned domains via the dissemination of our tools.
Also, they give rise to new problems of interest for our community, and help us to improve our
knowledge and to test our algorithms on specific instances.

• The research done in COATI results in the production of software (WorlDynamics.jl, etc.), and in the

contribution to large open-source softwares such as Sagemath.

Note also that besides our research activity, we are deeply involved in Terra Numerica and contribute

to disseminating our domain towards a general audience.

4 Application domains

COATI is mostly interested in telecommunications networks but also in the network structures appearing
in social, molecular, and transportation networks.

4.1 Telecommunication networks

We focus on the design and management of heterogeneous physical and logical networks. The project
has kept working on the design of backbone networks (optical networks, radio networks, IP networks).
However, the fields of Software Defined Networks and Network Function Virtualization are growing in
importance in our studies. In all these networks, we study routing algorithms and the evolution of the
routing in case of any kind of topological modifications (maintenance operations, failures, capacity
variations, etc.).

4.2 Other Domains

Our combinatorial tools may be well applied to solve many other problems in various areas (transport,
biology, resource allocation, chemistry, smart-grids, speleology, etc.) and we collaborate with experts of
some of these domains.

For instance, we collaborate with project-team ABS (Algorithms Biology Structure) from Sophia
Antipolis on problems from Structural Biology and with project-team CRONOS (formerly ATHENA) on
problems arising in computational neurosciences. In the area of transportation networks, we collaborate
with SMEs Benomad and Instant-System on dynamic car-pooling combined with multi-modal trans-
portation systems in the context of ANR project Multimod started in January 2018. We collaborate with
SME MillionRoads since October 2019 on the modeling and exploration of the HumanRoads database
that gathers more than 100 million curricula (studies and career paths of persons). Last, we collaborate
with GREDEG (Groupe de Recherche en Droit, Economie et Gestion, Université Côte d’Azur) and the
SKEMA business school on the analysis of the impact of competitive funding on the evolution of scientific
collaboration networks.

5 Social and environmental responsibility

5.1 Footprint of research activities

Joanna Moulierac is member of the I3S CO2 group since 2019. The objective of this working group is to
evaluate the environmental impact of our research activities and to propose ways to make them evolve by
2030, in order to fulfill the Paris agreements (www.i3s.unice.fr/co2/).

6

Inria Annual Report 2023

6 Highlights of the year

6.1 New team member

• André Nusser has been recruited as CRCN CNRS, section 7, at the I3S laboratory and he joined the

team in December 2023;

6.2 Promotions

• Nicolas Nisse has been promoted Senior Researcher (Directeur de Recherche) in October 2023;

7 New software, platforms, open data

7.1 New software

7.1.1 k-shortest simple paths

Name: k-shortest simple paths

Keywords: Graph, Graph algorithmics

Functional Description: Implementation in C++ of algorithms for computing the k shortest simple

paths from a source to a destination in a weighted directed graph.

Release Contributions: This version implements the standard algorithm proposed by Yen (Yen), the
Node Classification (NC) algorithm proposed by Feng, the Sidetrack Based (SB) algorithm proposed
by Kurz and Mutzel, and variants of SB proposed by Al Zoobi, Coudert and Nisse to reduce running
time (improved SB, SB*) and memory usage (Parsimonious SB, PSB). It also implements the Post-
pone Node Classification (PNC) algorithm proposed by Al Zoobi, Coudert and Nisse to reduce the
execution time of the NC algorithm.

URL: https://gitlab.inria.fr/dcoudert/k-shortest-simple-paths

Publications: hal-02865918, hal-03196830v2, hal-03196830, hal-03438331

Contact: David Coudert

Participants: David Coudert, Nicolas Nisse, Ali Al Zoobi

7.1.2 SageMath

Name: SageMath

Keywords: Graph algorithmics, Graph, Combinatorics, Probability, Matroids, Geometry, Numerical

optimization

Scientific Description: SageMath is a free open-source mathematics software system. It builds on top
of many existing open-source packages: NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT,
R and many more. Access their combined power through a common, Python-based language or
directly via interfaces or wrappers.

Functional Description: SageMath is a free mathematics software system written in Python, combining

a large number of mathematical libraries under a common interface.

INRIA teams contribute in different ways to the software collection. COATI adds new graph
algorithms along with their documentations and contributes the improvement and maintenance of
the graph module and its underlying data structures. LFANT contributes through libraries such as
ARB and PARI/GP, and directly through SageMath code for algebras and ring and field extensions.

Release Contributions: See http://www.sagemath.org/changelogs/

Project COATI

7

URL: http://www.sagemath.org/

Contact: David Coudert

Participants: David Coudert, Xavier Caruso

7.1.3 WorldDynamics.jl

Name: WorldDynamics.jl

Keywords: Integrated assessment modeling, Scientific computing, Julia programming language

Scientific Description: The World Dynamics project aims to provide a modern framework to investigate
integrated assessment models of sustainable development, based on current software engineering
and scientific machine learning techniques. Our group is developing a Julia library to allow scient-
ists to easily use and adapt different world models, from Meadows et al.’s World3 to recent proposals.
By enabling an open, interdisciplinary, and consistent comparative approach to scientific model
development, our goal is to inform global policy makers on environmental and economic issues.

Functional Description: Integrated Assessment Modeling is a research area that focuses on developing
and applying integrated models of human and earth systems to help understand how key aspects
of society may evolve in the future and how they might interact with the natural environment and
with a changing climate.

Despite the importance of the field, there has been no general software framework which allows
scientists to investigate integrated assessment models of sustainable development, by using and
adapting the most famous world models, from Meadows et al.’s World3 to recent proposals.

WorldDynamics.jl is a new software library written by members of the COATI Team, that aims to fill
such crucial gap, by providing a modern framework in the Julia programming language based on
current software engineering and scientific machine learning techniques.

URL: https://github.com/worlddynamics/WorldDynamics.jl

Contact: Emanuele Natale

Participants: Pierluigi Crescenzi, Paulo Bruno De Sousa Serafim, Aurora Rossi, Hicham Lesfari, Emanuele

Natale

Partner: Gran Sasso Science Institute

7.1.4 Idawi

Keywords: Java, Distributed computing, Web Services, Parallel computing, Component models, Software

Components, P2P, Dynamic components, Internet of things, Distributed Applications

Functional Description: Idawi is a middleware for the development and experimentation of distributed
applications for multi-hop dynamic networks, such as the IoT, the Edge, Mobile Ad hoc Networks,
etc. Such networks can be represented by mixed (featuring both directed and undirected edges)
dynamic multi-graphs.

The development of Idawi was initially motivated by the need of the COATI Research group to
deploy scientific applications in clusters of computers, in order to run large experimentation
campaigns of graph algorithms. Idawi is an innovative arrangement of many features found
in existing tools into a fresh Open Source Java reference implementation, but it our Research
context we were led to introduce new features and ideas not found in other middleware solutions
for distributed computing - such as a fully decentralized network model, a by-default collective
communication/computation model, etc.

These naturally turned Idawi into a Research software platform for the experimentation of middleware-
level techniques.

8

Inria Annual Report 2023

Idawi defines applications elements as components organized into a multi-hop overlay network on
top of agnostic transport layers such as TCP, UDP and SSH (to enable component deployment and
communication even in the presence of NATs and firewalls). In the usual use case, there will be
only one component per device. But, in order to enable the simulation/emulation of large systems,
components can deploy other components in their Java Virtual Machine (JVM) or in another JVM(s)
in the same device.

Idawi proposes a structuring model of distributed applications, which then must conform to
a specific Object-Oriented model in the style of SOA: it defines that components expose their
functionality via services. Services hold data and implement functionality about the specific
concern they are about. Functionality is then exposed via operations, which can be triggered
remotely from anywhere in the component overlay.

The decentralized communication model of Idawi matches the very nature of mobile multi-hop
networks. It defines that components communicate with each other via messages of bounded size.
Messaging can be both synchronous (imperative) and asynchronous (reactive/event-driven). It is
powered by a default routing scheme and APIs that are tailored to collective communication, so as
to offer native support of parallel processing.

Idawi comes with a set of built-in fully decentralized services for automatized quick deploy-
ment/bootstrapping of components through SSH, interoperability through a REST-based web
interface, service provisioning and discovery, overlay management, and many other system-level
functionality.

In 2023, Idawi was completely refactored so as to introduce the notion of "digital twin" as the core of
its network management model. This idea is that the environment of a component is represented by
a digital twin — each remote component being represented by a local twin counterpart. Messages
can then be configured to be delivered to a twin or to the real component. Doing this smoothens
the API and enables any component to simulate distributed processes.

URL: https://github.com/lhogie/idawi

Publications: hal-03863333, hal-03886521, hal-03562184

Contact: Luc Hogie

7.1.5 OnlineGraph

Keywords: Java, Distributed computing, Graph algorithmics

Functional Description: OnlineGraph is a decentralized mixed graph library. OnlineGraph is designed
and developed as a specific application-level service of the Idawi middleware. It implements
a decentralized application distributed over a multi-hop overlay network of components. In
this application dedicated to the storage, edition and graphical rendering of graphs, graphs are
partitioned over the set of components. The application imposes no allocation strategy: it is left to
the application. A graph may be entirely allocated on one specific component, or a subset of the
components forming the application, or all of them.

Any component in the application can expose graphs to the Web—not just its component-local
part, but all the parts it has access to in the overlay networks. Graphs are then accessible to clients
through a set of Web servers exposing services.

A component-local part of a partitioned graph consists of three correlated sets: the vertex set, the
arc set, and the edge set. These sets can store the elements they contain in RAM or on disk, thereby
enabling persistence. In these sets, graph elements are represented by a 64-bit numerical ID, and
they can be associated to any data. This graph data structures can be used out of the distributed
infrastructure, just any graph library.

OnlineGraph is developed within the COATI Research group at Inria Sophia Antipolis and I3S
Computer Science Laboratory of Université Côte d’Azur.

URL: https://github.com/lhogie/OnlineGraph

Project COATI

Contact: Luc Hogie

7.2 Open data

7.2.1 Temporal brain networks

Participants:

Emanuele Natale, Aurora Rossi.

9

The Temporal Brain Networks dataset [78] contains networks representing the brain activity of 1047
subjects. These networks are derived from resting-state functional Magnetic Resonance Imaging (fMRI)
data from the Human Connectome Project (HCP). Network nodes represent brain regions, and edges
represent the correlation of a window of two brain region activity values. The networks are undirected
and weighted. The diagonal values are always 1 because they represent the correlation of a brain region
with itself. The number of nodes remains constant over time, while the weights of the edges change. The
dataset can be used to investigate brain activity as a temporal graph, it can be found in the Inria space on
the Recherche Data Gouv Platform ( https://entrepot.recherche.data.gouv.fr/dataset.xhtm
l?persistentId=doi%3A10.57745%2FPR8VUV).

This dataset has been assembled in collaboration with Samuel Deslauriers-Gauthier (CRONOS).

7.2.2 Labeled temporal brain networks

Participants:

Aurora Rossi.

The Labeled Temporal Brain Networks dataset contains a collection of temporal brain networks from 100
subjects. Each subject is labeled with their biological sex (M for male and F for female) and age range
(22-25, 26-30, 31-35, and 36+). The networks are obtained from resting-state fMRI data from the Human
Connectome Project (HCP) and are undirected and weighted. The number of nodes is fixed at 202, while
the edge weights vary over time. The dataset is labeled and intended for use in machine learning tasks,
specifically related to temporal graph neural network architectures. It can be found in the Inria space on
the Recherche Data Gouv Platform ( https://entrepot.recherche.data.gouv.fr/dataset.xhtm
l?persistentId=doi:10.57745/HHNT10).

8 New results

8.1 Network design and management

Network design is a very wide subject, which concerns all kinds of networks. In telecommunications,
networks can be either physical (backbone, access, wireless, etc.) or virtual (logical). The objective is to
design a network able to route a (given, estimated, dynamic, etc.) traffic under some constraints (e.g.
capacity) and with some quality-of-service (QoS) requirements. Usually the traffic is expressed as a family
of requests with parameters attached to them. In order to satisfy these requests, we need to find one
or several paths between their end-nodes. The set of paths is chosen according to the technology, the
protocol or the QoS constraints.

The last years have been very lively for networks with the rises of several new paradigms like Software
Defined Networks (SDN) and Network Function Virtualization (NVF), of new technologies like 5G, elastic
optical or LoRa networks, and of new usages like Internet of Things (IoT), high quality video streaming.
Furthermore, the development of machine-learning based methods brings new tools that can help solving
optimization problems. All these changes have brought or renewed a large number of algorithmic and
optimization problems for the design and management of networks. In this context, our work has mainly
focused on the study of three types of problems:

• How to efficiently route and place virtual resources in networks?

10

Inria Annual Report 2023

• How to use efficiently wireless networks?

• How to use machine-learning based methods for solving network optimization problems?

This very wide topic is considered by a lot of academic and industrial teams in the world. Our
approach is to tackle these problems with tools from operations research and discrete mathematics
(some of them developed in our teams, see Sections 8.2 and 8.3). This approach is shared by a number of
other teams worldwide, e.g. UFC and UNIFOR (Fortaleza, Brazil), Concordia Univ. (Montréal, Canada),
Univ. Adolfo Ibañez (Santiago, Chile), Univ. Oran (Algeria), with which we have a direct collaboration.

8.1.1 What is the carbon footprint of one hour of video streaming?

Participants:

Joanna Moulierac.

Video streaming traffic dominates the Internet traffic. In such a context, assessing the carbon footprint
of video streaming has received recently a significant attention with a number of models proposed to
associate a CO2 cost to one hour of streaming. The topic is even becoming sensitive, as highlighted by the
recent debate between the SHIFT project in France and the International Energy Agency (IEA) experts.
Our objective in this work is to compare the modeling assumptions and computation methods used by a
number of recent works to inform the debate. Indeed, initial results can be at odds, with up to one order
of magnitude difference in the results.

In [74], we focus on five different models. Our contributions are: (i) we relate the difference in the
results primarily to the perimeter of the study, e.g. including grey energy (production cost) or not; (ii)
we demonstrate that some of the assumptions, while necessary, are difficult to estimate due to a lack
of public data; (iii) we question some of the modeling assumptions made using a real deployment of
a streaming server in a controlled environment with up to 2000 clients; (iv) we propose a technique to
reconcile the models and obtain a CO2 estimate in between 60 and 400 grams when considering the
average worldwide electricity efficiency.

8.1.2 Machine learning for video streaming systems

Participants:

Frédéric Giroire.

HTTP-based streaming has become the dominant technology for streaming due to the widespread
adoption of the HTTP protocol. Many streaming providers use a combination of Content Delivery
Network (CDN) and Viewer-to-Viewer (V2V) technology, known as Hybrid CDN/V2V live streaming,
for both efficiency and cost-effectiveness. V2V technology allows for offloading streaming traffic from
the CDN and reducing operational costs, and WebRTC technology facilitates direct V2V transfer, as it
is natively supported by all browsers. In a WebRTC-based V2V network, some viewers cache the video
chunks on their devices, while others wait and fetch chunks from their neighbors. A common strategy
used to determine when a viewer should stop waiting for chunk delivery and revert to the CDN is called
Random Waiting Time Control (RWC). However, due to the complex dynamics in the V2V system, RWC
is far from optimal. In [50], we have formulated the Waiting Time Control determination problem as a
reinforcement learning problem and proposed a Q-learning-based Waiting Time Control (QWC) solution.
We conducted offline experiments in the Grid5000 [83] testbed and validated our results through a 14-day
A/B testing in the wild. Our findings showed that QWC improves overall streaming Quality-of-Experience
(QoE) in rebuffering (-29% fewer events), video quality (+17% higher), and buffer length (+5% longer),
with a slightly improved V2V ratio (+5% more).

This is a collaboration with Zhejiayu Ma and Sofiane Rouibia from EasyBroadcast and Guillaume

Urvoy-Keller (I3S).

Project COATI

11

8.1.3 Learning-based packet routing

Participants:

Tiago da Silva Barros.

PRISMA: A Packet Routing Simulator for Multi-Agent Reinforcement Learning In [35], we present
PRISMA-v2, a new release of PRISMA [80, 81], a Packet Routing Simulator for Multi-Agent Reinforcement
Learning. PRISMA-v2 brings a new set of features. First, it allows simulating overlay network topologies,
by integrating virtual links. Second, this release offers the possibility to simulate control packets, which
allows to better evaluate the overhead of the network protocol. Last, we integrate the modules along with
the core (ns-3) to a docker container, so that it can be run in any machine or platform. PRISMA-v2 is,
to the best of our knowledge, the first realistic overlay network simulation playground that offers to the
community the possibility to test and evaluate new network protocols.

This work has been done in collaboration with Lucile Sassatelli from SIS team of I3S laboratory.

8.1.4 Modeling LoRa networks for the IoT

Participants: Christelle Caillouet.

LoRa is a low-power and long range radio communication technology designed for low-power In-
ternet of Things (IoT) devices. These devices are often deployed in remote areas where the end-to-end
connectivity provided through one or more gateways may be limited. In collaboration with Martin Heusse
and Andrzej Duda (Drakkar, LIG, Grenoble), we present a model for frame delivery rates in LoRaWAN
when the gateway is capable of receiving antenna diversity [48]. Based on this model, we investigate the
level of transmission redundancy required to guarantee reliable data reception without overloading the
channel. We then show that receive antenna diversity combined with a well-chosen level of transmission
redundancy guarantees maximum channel utilization while maintaining reliable reception of application
data.

We also explore the capacity limits and the tradeoff between the antagonistic means of enabling
reliable data delivery in a loaded LoRaWAN cell [33]. In fact, channel attenuation and variability call for
robust transmission settings but the associated load increase causes more collisions between frames.
In addition to the physical layer parameters of the LoRa modulation, this work considers the benefits
and tuning of inter-packet Error Correction Codes (ECC), which also trades transmission redundancy
for reliability. We propose a refined Packet Delivery Ratio (PDR) model that improves the ones found in
the literature in that, first, it takes into account the dependency between overcoming ambient noise and
dominating colliding frames; and second, it considers the sum of interference powers when multiple
colliding frames are present, even if the interference preexists. Moreover, the model extends to the case of
a gateway with receiver diversity. In a second step, the model allows to set out the level of redundancy at
which ECC is the most effective without hindering capacity: a coding rate of one third. When this is fixed,
it allows to define the transmission parameters allocation within a cell and thus the size of the cell.

8.1.5 Aerial networks for sensor coverage and energy harvesting

Participants: Christelle Caillouet, Igor Dias da Silva.

The problem of the lifetime of connected objects, in most use cases (Industrial Internet of Things
(IIoT), disaster management, etc.) is an essential element of the proposed solutions. Radio frequency (RF)
harvesting of sensor batteries is an attractive solution, however, it does not scale up if it has to be done by
human operators, and becomes impossible if the objects are located in unreachable places. An innovative
solution consists of using fleets of drones to take care of this regular recharge. In collaboration with

12

Inria Annual Report 2023

Yann Busnel (IMT Nord Europe) [55], we propose a two-stage optimization framework for determining
near-optimal trajectories for unmanned aerial vehicles (UAVs), or drones, in order to rapidly recharge
a ground-based sensor network, thereby increasing its lifetime. The chosen wireless radio-frequency
(RF) charging solution enables multiple sensors to be charged in parallel by a single UAV. However, when
several drones charge the same sensor simultaneously, there is a high energy loss. We therefore optimize
the flight plan of the drone fleet to minimize the time needed to charge all the sensors, while avoiding
this wastage.

8.1.6 Gossiping with interference in radio ring networks

Participants:

Jean-Claude Bermond.

In collaboration with Takako Kodate (Tokyo Woman’s Christian University, Japan) and Joseph Yu (Uni-
versity of the Fraser Valley, B.C., Canada), we tackled in [27] the problem of gossiping with interference
constraint in radio ring networks. Gossiping (or total exchange information) is a protocol where each
node in the network has a message and is expected to distribute its own message to every other node
in the network. The gossiping problem consists in finding the minimum running time (makespan)
of a gossiping protocol and algorithms that attain this makespan. We focus on the case in which the
transmission network is a ring network. We consider synchronous protocols where it takes one unit of
time (step) to transmit a unit-length message. During one step, a node receives at most one message only
through one of its two neighbors. We also suppose that, during one step, a node cannot be both a sender
and a receiver (half duplex model). Moreover communication is subject to interference constraints. We
use a primary node interference model where, if a node receives a message from one of its neighbors, its
other neighbor cannot send at the same time. With these assumptions we completely solve the problem
for ring networks. We first show lower bounds and then present gossiping algorithms that meet these
lower bounds and so are optimal. The number of rounds depends on the congruences of n modulo 12.

8.1.7 A middleware for the experimentation on IoT mobile networks - a decentralized Web backend

Participant:

Luc Hogie (COATI, KAIROS).

Idawi (see Section 7.1.4) is a research software platform for the experimentation of Edge Computing
algorithms, whose the infrastructure network can be represented by a mixed (featuring both directed and
undirected edges) dynamic multi-graph.

The development of Idawi was initially motivated by the need of COATI to deploy scientific applications
in clusters of computers, in order to run large experimentation campaigns of graph algorithms, and it
progressively turned to a research platform for decentralized algorithms/systems.

In order to enable the Idawi middleware interoperability with Web appplications, and in particular
to build a user Web interface for the control of running distributed computations, we introduced into
the middleware a specific service. The role of the service is bridge Web (HTTP/JSON) queries to the
internal messaging system of Idawi. The very decentralized nature of Idawi allowed us to design and
implement a novel architecture for a Web backend that consists of a set of application-specific services
accessible via bridge services available in one or several component of the Idawi system. This enables
the resulting decentralized Web backend to be accessible from anywhere, regardless of the presence of
network obstacles (NATs, firewall), and to natively support redundancy [49].

8.2 Graph algorithms

In the last years, COATI has conducted an intense research effort on the algorithmic aspects of graph
theory. We are mainly interested in designing efficient algorithms for large graphs and in understanding
how structural properties of networks can help for this purpose. In general, we try to find the most

Project COATI

13

efficient algorithms, either exact algorithms or approximations, to solve various problems of graph theory,
often with applications in telecommunication networks. We are involved in many international and
national collaborations with academic and industrial partners.

We mainly focus on four topics: efficient computation of graph parameters, graph decompositions,

combinatorial games in graphs, and distributed computing.

• We use graph theory to model various network problems. We study their complexity with the aim
of identifying the key structural properties of graphs that make these problems hard or easy. We
then search for the most efficient algorithms to solve the problems, sometimes focusing on specific
graph classes from which the problems are polynomial-time solvable. Our algorithms are generally
implemented (e.g., in Sagemath) and tested on real-life networks (e.g., road networks, Twitter,
graph of co-publications from Scopus, etc.).

• Tree-decompositions are the corner-stone of many dynamic programming algorithms for solving
graph problems. Since the complexity of such algorithms generally depends exponentially on
the width (size of the bags) of the decomposition, much work has been devoted to compute
tree-decompositions with small width. We propose different approaches, based on a pursuit-
evasion perspective or on metric aspects of graphs, to compute optimal or approximate tree-
decompositions of graphs.

• One important topic of COATI is the study of combinatorial games in graphs. For instance, we are
strongly involved in the organization of GRASTA dedicated to pursuit-evasion games (and their
relationships with tree-decompositions) and games in graphs (special issues [87, 82], organization
of the 11t h edition of GRASTA in October 2023, etc.). We study combinatorial games for themselves
by determining their complexity but also because they provide nice models for problems arising in
telecommunication networks (e.g., localization games).

• Within the research area of the theory of distributed computing, COATI investigates the recent topics
of computational dynamics on complex networks, namely the study of algorithmically-simple
interaction rules among agents represented by nodes of a complex network. Such systems are of
interest in many scientific areas, ranging from biology to sociology. We contribute to this research
endeavour by focusing on the fundamental coordination problems, in which agents are required to
agree on a configuration that satisfies some condition based on their initial input state.

8.2.1 Complexity of graph problems

Participants:

Jean-Claude Bermond, Michel Cosnard, David Coudert, Thomas Dis-
saux, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta.

Leanness of graphs Let u and v be vertices in a connected graph G = (V, E ). For any integer k such that
0 ≤ k ≤ distG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that distG (u, x) =
k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied
under different names, such as “interval thinness” and “fellow traveler property”. Graphs with leanness
equal to 0, a.k.a. geodetic graphs, also have received special attention in graph theory. The practical
computation of leanness in real-life complex networks has been studied recently [88]. In collaboration
with Samuel Coulomb (ENS Paris) and Guillaume Ducoffe (IRO, Bucharest, Romania), we give in [69] a
finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a
graph G is at most some small value ℓ; and computing the leanness on specific graph classes. We obtain
improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses.

New lower bounds on the cutwidth of graphs Cutwidth is a parameter used in many layout problems.
Determining the cutwidth of a graph is an NP-complete problem, but it is possible to design efficient
branch-and-bound algorithms if good lower bounds are available for cutting branches during exploration.
Knowing how to quickly evaluate good bounds in each node of the search tree is therefore crucial. In [54],

14

Inria Annual Report 2023

we present new lower bounds based on different graph density parameters. We also propose a lower
bound based on the grooming of traffic requests on the path.

Constrained flows in networks The support of a flow x in a network is the subdigraph induced by the
arcs i j for which xi j > 0. In [66], we discuss a number of results on flows in networks in which we put
certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because
they generalize linkage problems for digraphs. For example, deciding whether a network N = (D, s, t , c)
has a maximum flow x such that the maximum out-degree of the support D x of x is at most 2 is NP-
complete as it contains the 2-linkage problem as a very special case. Another problem that is NP-complete
for the same reason is that of deciding the maximum flow we can send from s to t along 2 paths (called a
maximum 2-path-flow) in N . Baier et al. (2005) gave a polynomial algorithm which finds a 2-path-flow
x whose value is at least 2
3 of the value of a optimum 2-path-flow. This is best possible unless P=NP.
They also obtained a 2
p -approximation for the maximum value of a p-path-flow for every p ≥ 2. In [66],
1
we present an algorithm that gets within a factor
H (p) of the optimum solution, where H (p) is the p’th
harmonic number (H (p) ∼ ln(p)). This improves the approximation bound due to Baier et al. when
p ≥ 5. We show that in the case in which the network is acyclic, we can find a maximum p-path-flow in
polynomial time for every p. We determine the complexity of a number of related problems concerning
the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some
sense best possible.

Treelength of series–parallel graphs The length of a tree-decomposition of a graph is the maximum
distance (in the graph) between two vertices of a same bag of the decomposition. The treelength of a
graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for
its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric
dimension of graphs and also, in compact routing in the context of distributed computing. Deciding
whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are
precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up
to a factor less than 3
2 (the best known approximation algorithm for treelength has an approximation
ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs,
except that the treelength of any outerplanar graph is equal to the third of the size of a largest isometric
cycle. This work initiates the study of treelength in planar graphs by considering the next natural subclass
of planar graphs, namely the one of series-parallel graphs.

We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking
two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not
trivial. Then, we show that treelength can be approximated up to a factor 3
2 in series-parallel graphs. Our
main result is a quadratic-time algorithm for deciding whether a series-parallel graph has treelength at
most 2. Our latter result relies on a characterization of series-parallel graphs with treelength 2 in terms of
an infinite family of forbidden isometric subgraphs [31].

8.2.2 Combinatorial games in graphs

Participants:

Julien Bensmail,
Frédéric Havet, Nicolas Nisse.

Jean-Claude Bermond, Michel Cosnard,

Recontamination helps a lot to hunt a rabbit The Hunters and Rabbit game is played on a graph G in
which the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown
vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins
if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number
h(G) of a graph G is the minimum integer k such that the Hunter player has a winning strategy (i.e.,
allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several
graph classes, in particular in bipartite graphs (grids, trees, hypercubes, etc.), but the computational
complexity of computing h(G) remains open in general graphs and even in more restricted graph classes

Project COATI

15

such as trees. To progress further in this study, we propose in [73, 44] a notion of monotonicity (a well-
studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the
Hunters and Rabbit game imposing that, roughly, a vertex that has already been shot "must not host the
rabbit anymore". This allows us to obtain new results in various graph classes. More precisely, let the
monotone hunter number mh(G) of a graph G be the minimum integer k such that the Hunter player has
a monotone winning strategy. We show that pw(G) ≤ mh(G) ≤ pw(G) + 1 for any graph G with pathwidth
pw(G), which implies that computing mh(G), or even approximating mh(G) up to an additive constant,
is NP-hard. Then, we show that mh(G) can be computed in polynomial time in split graphs, interval
graphs, cographs and trees. These results go through structural characterizations which allow us to relate
the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows
us to specify the hunter number or to show that there may be an arbitrary gap between h and mh, i.e.,
that monotonicity does not help. In particular, we show that, for every k ≥ 3, there exists a tree T with
h(T ) = 2 and mh(T ) = k. We conclude by proving that computing h (resp., mh) is FPT parameterized by
the minimum size of a vertex cover.

Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation Let r ≥ 1 be any
non negative integer and let G = (V, E ) be any undirected graph in which a subset D ⊆ V of vertices are
initially infected. In [18], we consider the process in which, at every step, each non-infected vertex with
at least r infected neighbours becomes infected and an infected vertex never becomes non-infected.
The problem consists in determining the minimum size sr (G) of an initially infected vertices set D that
eventually infects the whole graph G. This problem is closely related to cellular automata, to percolation
problems and to the Game of Life studied by John Conway. Note that s1(G) = 1 for any connected graph
G. The case when G is the n × n grid, Gn×n, and r = 2 is well known and appears in many puzzle books, in
particular due to the elegant proof that shows that s2(Gn×n) = n for all n ∈ N. We study the cases of square
grids, Gn×n, and tori, Tn×n, when r ∈ {3, 4}. We show that s3(Gn×n) = ⌈ n2+2n+4
⌉ for every n even and that
⌈ n2+2n
⌉ + 1 for any n odd. When n is odd, we show that both bounds are reached,
3
3
namely s3(Gn×n) = ⌈ n2+2n
⌉ if n ≡ 5 (mod 6) or n = 2p − 1 for any p ∈ N∗
⌉ + 1 if
n ∈ {9, 13}. Finally, for all n ∈ N, we give the exact expression of s3(Tn×n).

, and s3(Gn×n) = ⌈ n2+2n

⌉ ≤ s3(Gn×n) ≤ ⌈ n2+2n

3

3

3

The Maker-Breaker largest connected subgraph game We consider the following 2-player combin-
atorial game taking a graph G and an integer k ∈ N as inputs. At every turn, first Alice colours red an
uncoloured vertex of G and then Bob colours an uncoloured vertex blue. Once all vertices have been
coloured, Alice wins if there exists a red component of order at least k and Bob wins otherwise. This
game is a Maker-Breaker version of the Largest Connected Subgraph Game introduced in [86]. We are
interested in computing cg (G) which is the maximum k such that Alice wins in G whatever Bob does.

(cid:109)

We first show that computing cg is PSPACE-complete1 in bipartite graphs with diameter 4, in split
graphs and in planar graphs. Then, we focus on A-perfect graphs, namely, graphs for which cg (G) =
(cid:108) |V (G)|
, i.e., the maximum possible value. While there exist arbitrary large A-perfect d -regular graphs for
2
any d ≥ 4, we prove that, surprisingly, no cubic graph with order at least 133 is A-perfect. Moreover, we
exhibit sufficient conditions in terms of degree or number of edges for a graph to be A-perfect.

Finally, graph classes where cg is expected to be computable in polynomial time are considered. We
show that cg (G) can be computed in polynomial time when G is a P4-sparse graphs (including cographs).
We conclude with many open questions. In particular, natural graph classes such that trees and grid-like
graphs seem to be more difficult to deal with. We only give partial results, namely, in caterpillars and in
the case of some grid-like graphs [23].

Complexity of Maker-Breaker games on edge sets of graphs
In [23], we initiate the study of the al-
gorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly
consider the perfect matching game and the H -game. Maker wins if she claims the edges of a perfect
matching in the first, and a copy of a fixed graph H in the second. We prove that deciding who wins the
perfect matching game and the H -game is PSPACE-complete, even for the latter in small-diameter graphs

1A decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length
(polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time.

16

Inria Annual Report 2023

if H is a tree. Toward finding the smallest graph H for which the H -game is PSPACE-complete, we also
prove that such an H of order 51 and size 57 exists.

We then give several positive results for the H -game. As the H -game is already PSPACE-complete
when H is a tree, we mainly consider the case where H belongs to a subclass of trees. In particular, we
design two linear-time algorithms, both based on structural characterizations, to decide the winners
of the P4-game in general graphs and the K1,ℓ-game in trees. Then, we prove that the K1,ℓ-game in any
graph, and the H -game in trees are both FPT parameterized by the length of the game, notably adding to
the short list of games with this property, which is of independent interest.

Another natural direction to take is to consider the H -game when H is a cycle. While we were unable
to resolve this case, we prove that the related arboricity-k game is polynomial-time solvable. In particular,
when k = 2, Maker wins this game if she claims the edges of any cycle.

8.2.3 Algorithms for social networks

Participants:

Frédéric Giroire, Nicolas Nisse, Stéphane Pérennes.

A random growth model with any real or theoretical degree distribution The degree distributions
of complex networks are usually considered to follow a power law distribution. However, it is not the
case for a large number of them. We thus propose a new model able to build random growing networks
with (almost) any wanted degree distribution [32]. The degree distribution can either be theoretical
or extracted from a real-world network. The main idea is to invert the recurrence equation commonly
used to compute the degree distribution in order to find a convenient attachment function for node
connections-commonly chosen as linear. We compute this attachment function for some classical
distributions, as the power-law, the broken power-law, and the geometric distributions. We also use
the model on an undirected version of the Twitter network, for which the degree distribution has an
unusual shape. We finally show that the divergence of chosen attachment functions is directly linked
to the heavy-tailed property of the obtained degree distributions. This is a collaboration with Thibaud
Trolliet (TSE).

Preferential attachment hypergraph with vertex deactivation In the field of complex networks, hy-
pergraph models have so far received significantly less attention than graphs. However, many real-life
networks feature multiary relations (coauthorship, protein reactions) may therefore be better modeled by
hypergraphs. Also, a recent study by Broido and Clauset suggests that a power-law degree distribution
is not as ubiquitous in the natural systems as it was thought so far. They experimentally confirm that a
majority of networks (56% of around 1000 networks that undergone the test) favor a powerlaw with an
exponential cutoff over other distributions. We address the two above observations by introducing a pref-
erential attachment hypergraph model that allows for vertex deactivations. The phenomenon of vertex
deactivations is rare in existing theoretical models and omnipresent in real-life scenarios (social network
accounts that are not maintained forever, collaboration networks in which people retire, technological
networks in which devices break down). We prove that the degree distribution of the proposed model
follows a power-law with an exponential cutoff. We also check experimentally that a Scopus collaboration
network has the same characteristic. We believe that our model will predict well the behavior of systems
from a variety of domains [46]. In collaboration with Małgorzata Sulkowska (Wrocław University of
Science and Technology).

8.2.4 Algorithm engineering

Participants: David Coudert, Nicolas Nisse.

Algorithm Engineering is concerned with the design, analysis, implementation, tuning, and experi-
mental evaluation of computer programs for solving algorithmic problems. It provides methodologies

Project COATI

17

and tools for developing and engineering efficient algorithmic codes and aims at integrating and reinfor-
cing traditional theoretical approaches for the design and analysis of algorithms and data structures. This
approach is particularly suited when formal analysis pessimistically suggests bounds which are unlikely
to appear on inputs of practical interest.

Algorithms for the k shortest simple paths problem The k shortest simple path problem (kSSP)
asks to compute a set of top-k shortest simple paths from a vertex s to a vertex t in a digraph. Yen
proposed in 1971 [89] the first algorithm with the best known theoretical complexity of O(kn(m +
n log n)) for a digraph with n vertices and m arcs. Since then, the problem has been widely studied from
an algorithm engineering perspective, and impressive improvements have been achieved. The most
noticeable proposals are the node-classification (NC) algorithm (Feng, 2014) and the sidetracks-based
(SB) algorithm (Kurz, Mutzel, 2016). The latest offers the best running time at the price of a significant
working memory. We proposed a new algorithm, the postponed node classification (PNC) algorithm, that
combines the best of NC (low memory consumption) and SB (fast computation) [16].

8.3 Graph and digraph theory

COATI works mainly on two important topics in graph theory, namely graph coloring and directed graphs
(digraphs), as well as on the interaction between the two.

We are putting an effort on better understanding directed graphs and partitioning problems, and in
particular coloring problems. We also try to better understand the many relations between orientations
and colorings. We study various substructures and partitions in (di)graphs. For each of them, we aim at
giving sufficient conditions that guarantee their existence and at determining the complexity of finding it.

8.3.1 Partitioning and labelling graphs and digraphs

Participants:

Julien Bensmail, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta,
Clément Rambaud.

Distinguishing labelling problems and the 1-2-3 Conjecture In distinguishing labelling problems,
the general goal is, given a graph, to label some of its elements so that some pairs of elements can be
distinguished accordingly to some parameter computed from the labelling. Note that this description
involves many parameters that can be played with, such as the set of elements to be labelled, the set of
labels to be assigned, the set of elements to be distinguished, and the distinguishing parameter computed
from the labelling. A notable example is the so-called 1-2-3 Conjecture, which asks whether almost all
graphs can have their edges labelled with 1,2,3 so that every two adjacent vertices are distinguished
accordingly to their sums of incident labels.

We have recently obtained a number of results, related both to the 1-2-3 Conjecture and related
problems. These results stand both as notable progress towards some open questions, and as new
problems of independent interest.

• In collaboration with H. Hocquard, D. Lajou and É. Sopena (LaBRI, Université de Bordeaux), we
have investigated the multiplicative version of the 1-2-3 Conjecture. In that variant of the 1-2-3
Conjecture, adjacent vertices are required to be distinguished, through a labelling, by their products
of incident labels. The main conjecture here, is due to Skowronek-Kaziów, who conjectured in 2012
that labels 1, 2, 3 should suffice for (nearly) all graphs. The best result towards that question, proved
back in 2012, was that labels 1, 2, 3, 4 suffice in general. In [25], building upon earlier studies, we
have come up with a full proof of the Multiplicative 1-2-3 Conjecture. This stands as one of the
most important results of the field, in the recent years.

• In some of our works, we also improved previous known results on other variants of the 1-2-3
Conjecture. In particular, in [26], with H. Hocquard and P.-M. Marcille (LaBRI, Université de
Bordeaux), we provided more evidence that a degenerate variant (in which only labels 1 and 2 can
be assigned, but the resulting sums are only required to induce forests) might hold true. In [38],

18

Inria Annual Report 2023

with the same authors we proved that a weaker form of the 1-2-3 Conjecture (involving coloured
labels) holds in graphs defined in terms of particular forbidden structures, graphs for which the
1-2-3 Conjecture was not known to hold.

• In a few works, we have also investigated a few aspects of the original 1-2-3 Conjecture. For instance,
in [19], we studied the consequences of requiring, through a proper labelling, that all resulting
sums appear in an equitable way (i.e., about the same number of times); while, in [20], we studied
proper labellings assigning label 1 to the most edges possible, which concern relates to some of the
original practical applications behind the 1-2-3 Conjecture.

• In [65, 64, 63], through the supervision of several students, we also introduced and investigated a
few new variants of the 1-2-3 Conjecture, and studied how they connect to the original problem. In
particular, through these three aforementioned works, we considered variants in directed graphs
and 2-edge-coloured graphs.

• Last, in [24], we also established formally the hardness of building optimal so-called AVD edge-
colourings, which notion has received a lot of attention in literature. In particular, we proved that
determining the associated chromatic parameter is NP-hard, which is of prime importance given
how investigated this notion has been.

Arbitrarily partitionable graphs
In [60, 21, 62], with O. Baudon and M. Boivin (LaBRI, Université de
Bordeaux), we have investigated several properties of arbitrarily partitionable graphs (AP graphs for
short), which are those graphs that can be vertex-partitioned into arbitrarily many connected subgraphs
with arbitrary order. While AP graphs form a superclass of Hamiltonian graphs, we proved results showing
both the similarities and the discrepancies between AP graphs and Hamiltonian graphs. In particular, we
proved that a few sufficient conditions for Hamiltonicity can be weakened to APness, while we proved
some do not, sometimes in a strong sense. We also investigated AP graphs that are minimal w.r.t. the AP
property, giving, among others, results on their order, their minimum degree, their maximum degree, and
their clique number.

Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs Let K be a complete graph of
order n. For d ∈ (0, 1), let c be a ±1-edge labeling of K such that there are d (cid:161)n
(cid:162) edges with label +1, and let
2
G be a spanning subgraph of K of maximum degree at most ∆ and with m(G) edges. In [28], we prove the
is at least
existence of an isomorphic copy G
(cid:162)(cid:180)
(cid:179)
d + fd
m(G) for some positive fd depending only on d , that is, this number visibly exceeds its
2∆+1
expected value d · m(G) when considering a uniformly random copy of G in K . For d = 1
2 , and ∆ ≤ 2, we
present more detailed results.

of G in K such that the number of edges with label +1 in G

− O (cid:161) 1
n

′

′

In [22] with T. Das, S. Nandi and S. Sen (from various institutes in India),
Colouring decorated graphs
and D. Lajou (LaBRI, Université de Bordeaux), we have pursued the study of the usual chromatic theory
of graphs to the realm of decorated graphs. Namely, we have considered the analogue of the chromatic
number for pushable graphs (oriented graphs in which vertices can be pushed at will, i.e., have the
direction of their incident arcs reversed), in particular in the context of various types of grids. The bounds
we established apart, we also summarized the state of research of the field to date, and raised new results
and questions, to motivate researchers to undertake further studies on the topic.

Colouring digraphs The dichromatic number ⃗χ(D) of a digraph D is the minimum number of colours
needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph.

In [67], we give both lower and upper bounds on the dichromatic number of super-orientations of
chordal graphs (i.e. digraphs for which the underlying graph is chordal). When restricted to oriented
graphs, we show that the easy bound on the dichromatic number of such digraphs is best possible even
for orientations of interval graphs. We then show, for every digraph D in this class, that its dichromatic
number is bounded above by 1
d · ω) with d the maximum average degree of the symmetric part
2
of D and ω the clique number of D. Finally, we show that if the symmetric part of D contains no C4 as a

ω + O(

(cid:112)

Project COATI

19

subgraph, then the dichromatic number is bounded above by (cid:167) ω+3
2
possible upper bound by constructing digraphs in this class with dichromatic number (cid:165) ω+3
2

(cid:168). We justify that this is almost best

(cid:166).

+

−

−

+

(v), d

(v), d

←→
Kr and

We define ∆max(D) as the maximum of {max(d

(v)) | v ∈ V } and ∆min(D) as the maximum of
(v)) | v ∈ V }. It is known that the dichromatic number of D is at most ∆min(D) + 1. In [51]
{min(d
and [34], we prove that every digraph D which has dichromatic number exactly ∆min(D) + 1 must contain
←→
Ks for some r, s such that r + s = ∆min(D) + 1. In particular, every oriented
the directed join of
graph ⃗G with ∆min(⃗G) ≥ 2 has dichromatic number at most ∆min(⃗G).

Let ⃗G be an oriented graph of order n such that ∆min(⃗G) ≤ 1. Given two 2-dicolourings of ⃗G, we show
that we can transform one into the other in at most n steps, by recolouring one vertex at each step while
maintaining a dicolouring at any step. Furthermore, we prove that, for every oriented graph ⃗G on n
vertices, the distance between two k-dicolourings is at most 2∆min(⃗G)n when k ≥ ∆min(⃗G) + 1.

We then extend a theorem of Feghali, Johnson and Paulusma to digraphs. We prove that, for every
digraph D with ∆max(D) = ∆ ≥ 3 and every k ≥ ∆ + 1, the k-dicolouring graph of D consists of isolated
vertices and at most one further component that has diameter at most c∆n2, where c∆ = O(∆2) is a
constant depending only on ∆.

A digraph D is k-dicritical if ⃗χ(D) = k and each proper subdigraph H of D satisfies ⃗χ(H ) < k. For
integers k and n, we define dk (n) (respectively ok (n), gk (n)) as the minimum number of arcs possible in
a k-dicritical digraph (respectively oriented graph, bidirected graph). Kostochka and Stiebitz have shown
that d4(n) ≥ 10
3 . They also conjectured that dk (n) = gk (n) and that there is a constant c such that
ok (n) ≥ cdk (n) for k ≥ 3 and n large enough. This conjecture is known to be true for k = 3 (Aboulker et
al.).

3 n − 4

In [76], we prove the first conjecture when k ≤ n ≤ 2k − 1. In this particular case, we also characterize
the k-dicritical digraphs with exactly dk (n) arcs. This generalizes a result about critical graphs obtained
in 1963 by Gallai. In [47, 59], we prove that every 4-dicritical oriented graph on n vertices has at least
( 10
51 )n − 1 arcs, showing the second conjecture for k = 4. We also characterize exactly the 4-dicritical
3
digraphs on n vertices with exactly 10

+ 1

3 n − 4

3 arcs.

Digraph redicolouring In this work, we generalize several results on graph recolouring to digraphs.

Given two k-dicolourings of a digraph D, we prove that it is PSPACE-complete to decide whether we
can transform one into the other by recolouring one vertex at each step while maintaining a dicolouring
at any step even for k = 2 and for digraphs with maximum degree 5 or oriented planar graphs with
maximum degree 6.

A digraph is said to be k-mixing if there exists a transformation between any pair of k-dicolourings.
min(D) + 2, generalizing a result due to Dyer et al.
avg(⃗G) + 1.
avg denote the min-degeneracy, the max-degeneracy, and the average-degeneracy

We show that every digraph D is k-mixing for all k ≥ δ∗
We also prove that every oriented graph ⃗G is k-mixing for all k ≥ δ∗
Here δ∗
min, δ∗
respectively.

max(⃗G) + 1 and for all k ≥ δ∗

max, and δ∗

We pose as a conjecture that, for every digraph D, the dicolouring graph of D on k ≥ δ∗

min(D) + 2
colours has diameter at most O(|V (D)|2). This is the analogue of Cereceda’s conjecture for digraphs. We
generalize to digraphs two results supporting Cereceda’s conjecture. We first prove that the dicolouring
graph of any digraph D on k ≥ 2δ∗
min(D) + 2 colours has linear diameter, extending a result from Bousquet
and Perarnau. We also prove that the analogue of Cereceda’s conjecture is true when k ≥ 3
min(D) + 1),
which generalizes a result from Bousquet and Heinrich.

2 (δ∗

Restricted to the special case of oriented graphs, we prove that the dicolouring graph of any subcubic
oriented graph on k ≥ 2 colours is connected and has diameter at most 2n. We conjecture that every
non 2-mixing oriented graph has maximum average degree at least 4, and we provide some support for
this conjecture by proving it on the special case of 2-freezable oriented graphs. More generally, we show
that every k-freezable oriented graph on n vertices must contain at least kn + k(k − 2) arcs, and we give a
family of k-freezable oriented graphs that reach this bound. In the general case, we prove as a partial
result that every non 2-mixing oriented graph has maximum average degree at least 7

2 [29, 68].

8.3.2 Structural digraph theory

20

Inria Annual Report 2023

Participants:

Julien Bensmail, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta,
Clément Rambaud.

One of our goals is to establish structural results on digraphs that can be used to design efficient
algorithms. In particular, we are looking for substructures with certain properties or ways to represent or
approximate efficiently the digraphs.

Semi-proper orientations of dense graphs An orientation D of a graph G is a digraph obtained from G
by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation D of a
graph G is a k-orientation if the in-degree of each vertex in D is at most k. An orientation D of G is proper
if any two adjacent vertices have different in-degrees in D. The proper orientation number of a graph G,
denoted by

−→χ (G), is the minimum k such that G has a proper k-orientation.

A weighted orientation of a graph G is a pair (D, w), where D is an orientation of G and w is an
arc-weighting A(D) → N \ {0}. A semi-proper orientation of G is a weighted orientation (D, w) of G such
that for every two adjacent vertices u and v in G, we have that S(D,w)(v) ̸= S(D,w)(u), where S(D,w)(v)
is the sum of the weights of the arcs in (D, w) with head v. For a positive integer k, a semi-proper
k-orientation (D, w) of a graph G is a semi-proper orientation of G such that maxv∈V (G) S(D,w)(v) ≤ k.
−→χs (G), is the least k such that G has a
The semi-proper orientation number of a graph G, denoted by
semi-proper k-orientation.
−→χs (G) ∈ {ω(G) − 1, ω(G)} for every split graph G, and that, given a split graph G,
We first prove that
−→χs (G) = ω(G) − 1 is an N P -complete problem. We also show that, for every k, there
deciding whether
−→χ (H ) = 2k − 2. In the
−→χ (G) ≤ k and
exists a (chordal) graph G and a split subgraph H of G such that
p
sequel, we show that, for every n ≥ p(p + 1),
n is the p t h power of the path on n
−→χ (G) ≤ 3 for any
vertices. We investigate further unit interval graphs with no big clique: we show that
unit interval graph G with ω(G) = 3, and present a complete characterization of unit interval graphs with
−→χs (G) = ω(G) can be solved in polynomial time in
−→χ (G) = ω(G) = 3. Then, we show that deciding whether
−→χs (G) is FPT when parameterized by the
the class of co-bipartite graphs. Finally, we prove that computing
−→χs (G),
minimum size of a vertex cover in G or by the treewidth of G. We also prove that not only computing
−→χ (G), admits a polynomial kernel when parameterized by the neighbourhood diversity plus the
but also
O (k2) and O (2k k2), in chordal graphs and split
value of the solution. These results imply kernels of size 4
−→χs (G) ≤ k parameterized by k. We also present
graphs, respectively, for the problem of deciding whether
−→χs (G) parameterized by the value of the solution when
exponential kernels for computing both
−→χs (G) does not admit a polynomial kernel
G is a cograph. On the other hand, we show that computing
parameterized by the value of the solution when G is a chordal graph, unless N P ⊆ coN P /pol y [36].
Collaboration within the Inria EA CANOE and the CAPES-Cofecub project with the PARGO team from
UFC, Fortaleza, Brazil.

2 p(cid:168), where P

−→χ (G) and

n ) = (cid:167) 3

−→χs (P

p

Deciding the Erd˝os-Pósa property in 3-connected digraphs A (di)graph H has the Erd˝os-Pósa (EP)
property for (butterfly) minors if there exists a function f : N → N such that, for any k ∈ N and any
(di)graph G, either G contains at least k pairwise vertex disjoint copies of H as (butterfly) minor, or
there exists a subset T of at most f (k) vertices such that H is not a (butterfly) minor of G − T . It is a well
known result of Robertson and Seymour that an undirected graph has the EP property if and only if it is
planar. This result was transposed to digraphs by Amiri, Kawarabayashi, Kreutzer and Wollan, who proved
that a strong digraph has the EP property for butterfly minors if, and only if, it is a butterfly minor of a
cylindrical grid. Contrary to the undirected case in which a graph is planar if, and only if, it is the minor
of some grid, not all planar digraphs are butterfly minors of a cylindrical grid. In [37], we characterize the
planar digraphs that have a butterfly model in a cylindrical grid. In particular, this leads to a linear-time
algorithm that decides whether a weakly 3-connected strong digraph has the EP property. Collaboration
within the Inria EA CANOE and the CAPES-Cofecub project with the PARGO team from UFC, Fortaleza,
Brazil.

Inversions in digraphs The inversion of a set X of vertices in a digraph D consists of reversing the
′
direction of all arcs of D〈X 〉. We study sinv
k (D) (resp. sinvk (D)) which is the minimum number of inver-

Project COATI

21

′
sions needed to transform D into a k-arc-strong (resp. k-strong) digraph and sinv
D is a 2k-edge-connected digraph of order n}. In [45], we show :

k (n) = max{sinv

′

k (D) |

(i) 1

2 log(n − k + 1) ≤ sinv

k (n) ≤ log n + 4k − 3 ;

′

(ii) for any fixed positive integers k and t , deciding whether a given oriented graph ⃗G satisfies sinv
′

k (⃗G) ≤

t (resp. sinvk (⃗G) ≤ t ) is NP-complete ;

′
(iii) if T is a tournament of order at least 2k +1, then sinv

k (T ) ≤ sinvk (T ) ≤ 2k, and sinv

k (T ) ≤ 4

3 k +o(k);

′

(iv) 1

2 log(2k + 1) ≤ sinv

k (T ) ≤ sinvk (T ) for some tournament T of order 2k + 1;

′

′
(v) if T is a tournament of order at least 19k − 2 (resp. 11k − 2), then sinv

k (T ) ≤ sinvk (T ) ≤ 1 (resp.

sinvk (T ) ≤ 3);

′
(vi) for every ϵ > 0, there exists C such that sinv

k (T ) ≤ sinvk (T ) ≤ C for every tournament T on at least

2k + 1 + ϵk vertices.

From branchings to flows: a study of an Edmonds’ like property to arc-disjoint branching flows An
s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow that reaches every
vertex in V(D) from s while loosing exactly one unit of flow in each vertex other than s. Bang-Jensen and
Bessy [84] showed that, when every arc has capacity n − 1, a network N admits k arc-disjoint s-branching
flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by
Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every
set X ⊆ V (D) \ s is at least k also characterizes the existence of k arc-disjoint s-branching flows in those
networks, suggesting that the larger the capacities are, the closer an s-branching flow is from simply being
an s-branching. This observation is further implied by results by Bang-Jensen et al. [85] showing that
there is a polynomial algorithm to find the flows (if they exist) when every arc has capacity n − c, for every
fixed c ≥ 1, and that such an algorithm is unlikely to exist for most other choices of the capacities. In [30],
we investigate how a property that is a natural extension of the characterization by Edmonds’ relates to
the existence of k arc-disjoint s-branching flows in networks. Although this property is always necessary
for the existence of the flows, we show that it is not always sufficient and that it is hard to decide if the
desired flows exist even if we know beforehand that the network satisfies it. On the positive side, we show
that it guarantees the existence of the desired flows in some particular cases depending on the choice of
the capacity function or on the structure of the underlying graph of D, for example. We remark that, in
those positive cases, polynomial time algorithms to find the flows can be extracted from the constructive
proofs. Collaboration within the Inria EA CANOE and the CAPES-Cofecub project with the PARGO team
from UFC, Fortaleza, Brazil.

Redicolouring digraphs: directed treewidth and cycle-degeneracy Given a digraph D = (V, A) on n
vertices and a vertex v ∈ V , the cycle-degree of v is the minimum size of a set S ⊆ V (D) \ {v} intersecting
every directed cycle of D containing v. From this definition of cycle-degree, we define the c-degeneracy
(or cycle-degeneracy) of D, which we denote by δ∗
c (D). It appears to be a nice generalization of the
undirected degeneracy. For instance, the dichromatic number ⃗χ(D) of D is bounded above by δ∗
c (D) + 1,
where ⃗χ(D) is the minimum integer k such that D admits a k-dicolouring, i.e., a partition of its vertices
into k acyclic subdigraphs.

In [75], using this new definition of cycle-degeneracy, we extend several evidences for Cereceda’s
conjecture to digraphs. The k-dicolouring graph of D, denoted by Dk (D), is the undirected graph whose
vertices are the k-dicolourings of D and in which two k-dicolourings are adjacent if they differ on the
colour of exactly one vertex. This is a generalization of the k-colouring graph of an undirected graph G,
in which the vertices are the proper k-colourings of G.
We show that Dk (D) has diameter at most Oδ∗

c (D) + 1)n)
when k is at least δ∗
c (D) + 1)). This improves known results
on digraph redicolouring (Bousquet et al.). Next, we extend a result due to Feghali to digraphs, showing
that Dd +1(D) has diameter at most Od ,ϵ(n(log n)d −1) when D has maximum average cycle-degree at most
d − ϵ.

δ∗
c (D)+1) (respectively O(n2) and (δ∗

c (D)(n
c (D) + 1) and 2(δ∗

c (D) + 2 (respectively 3

2 (δ∗

22

Inria Annual Report 2023

We then show that two proofs of Bonamy and Bousquet for undirected graphs can be extended to
digraphs. The first one uses the digrundy number of a digraph ⃗χg (D), which is the worst number of
colours used in a greedy dicolouring. If k ≥ ⃗χg (D)+1, we show that Dk (D) has diameter at most 4·⃗χ(D)·n.
The second one uses the D -width of a digraph, denoted by D w(D), which is a generalization of the
treewidth to digraphs. If k ≥ D w(D) + 2, we show that Dk (D) has diameter at most 2(n2 + n).

Finally, we give a general theorem which makes a connection between the recolourability of a digraph
D and the recolourability of its underlying graph UG(D). Assume that G is a class of undirected graphs,
closed under edge-deletion and with bounded chromatic number, and let k ≥ χ(G ) (i.e., k ≥ χ(G) for
every G ∈ G ) be such that, for every n-vertex graph G ∈ G , the diameter of the k-colouring graph of G is
bounded by f (n) for some function f . We show that, for every n-vertex digraph D such that UG(D) ∈ G ,
the diameter of Dk (D) is bounded by 2 f (n). For instance, this result directly extends a number of results
on planar graph recolouring to planar digraph redicolouring. In collaboration with Ignasi Sau (CNRS,
LIRMM).

8.3.3 Metric dimension in oriented graphs

The (directed) metric dimension of a digraph D, denoted by
vertices such that every two vertices of D are distinguished via their distances from the vertices in S.

−−→
MD(D), is the size of a smallest subset S of

In [17], we investigate the graph parameters BOMD(G) and WOMD(G) which are respectively the
smallest and largest metric dimension over all orientations of G. We show that those parameters are
related to several classical notions of graph theory and investigate the complexity of determining those
parameters. We show that BOMD(G) = 1 if and only if G is hypotraceable (that is has a path spanning
all vertices but one), and deduce that deciding whether BOMD(G) ≤ k is NP-complete for every positive
integer k. We also show that WOMD(G) ≥ α(G) − 1, where α(G) is the stability number of G. We then
deduce that for every fixed positive integer k, we can decide in polynomial time whether WOMD(G) ≤ k.
The most significant results deal with oriented forests. We provide a linear-time algorithm to compute
the metric dimension of an oriented forest and a linear-time algorithm that, given a forest F , computes an
) = BOMD(F )) and an orientation
orientation D
D

with largest metric dimension (i.e. such that
Collaboration within the Inria EA CANOE and the CAPES-Cofecub project with the PARGO team from

−−→
MD(D
) = WOMD(F )).

with smallest metric dimension (i.e. such that

−−→
MD(D

+

−

+

−

UFC, Fortaleza, Brazil.

8.4 Machine learning theory and algorithms

Participants:

Arthur Carvalho da Cunha,
Emanuele Natale, Aurora Rossi, Chuan Xu.

Ilias Driouich, Frédéric Giroire,

In the last years, COATI has started investigating machine-learning-based methods to enhance algorithms
or solve optimization problems in networks (see e.g., Sections 8.1.2 and 8.1.3). It also investigates how to
use tools from graph theory, algorithmic and combinatorics to improve machine-learning tools. We here
present our last results in this direction.

New results on the Random Subset Sum problem and the Strong Lottery Ticket Hypothesis The
Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialized neural networks likely contain
subnetworks that perform well without any training. Although unstructured pruning has been extensively
studied in this context, its structured counterpart, which can deliver significant computational and
memory efficiency gains, has been largely unexplored. One of the main reasons for this gap is the
limitations of the underlying mathematical tools used in formal analyses of the SLTH. In [39], we overcome
these limitations: we leverage recent advances in the multidimensional generalization of the Random
Subset-Sum Problem and obtain a variant that admits the stochastic dependencies that arise when
addressing structured pruning in the SLTH. We apply this result to prove, for a wide class of random
Convolutional Neural Networks, the existence of structured subnetworks that can approximate any
sufficiently smaller network. This result provides the first sub-exponential bound around the SLTH for

Project COATI

23

structured pruning, opening up new avenues for further research on the hypothesis and contributing
to the understanding of the role of over-parameterization in deep learning. Furthermore, in [42], we
present an alternative proof for the classical result on the Random Subset Sum problem, which has been
leveraged in previous proofs of the SLTH. Our new result offer a more direct approach and make use of
more elementary tools.

A GPU implementation of the FlyHash approximate search method FlyHash is a locality-sensitive
hashing algorithm inspired by the nervous system of the Drosophila fly. It has demonstrated to be
particularly effective for similarity search, especially in the federated context where multiple players
collaborate to solve a statistical learning task. FlyHash mainly relies on a process called winner-take-all,
which is used to binarize information. However, the implementation of this process is a major challenge
and limits the algorithm’s usage in processing large data streams. In [41, 72], we propose a simple
algorithm to make the winner-take-all operation efficient on GPUs. We create a FlyHash adaptation
suitable for the CUDA architecture. We assess the speed of this version experimentally and present a
comparison with the CPU version of FlyHash.

Neural network information leakage through hidden learning In [40], we investigate the problem of
making an artificial neural network perform hidden computations whose result can be easily retrieved
from the network’s output. In particular, we consider the following scenario. A user is provided a neural
network for a classification task by a third party. The user’s input to the network contains sensitive
information and the third party can only observe the output of the network. In this work, we provide a
simple and efficient training procedure, which we call hidden learning, that produces two networks: (i)
one that solves the original classification task with performance near to state of the art; (ii) a second one
that takes as input the output of the first, retrieving sensitive information to solve a second classification
task with good accuracy. Our result might expose important issues from an information security point of
view, as for the use of artificial neural networks in sensible applications.

An open-source framework written in Julia for integrated global assessment modeling Trying to
predict the evolution of human society in terms of its fundamental aspects is both a delicate and urgent
issue for science. Over the years, a number of models have been developed to help in this respect. In [56,
70], we present WorldDynamics.jl, an open-source framework that includes the software presented in
Section 7.1.3, with the aim of enabling scientists to easily use and adapt different integrated assessment
models for sustainable development. The library has been developed using the Julia programming
language and incorporates different famous integrated assessment models. The implementation provided
can directly benefit from a wide range of tools already available in the Julia language ecosystem, including
the JuMP modeling language for performing mathematical optimization on aspects of the models.

8.5 Collaborations with other fields

One important objective of COATI is to use its expertise on graph algorithms and Operations Research to
address problems in other scientific domains (transport, bio-informatics, e-health, ed-tech, etc.). During
the last years, we have initiated several collaborations with academic and industrial partners in this direc-
tion. In this section, we present the last results we have obtained in the context of these collaborations. In
addition, some results motivated by transportation networks are presented in Section 8.2.4.

8.5.1 Analysis of temporal brain networks

Participants:

Emanuele Natale, Aurora Rossi.

In collaboration with Samuel Deslauriers-Gauthier (CRONOS) we investigated the properties of temporal
brain networks extracted from functional Magnetic Resonance Imaging (fMRI) data from the WU-Minn
Human Connectome Project (HCP). We first created and published [79] the dataset that collects the
networks (see Section 7.2.1). We presented it with a poster at the annual NeuroMod meeting. We analyzed

24

Inria Annual Report 2023

the dataset focusing on temporal small-worldness. To test certain hypotheses of the observed functional
connectivity, we proposed three temporal null models: the geometric euclidean model on a square and
on a torus, and the hyperbolic geometric graph model. The hyperbolic model is popular in the research
community for studying real-world complex networks. It can model both a high-tailed degree distribution
and small-worldness. Our analysis indicates that the hyperbolic model is more effective in reproducing
the small-worldness property of real data, making it a favorable null model. We presented our initial
findings at the Complex Network Conference [52]. A complete version of the work will soon be appearing
in the journal Network Neuroscience.

8.5.2 Temporal graph neural networks

Participants:

Aurora Rossi.

We collaborated with Carlo Lucibello (Bocconi University, Italy) to contribute to the Julia open source
libraries GraphNeuralNetworks.jl and MLDatasets.jl. Our project’s objective was to add support for
temporal graph neural networks (TGNNs) to GraphNeuralNetworks.jl by creating a temporal graph type.
We added new layers to the package and included new datasets of brain connectomes (see Section 7.2.2)
and traffic networks in MLDatasets.jl. Tutorials have been created to introduce the new temporal graph
type and demonstrate how to perform temporal graph classification using the added data, model, and
features. Examples were presented in a poster at the Julia Days in Paris 2023 [77].

8.5.3 Distributed algorithms

Participants: Davide Ferré, Nicolas Nisse.

Weakly synchronous systems with three machines are turing powerful Communicating finite-state
machines (CFMs) are a Turing powerful model of asynchronous message-passing distributed systems.
In weakly synchronous systems, processes communicate through phases in which messages are first
sent and then received, for each process. Such systems enjoy a limited form of synchronization, and
for some communication models this restriction is enough to make the reachability problem decidable.
In particular, we explore the intriguing case of p2p (FIFO) communication, for which the reachability
problem is known to be undecidable for four processes, but decidable for two. We show in [43] that the
configuration reachability problem for weakly synchronous systems of three processes is undecidable.
This result is heavily inspired by our study on the treewidth of the Message Sequence Charts (MSCs) that
might be generated by such systems. In this sense, the main contribution of this work is a weakly syn-
chronous system with three processes that generates MSCs of arbitrarily large treewidth. In collaboration
with Cinzia di Giusto and Étienne Lozes (I3S, UniCA).

9 Bilateral contracts and grants with industry

9.1 Bilateral contracts with industry

Amadeus, 2022-2023

Participants:

Ilias Driouich, Frédéric Giroire, Chuan Xu.

• Collaboration with Amadeus funded by ANR in the context of "plan de relance". It supports the

PhD thesis of Ilias Driouich under the co-supervision of Frédéric Giroire and Chuan Xu.

• The PhD student has interrupted his PhD in October 2023, thus ending the contract.

Project COATI

25

10 Partnerships and cooperations

10.1 International initiatives

10.1.1 Inria associate team not involved in an IIL or an international program

CANOE

Participants:

Thomas Dissaux, Frédéric Giroire, Frédéric Havet, Nicolas Nisse, Lu-
cas Picasarri-Arrieta, Clément Rambaud.

Title: Combinatorial Algorithms for Networking prOblEms

Duration: 2023 - 2025

Coordinator: Nicolas Nisse

Partners: ParGO Research Group, Department of Mathematics, Federal University of Ceará, Fortaleza,

Brazil

Summary: A graph is a mathematical structure that allows modeling networks in many contexts, from
route networks, telecommunication networks, biological networks, neural networks to social
networks. There are graph problems arising in each of these domains that are classified as compu-
tationally difficult, where the objective is to obtain an efficient algorithm for any graph presented
as input. However, studying algorithms for a problem restricted to special graphs can shed light
on the problem. This approach consists in assuming that the graph has some special structural
property and exploiting this property in the algorithm. Such a structural property defines a class
of graphs, for example, trees or planar graphs. The aim is to build an efficient algorithm for a
class of graphs, and then explore the ideas used to solve larger and larger classes of graphs or with
fewer structural constraints. While a lot of work has been dedicated to the study of structural
properties of graphs, very few results are known concerning directed graphs or hypergraphs which
better model real life networks. For instance, road networks are intrinsically directed and so are
many social networks (e.g., Twitter), co-authorship networks correspond to hypergraphs (where
each publication corresponds to an hyperedge gathering the co-authors), etc. This project aims
at tackling chalenging theoretical open problems in digraphs and/or hypergraphs. The purpose
of this project is also to pursue and extend our fruitful collaboration with the ParGO team from
Universidade Federal do Ceara (Fortaleza).

Web: team.inria.fr/coati/inria-associated-team-canoe/

10.1.2 Participation in other International Programs

CAPES-Cofecub project Ma 1004/23 : Graphs, Optimization, Combinatorics and Algorithms

Participants:

Thomas Dissaux, Frédéric Giroire, Frédéric Havet, Nicolas Nisse, Lu-
cas Picasarri-Arrieta, Clément Rambaud.

Title: Graphs, Optimization, Combinatorics and Algorithms

Duration: 2023 - 2026

Coordinator: Nicolas Nisse

Partners: ParGO Research Group, Department of Mathematics, Federal University of Ceará, Fortaleza,

Brazil

Summary: Complementary project of the Inria EA CANOE.

26

Inria Annual Report 2023

10.2 International research visitors

10.2.1 Visits of international scientists

• Pierluigi Crescenzi, professor at the Gran Sasso Science Institute (L’Aquila, Italy), has been visiting
the team from 1/04/2023 to 26/05/2023 as an invited professor, funded by the UCAJEDI "Appel à
candidatures pour Professeurs Invités UCA 2023".

• Jonatan Narboni, Post-Doctoral Researcher, Jagiellonian University (Poland), February 13 − 18th

2023.

• Jørgen Bang-Jensen, Professor at the University of Southern Denmark, May 22 − 26th 2023.

• Florian Hörsch, post-doctoral fellow at CISPA Helmholtz Center (Germany), June 12 − 17th 2023.

• Claudia Linhares Sales, professor at UFC (Fortaleza, Brazil), granted by CAPES-Cofecub project Ma

1004/23 (Graphs, Optimization, Combinatorics and Algorithms). Dec. 3 − 13th 2023.

• Ana Karolinna Maia, professor at UFC (Fortaleza, Brazil), granted by Inria Associated Team CANOE.

Dec. 11 − 22th 2023.

10.2.2 Visits to international teams

Research stays abroad

• Lucas Picasarri-Arrieta

– SDU, Odense, Denmark. Sep. 25-29, 2023.

• Nicolas Nisse and Lucas Picasarri-Arrieta

– UFC, Fortaleza, Brazil (EA CANOE). Nov. 3-29, 2023.

10.3 European initiatives

10.3.1 Horizon Europe

HORIZON-CL4-2022-HUMAN-02-02 dAIEDGE, 2023-2026

Participants: Chuan Xu, Frédéric Giroire.

Program: HORIZON-CL4-2022-HUMAN-02-02 European Network of AI Excellence Centres: Expanding

the European AI lighthouse.

Project acronym: dAIEDGE

Project title: A network of excellence for distributed, trustworthy, efficient and scalable AI at the Edge

Granting Authority

Duration: September 2023 - August 2026

Coordinator: Alain Pagani, DFKI

Other partners: 36 partners from 15 countries.

Summary: The dAIEDGE Network of Excellence (NoE) seeks to strengthen and support the development
of a dynamic European cutting-edge AI ecosystem under the umbrella of the European Lighthouse
for AI and to sustain the development of advanced AI.

dAIEDGE fosters the exchange of ideas, concepts, and trends on cutting-edge next generation
AI, creating links between ecosystem actors to help both the European Commission (EC) and the

Project COATI

27

European Union (EU) and the peripheral AI constituency identify strategies for future developments
in Europe.

Our main objective is to advance Europe’s innovation and technology base by developing a com-
prehensive policy and governance approach to AI in order for the EU to become a world leader in
innovation in the data economy and its applications.

Web: daiedge.eu

10.4 National initiatives
DGA/Inria Brainside, 2019-2023

Participants:

Francesco D’Amore, Arthur Carvalho Walraven Da Cunha,
Emanuele Natale.

Program: DGA/Inria

Project acronym: Brainside

Project title: Algorithms for simplifying neural networks

Duration: October 2019 - March 2023

Coordinator: Emanuele Natale

Other partners: Inria Paris, EP GANG

Summary: The widespread use of neural networks on devices with computationally-low capabilities, de-
mands for lightweight and energy-efficient networks. Despite such need, and despite the strategies
employed to prevent overfitting by removing a substantial part of their edges, the question of how
to reduce their size in terms of the number of neurons appears largely unexplored. The aim of the
project is to investigate algorithmic procedures to reduce the size of neural networks, in order to
improve the speed with which they can be evaluated and to shed light on how much information
about the computational problem at hand can be encoded within neural networks of small size.

ANR-17-CE22-0016 MultiMod, 2018-2023

Participants:

Ali Al Zoobi, David Coudert, Nicolas Nisse, Michel Syska.

Program: ANR

Project acronym: MultiMod

Project title: Scalable routing in Multi Modal transportation networks

Duration: January 2018 - June 2023

Coordinator: David Coudert

Other partners: Inria Paris, EP GANG; team CeP, I3S laboratory; SME Instant-System; SME Benomad

Summary: The MultiMod project addresses key algorithmic challenges to enable the fast computation of
personalized itineraries in large-scale multi-modal public transportation (PT) networks (bus, tram,
metro, bicycle, etc.) combined with dynamic car-pooling. We will use real-time data to propose
itineraries with close to real travel-time, and handle user-constraints to propose personalized
itineraries. Our main challenge is to overcome the scalability of existing solutions in terms of query
processing time and data-structures space requirements, while including unplanned transportation

28

Inria Annual Report 2023

means (car-pooling), real-time data, and personalized user constraints. The combination of car-
pooling and PT network will open-up areas with low PT coverage enable faster itineraries and so
foster the adoption of car-pooling. We envision that the outcome of this project will dramatically
enhanced the mobility and daily life of citizens in urban areas.

Web: project.inria.fr/multimod/

ANR-19-CE48-0013 Digraphs, 2020-2023

Participants:

Julien Bensmail, David Coudert, Frédéric Havet, Nicolas Nisse,
Stéphane Pérennes.

Program: ANR

Project acronym: Digraphs

Project title: Digraphs

Duration: January 2020 - December 2023

Coordinator: Frédéric Havet

Other partners: LIRMM, Montpellier; LIP, Lyon

Summary: The objectives of the project is to make some advances on digraph theory in order to get a
better understanding of important aspects of digraphs and to have more insight on the differences
and the similarities between graphs and digraphs. Our methodology is two-fold. On the one hand,
we will focus on the tools. Indeed we believe that many proof techniques have been too rarely used
or adapted to digraphs and can be developed to obtain many more results. On the second hand, we
will consider many results on graphs, find their (possibly many) formulations in terms of digraphs
and see if and how they can be extended. Studying such extensions has been occasionally done,
but the point here is to do it in a kind of systematic way. Moreover we shall push even further the
study by considering classes of digraphs: if a result does not extend to the whole class of digraphs,
for which classes does it extend ? if a result extends, can we get better results for some restricted
classes of digraphs ?

Web: project.inria.fr/anrdigraphs/

Défi Inria-Cerema ROAD-AI, 2021-2024

Participants: Christelle Caillouet, David Coudert.

Project acronym: ROAD-AI

Project title: Routes et Ouvrages d’Art Diversiformes, Augmentés & intégrés

Duration: July 2021 - June 2024

Coordinators: Nathalie Mitton (head, Inria, EP FUN), Christophe Biernacki (vice-head, Inria, EP MODAL),

Pierre Marchand (Cerema, DTEC ITM), André Orcési (Cerema, DTEC ITM)

Inria participants: Inria project-teams ACENTAURI, COATI, FUN, MODAL, STATIFY, MODAL

Other partners: Cerema

Project COATI

29

Summary: Integrated management of infrastructure assets is an approach which aims at reconciling
long-term issues with short-term constraints and operational logic. The main objective is to enjoy
more sustainable, safer and more resilient transport infrastructure through effective, efficient
and responsible management. To achieve this, CEREMA and Inria are joining forces in this Inria
Challenge (DEFI) which main goals are to overcome scientific and technical barriers that lead to
the asset management of tomorrow for the benefit of road operators: (i) build a “digital twin” of
the road and its environment at the scale of a complete network; (ii) define “laws” of pavement
behavior; (iii) instrument system-wide bridges and tunnels and use the data in real time; (iv) define
methods for strategic planning of investments and maintenance.

Défi Inria Fed-Malin, 2022-2026

Participants:

Ilias Driouich, Frédéric Giroire, Chuan Xu.

Project acronym: Fed-Malin

Project title: Federated machine Learning over the internet

Duration: 2022 - 2026

Coordinators: Aurélien Bellet (Inria, EP MAGNET), Giovanni Neglia (Inria, EP NEO)

Inria participants: Inria project-teams ARGO, COATI, COMETE, EPIONE, MAGNET, MARACAS, NEO,

SPIRALS, TRIBE, WIDE

Summary: In many use-cases of Machine Learning (ML), data is naturally decentralized: medical data
is collected and stored by different hospitals, crowdsensed data is generated by personal devices,
etc. Federated Learning (FL) has recently emerged as a novel paradigm where a set of entities
with local datasets collaboratively train ML models while keeping their data decentralized. Fed-
Malin is a research project that spans 10 Inria research teams and aims to push FL research and
concrete use-cases through a multidisciplinary consortium involving expertise in ML, distributed
systems, privacy and security, networks, and medicine. We propose to address a number of
challenges that arise when FL is deployed over the Internet, including privacy & fairness, energy
consumption, personalization, and location/time dependencies. Fed-Malin will also contribute to
the development of open-source tools for FL experimentation and real-world deployments, and
use them for concrete applications in medicine and crowdsensing.

Défi Inria-Hive Alvearium, 2022-2026

Participants:

Frédéric Giroire, Stéphane Pérennes.

Project acronym: Alvearium

Project title: Large Scale Secure and Reliable Peer-to-Peer Cloud Storage: towards a shared sovereign

cloud that respects its users’ data

Duration: 2022 - 2026

Coordinator: Claudia-Lavinia Ignat

Inria participants: Inria project-teams COAST, COATI, MYRIADS, WIDE

Other partners: HIVE (www.hivenet.com)

30

Inria Annual Report 2023

Summary: The project aims to propose an alternative peer-to-peer cloud which provides both comput-
ing and data storage via a peer-to-peer network rather than from a centralized set of data centers.
HIVE proposes to exploit the unused capacity of computers and to incentivize users to contribute
their computer resources to the network in exchange for similar capacity from the network and/or
monetary compensation. By exchanging similar computer resources and network capacity users
can benefit from all cloud services. Peers store encrypted fragments of the data of other peers. This
proposed peer-to-peer cloud solution addresses users concerns about the privacy of their data
and the dependency on centralized cloud providers. In this collaboration with HIVE we will apply
our work on replication mechanisms for sharded encrypted data, data placement, Byzantine fault
tolerance and security mechanisms in peer-to-peer environments.

Web: project.inria.fr/alvearium/

PEPR NF (Networks of the Future 2023-2030, 65M€)

Participants: Christelle Caillouet, David Coudert, Frédéric Giroire, Joanna Mouli-

erac.

Project acronym: NF

Project title: Networks of the Future

Duration: 2023 - 2030

Coordinators: CEA (Dmitri Kténas), CNRS (Serge Verdeyme), IMT (Daniel Koffman)

Inria participants: Inria project-teams AGORA, AIO, COATI, DIANA, DYOGENE, ERMINE, FUN, MARACAS,

NEO, RESIST, TRIBE

Summary of PEPR NF: The 5G network and the networks of the future represent a key issue for French
and European industry, society and digital sovereignty. This is why the French government has
decided to launch a dedicated national strategy. One of this strategy’s priority ambitions is to
produce significant public research efforts so the national scientific community contributes fully
to making progress that clearly responds to the challenges of 5G and the networks of the future.
In this context, the CNRS, the CEA and the Institut Mines-Télécom (ITM) are co-leading the ’5G’
acceleration PEPR to support upstream research into the development of advanced technologies
for 5G and the networks of the future.
Inria is involved into 8 research projects over the 10 supported by the program, with the participa-
tion of 11 project-teams of the theme "Networks and Telecommunications" and the coordination
of the PC9-Founds.
COATI is involed in PC1 NF-MUST (End-to-end multi domain services management), coordinated
by Djamal Zeghlache (IMT), which involves Inria project-teams COATI, DIANA and ERMINE.

Summary of PC1 NF-MUST: The 5G and 6G end-to-end Multi-Domain Services Management Architec-
ture (NF-MUST) aims at automating production of inter-domain (business and application level)
services for 5G, 5G Beyond and 6G networks. This is a challenging and still unrealized evolution
of the networks compared with single domain services or pre-established static multi-domain
services that are gradually emerging in 5G and Beyond.
Project NF-MUST of the PEPR 5G and Future Networks, focuses mainly on transforming client
requests into end-to-end service orderings and on mapping them to resources and network level
services (to be) provisioned by the multiple underlying networks. There is a clear evolution of 5
and 6G networks towards the provisioning of services involving multiple players and multiple tech-
nologies. Project NF-MUST addresses the related roles and interactions between customers and
multiple domains in connection to the other “PEPR 5G and Future Networks” projects, to ensure
automated production and operation of multi-domain services across multiple providers. Besides
ordering services, NF-MUST will drive the management of the life cycle of the infrastructures”

Project COATI

31

provisioned services and partake in their dynamic and automated adaptation and operation.
NF-MUST operates at the business subsystem (BSS) level and at the service side of the operation
subsystem (OSS) level. NF-MUST interacts directly with network services treated by project 2 of the
overall program.

PEPR Cloud, 2023-2030

Participants:

Frédéric Giroire, Joanna Moulierac.

Project acronym: Cloud

Project title: Développement de technologies avancées de cloud

Duration: 2023 - 2030

Coordinators: CEA, INRIA

Inria participants: AVALON, COATI, SPIRALS

Summary: PC CARECLoud - Understanding, improving, reducing the environmental impacts of Cloud

Computing.

Cloud computing and its many variations offer users considerable computing and storage capacit-
ies. The maturity of virtualization techniques has enabled the emergence of complex virtualized
infrastructures, capable of rapidly deploying and reconfiguring virtual and elastic resources in
increasingly distributed infrastructures. This resource management, transparent to users, gives
the illusion of access to flexible, unlimited and almost immaterial resources. However, the power
consumption of these clouds is very real and worrying, as are their overall greenhouse gas (GHG)
emissions and the consumption of critical raw materials used in their manufacture. In a context
where climate change is becoming more visible and impressive every year, with serious con-
sequences for people and the planet, all sectors (transport, building, agriculture, industry, etc.)
must contribute to the effort to reduce GHG emissions. Despite their ability to optimize processes
in other sectors (transport, energy, agriculture), clouds are not immune to this observation: the
increasing slope of their greenhouse gas emissions must be reversed, otherwise their potential
benefits in other sectors will be erased. This is why the CARECloud project (understanding, im-
proving, reducing the environmental impacts of Cloud Computing) aims to drastically reduce the
environmental impacts of cloud infrastructures.

Cloud infrastructures are becoming more and more complex: both in width, with more and more
distributed infrastructures, whose resources are scattered as close as possible to the user (edge, fog,
continuum computing) and in depth, with an increasing software stacking between the hardware
and the user’s application (operating system, virtual machines, containers, orchestrators, micro-
services, etc.) The first objective of the project is to understand how these infrastructures consume
energy in order to identify sources of waste and to design new models and metrics to qualify
energy efficiency. The second objective focuses on the energy efficiency of cloud infrastructures,
i.e., optimizing their consumption during the usage phase. In particular, this involves designing
resource allocation and energy lever orchestration strategies: mechanisms that optimize energy
consumption (sleep modes, dynamic adjustment of the size of virtual resources, optimization of
processor frequency, etc.). Finally, the third objective targets digital sobriety in order to sustainably
reduce the environmental impact of clouds. Indeed, current clouds offer high availability and very
high fault tolerance, at the cost of significant energy expenditure, particularly due to redundancy
and oversizing. This third objective aims to design infrastructures that are more energy and IT
resource efficient, resilient to electrical intermittency, adaptable to the production of electricity
from renewable energy sources and tolerant of the disconnection of a highly decentralized part of
the infrastructure.

32

Inria Annual Report 2023

PEPR MOBIDEC - Mob Sci-Data Factory project, 2023-2031

Participants: David Coudert.

Project acronym: MOBIDEC

Project title: Digitalisation et décarbonation des mobilités

Duration: 2023 - 2030

Coordinators: IFP Energies nouvelles (IFPEN) and Université Gustave Eiffel (UGE)

Participants Mob Sci-Data Factory: INRIA (coordinateur), UGE, IFPEN, IGN, CEREMA

Inria participants: AGORA, ASCII, COATI, FUN, TRIBE

Summary: The PEPR Data Technology for Mobility in the Territories (MOBIDEC) is in line with France
2030’s objective of developing sober, sovereign and resilient mobility, by placing the collection,
analysis and processing of mobility data at the heart of its work. It aims to understand and anticipate
the mobility behaviors of goods and people, to facilitate the interpretation and processing of data,
and to offer decision-making tools to simulate the impact of public policies in advance, or to assess
the relevance of a new transport offer.

COATI is involed in project “Mob Sci-Data Factory”, one of the three projects composing the PEPR
MOBIDEC. It shares the PEPR’s primary goal of contributing to developing more sustainable
mobility strategies by providing decision-making support methodology and a digital toolbox fed
by appropriately selecting and processing mobility data and by a deeper understanding of the
involved transport uses and behaviors in mobility. It aims at clarifying and extracting the elements
determining and explaining the characteristics of mobility data, which also raise the following
challenging questions: (1) What data and what are their availability, accessibility, quality, and
representativeness? (2) Which methods and digital tools are necessary for processing, calibrating,
understanding, and enriching data while dealing with missing data and new acquisition ? (3)
What are the specifications of the decision-support platform required for standard tools and data
research sharing?

Mob Sci-Data Factory will make available in a secure and privacy-compliant cloud-based infrastruc-
ture different sources of mobility data together with open-source libraries and methods designed
to be unified, modular, and interoperable from conception. Mob Sci-Dat Factory outcomes will
facilitate data sovereignty and open-source development interoperability across multiple scientific
actors in France, while accelerating research focused on mobility by offering privacy-compliant
and secure data accessibility.

10.4.1 GDR Actions

GDR RSD, ongoing (since 2006) Members of COATI are involved in the working group RESCOM (Réseaux
de communications) of GDR RSD, CNRS (gdr-rsd.fr/pole-rescom). In particular, Christelle Caillouet is
co-chair of this working group since July 2022.

We are also involved in the working group "Energy" of GDR RSD (gdr-rsd.fr/gt-energie). In particular,

Frédéric Giroire is co-chair of this working group.

GDR IM, ongoing (since 2006) Members of COATI are involved in the working group "Graphes" (gt-
graphes.labri.fr/) and Complexité et algorithmes (CoA) www.gdr-im.fr/les-gt/gt-coa/ of GDR IM, CNRS.
(gtgraphes.labri.fr/). In particular, Frédéric Havet is member of the steering committee of the GT Graphes
and Nicolas Nisse is member of the steering committee of the GT CoA.

Project COATI

33

GDR MADICS, ongoing (since 2017) Members of COATI are involved in the working group GRAM-
INEES (GRaph data Mining in Natural, Ecological and Environnemental Sciences) of GDR MADICS
(Masses de Données, Informations et Connaissances en Sciences). (www.madics.fr/actions/actions-en-
cours/graminees/).

11 Dissemination

11.1 Promoting scientific activities

11.1.1 Scientific events: Steering Committees

• David Coudert :

– member of the steering committee of the Symposium on Experimental Algorithms, since

September 2022.

• Emanuele Natale :

– member of the steering committee of the Symposium on Experimental Algorithms, since

September 2022.

• Nicolas Nisse :

– member of the steering committee of the Workshop on GRAph Searching, Theory and Applic-

ations, since 2014.

11.1.2 Scientific events: organisation

General chair, scientific chair

• Christelle Caillouet :

– Organizing chair of the annual conferences CoRes and AlgoTel of the GDR RSD located in

Cargèse, France, May 22-26 2023. coresalgotel2023.i3s.univ-cotedazur.fr

• Nicolas Nisse :

– Organizing chair and scientific chair of the 11t h Workshop on GRAph Searching, Theory and

Applications, Bertinoro, Italy, October 22-27, 2023 grasta23.bici.events/home.

Member of the organizing committees

• David Coudert :

– UCA-Majulab Workshop 2023: quantum technologies & photonics, Nice, France, June 19-21,

2023. www-sop.inria.fr/coati/events/ucamajulab2023/

11.1.3 Scientific events: selection

Chair of conference program committees

• Christelle Caillouet :

– Co-PC chair with Nancy Perrot and Eric Gourdin (Orange Labs) of the session "Optimisation

dans les Réseaux Telecom" at the conference Roadef 2023.

34

Inria Annual Report 2023

Member of the conference program committees

• Christelle Caillouet :

– AlgoTel : 25èmes Rencontres francophones sur les aspects algorithmiques des télécommunic-

ations, Cargèse, France, 22-26 May 2023;

– Wisarn : 16th International Workshop on WIreless Sensing and Actuating Robotic Networks

(in conjunction with IEEE INFOCOM 2023), New-York, USA, 17-20 May 2023;

– Wimob : 19th International Conference on Wireless and Mobile Computing, Networking and

Communications, Montreal, Canada, 21-23 June 2023;

– VTC-Spring : IEEE 97th Vehicular Technology Conference, Florence, Italy, 20-23 June 2023;

– ITC35 : 35th International Telecongress Conference, Turin, Italy, 3-5 October 2023.

• David Coudert:

– ATMOS: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization,

and Systems, Amsterdam, Netherlands, September 7-8, 2023;

– ESA - track B: European Symposium on Algorithms, Amsterdam, Netherlands, September 4-6,

2023;

– IEEE ICC: IEEE International Conference on Communications, Rome, Italy, May 28 -June 1st,

2023;

– IEEE Globecom: IEEE Global Communications Conference, Kuala Lumpur, Malaysia, Decem-

ber 4-8, 2023;

– ONDM: Conference on Optical Network Design and Management, Coimbra, Portugal, May

8-11 2023.

• Frédéric Havet :

– LAGOS : XII Latin-American Algorithms, Graphs and Optimization Symposium, Huatulco,

Mexico, September 18-22th, 2023;

– JGA : 25èmes Journées Graphes et Algoritmes, Lyon, France, November 12-14th, 2023.

• Emanuele Natale:

– NeurIPS: Thirty-seventh Conference on Neural Information Processing Systems, New Orleans,

LA, USA, December 10-16, 2023;

– AAAI: The 38th Annual AAAI Conference on Artificial Intelligence, Vancouver, Canada, Febru-

ary 20-27 2024;

– UAI: 39th Conference on Uncertainty in Artificial Intelligence, Pittsburgh, PA, USA, 31 July - 4

August 2023 (identified as Top Reviewer by the PC chairs);

– AAAI: The 37th Annual AAAI Conference on Artificial Intelligence, Washington, DC, USA,

February 7-14 2023;

– JuliaCon: The Julia Programming Language Conference, Cambridge, USA, July 25-29 2023.

• Nicolas Nisse :

– AlgoTel : 25èmes Rencontres francophones sur les aspects algorithmiques des télécommunic-

ations, Cargèse, France, 22-26 May 2023;

– LAGOS : XII Latin-American Algorithms, Graphs and Optimization Symposium, Huatulco,

Mexico, September 18-22th, 2023.

• Chuan Xu :

– Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Oppor-

tunities Workshop at ICML 2023, Hawaii, USA, July 28, 2023 .

Project COATI

35

11.1.4 Journal

Member of the editorial boards

• Jean-Claude Bermond :

– Computer Science Reviews (Elsevier);

– Discrete Applied Mathematics (Elsevier);

– Discrete Mathematics (Elsevier);

– Discrete Mathematics, Algorithms and Applications (World Scientific);

– Journal of Graph Theory (Wiley);

– Advisory board of Journal of Interconnection Networks (World Scientific);

– Networks (Wiley);

– Parallel Processing Letters (World Scientific);

– the SIAM book series on Discrete Mathematics (SIAM).

• Alexandre Caminada :

– IEEE Transactions on Mobile Computing (IEEE);

– IEEE Transactions on Vehicular Technology (IEEE);

– Journal of Traffic and Transportation Engineering (Elsevier);

– Sensors — Open Access Journal (MDPI);

– Soft Computing (Springer).

• David Coudert :

– Discrete Applied Mathematics (Elsevier);

– Networks (Wiley).

• Frédéric Giroire :

– Journal of Interconnection Networks (World Scientific);

– Telecom (MDPI).

• Frédéric Havet

– Discrete Mathematics and Theoretical Computer Science (DMTCS);

– Innovations in Graph Theory

• Emanuele Natale

– The WikiJournal of Science (Wikimedia Foundation).

• Nicolas Nisse :

– Discrete Applied Mathematics (Elsevier).

11.1.5 Invited talks

• Chuan Xu

– Passive attacks for federated learning. Days on Distributed Learning, GDR RSD Summer

School on Distributed Learning, September 21th-22th, Lyon, France

• Nicolas Nisse

– Deciding the Erdös-Pósa property in 3-connected digraphs. 2nd Fortaleza Workshop on Com-

binatorics (ForWorC), 6-10th November 2023, Fortaleza, Brazil

36

Inria Annual Report 2023

11.1.6 Leadership within the scientific community

• Christelle Caillouet :

– Co-chair of Pôle RESCOM of GDR RSD of CNRS since July 2022.

• David Coudert :

– Member of the steering committee of the Institut Fédératif Quantique Azuréen (QuantAzur) at

Université Côte d’Azur till June 2023;

– Member of the steering committee of seminar Forum Numerica of Academy 1 RISE of UCAJEDI

since 2018;

• Frédéric Giroire :

– Member of the steering committee of GT Energy of the GDR RSD of CNRS.

• Frédéric Havet :

– Member of the steering committee of GT Graphes of the GDR IM of CNRS since 2005;

– President of the PhD prize committee ; Graphes "Charles Delorme".

• Nicolas Nisse :

– Member of the steering committee of GT CoA of the GDR IM of CNRS since 2018;

11.1.7 Scientific expertise

• Jean-Claude Bermond :

– Expert for DRTT-MESR Crédit impôt recherche (CIR et agréments).

• David Coudert :

– Expert for ANR;

– Expert for the Emergence 2023-2024 call of Sorbonne Université.

• Emanuele Natale :

– Member of the ST6 Expert Panel (Computer science and informatics) of the National Science

Centre of Poland, 2023.

• Nicolas Nisse

– Expert for EUTOPIA Science and Innovation Program;

– Expert for ECOS SUD CHILI 2023.

11.1.8 Research administration

• Christelle Caillouet

– Elected member of Conseil de Laboratoire I3S since 2017;

• Alexandre Caminada

– Member of the executive board of the Sophia Interdisciplinary Institute of Artificial Intelli-

gence started in 2019;

– Manager of the research committee for the Polytech network national academic Foundation.

• David Coudert :

– Head of Science of the Inria Centre at Université Côte d’Azur, since September 2022;

Project COATI

37

– Member of the “Bureau du comité des équipe-projets” of Inria research center Sophia Antipolis

- Méditerranée since 2018;

– Member of the Inria Evaluation Committee, since September 2022;

– Member of the Inria committee for researchers promotions (CRHC, CRHC-8, DR1, DRCE,

DRCE-2), 2023;

– Member of the Inria selection committee for Senior Researchers (DR2), 2023.

• Frédéric Giroire :

– Head of COMRED team of I3S laboratory, since April 2022;

– In charge of the internships of stream UbiNet of Master 2 IFI, Université Côte d’Azur.

• Frédéric Havet

– Coordinator of ANR project Digraphs;

– Co-head of Terra Numerica.

• Joanna Moulierac:

– Member of the CA of SPECIF-CAMPUS (Société Professionnelle des Enseignants et Chercheurs

en Informatique de France);

– Member of the I3S CO2 group since 2019 (www.i3s.unice.fr/co2/);

– Member of the CSPT ( Comité Scientifique, Pédagogique et Technique) Terra Numerica, since

2022.

• Emanuele Natale:

– External member of University of Rome Tor Vergata’s PhD School in Data Science (Italy).

• Nicolas Nisse :

– Elected member for the "Comité de centre", Inria Sophia Antipolis - Méditerranée, since 2017;

– Elected member for Inria at the CoSP of EUR DS4H since October 2020;

– Nominated member for Inria at the board of doctoral school STIC, since September 2022;

– Member of the “Comité de Suivi Doctoral” of Inria, since September 2022;

– Member of the CSPT Terra Numerica, since 2020.

• Luc Hogie

– Elected member of Conseil de Laboratoire I3S.

11.2 Teaching - Supervision - Juries

11.2.1 Teaching Responsibilities

• Julien Bensmail :

– Head of the Licence Professionnelle “Managements des Processus Logistiques” (MPL) of

Université Côte d’Azur, since September 2019.

• Christelle Caillouet :

– Member of the “Conseil de Département Informatique” of IUT Nice Côte d’Azur (since Septem-

ber 2022).

• Alexandre Caminada

38

Inria Annual Report 2023

– Head of the graduate school of engineering Polytech Nice Sophia (1500 master grade students,

100 faculty members, 50 staffs);

– Member of the executive board of the Polytech network, national network of public graduate

school of engineering;

– Member of the executive board of Université Côte d’Azur.

• Joanna Moulierac :

– Member of the “Conseil de Département Informatique” of IUT Nice Côte d’Azur (since Septem-

ber 2017).

• Michel Syska :

– Head of the MIAGE (IT methods applied to business management) Master’s degree MBDS
(Mobiquity, Big Data and Systems integration), of Université Côte d’Azur (since September
2022);

– Co Head of the Bachelor’s degree in Artificial Intelligence (Licence Sciences et Technologies

parcours IA), of Université Côte d’Azur;

– Head of "Campus des Métiers et des Qualifications - défi du numérique", Université Côte

d’Azur, Rectorat et Région PACA.

11.2.2 Teaching

Members of COATI have taught for more that 1100 hours (ETD) this year:

• BUT: Julien Bensmail, Recherche opérationnelle, 90h ETD, Level L2, Département QLIO of IUT,

Université Côte d’Azur, France;

• BUT: Julien Bensmail, Algorithmique et programmation avancées, 64h ETD, Level L2, Département

QLIO of IUT, Université Côte d’Azur, France;

• BUT: Thomas Dissaux, Communication et fonctionnement bas niveau, 20h ETD, Level L1, Départe-

ment Informatique of IUT, Université Côte d’Azur, France;

• BUT: Thomas Dissaux, Introduction aux services réseaux, 14h ETD, Level L1, Département Inform-

atique of IUT, Université Côte d’Azur, France;

• BUT: Thomas Dissaux, Initiation au développement, 64h ETD, Level L1, Département Informatique

of IUT, Université Côte d’Azur, France;

• BUT: Luc Hogie, System programming, 24h ETD, Level L2, IUT, Université Côte d’Azur, France;

• BUT: Christelle Caillouet, Automates et langages, 12h ETD, Level L2, IUT, Université Côte d’Azur,

France;

• BUT: Christelle Caillouet, Programmation orientée objet, 48h ETD, Level L1, IUT, Université Côte

d’Azur, France;

• BUT: Christelle Caillouet, Méthodes d’optimisation pour l’aide à la décision, 21h ETD, Level L3, IUT,

Université Côte d’Azur, France;

• BUT: Lucas Picasarri-Arrieta, Automates et langages, 12h ETD, Level L2, IUT, Université Côte d’Azur,

France;

• BUT: Lucas Picasarri-Arrieta, Introduction à la programmation, 52h ETD, Level L1, IUT, Université

Côte d’Azur, France;

• BUT: Lucas Picasarri-Arrieta, Méthodes d’optimisation pour l’aide à la décision, 12h ETD, Level L1,

IUT, Université Côte d’Azur, France;

Project COATI

39

• BUT: Joanna Moulierac, Introduction aux Réseaux, 56h ETD, Level L1, IUT, Université Côte d’Azur,

France;

• BUT: Joanna Moulierac, Réseaux avancés, 30h ETD, Level L2, IUT, Université Côte d’Azur, France;

• PeiP: Joanna Moulierac, Programmation Objet, 30h ETD, Level L1, Polytech, Université Côte d’Azur,

France;

• LP: Julien Bensmail, Sécurité des échanges de données inter-entreprises, 30h ETD, Level LP, LP MPL

of IUT, Université Côte d’Azur, France;

• LP: Joanna Moulierac, Programmation C#, 30h ETD, Level L3, IUT, Université Côte d’Azur, France;

• Licence: Michel Syska, Algorithmics, 33h ETD, Level L3, parcours IA Science & Technologie -

Université Côte d’Azur, France;

• Licence: Michel Syska, Heuristic search, 21h ETD, Level L3, parcours IA Science & Technologie -

Université Côte d’Azur, France;

• Licence: Chuan Xu, Programmation fonctionnelle, 36h ETD, Level L3, Université Côte d’Azur,

France;

• Licence: Chuan Xu, Python pour l’IA, 30h ETD, Level L3, MIAGE IA2 - Université Côte d’Azur,

France;

• Licence: Clément Rambaud, Informatique Théorique, 20h ETD, MAM3, Polytech Nice Sophia

Antipolis, France;

• Master: Christelle Caillouet, Introduction Algorithmic and Programming, 60h ETD, MAM3, Polytech

Nice Sophia Antipolis, France;

• Master: Alexandre Caminada, Radio location systems, 20h ETD, Master 2 (in english), Polytech Nice

Sophia Antipolis, France;

• Master: Alexandre Caminada, Artificial intelligence, 40h ETD, Master 2 (in english), Polytech Nice

Sophia, France;

• Master: Alexandre Caminada, Master grade student’s internship supervision and assesment, 10h

ETD, Master 2, Polytech Nice Sophia Antipolis, France;

• Master: Frédéric Giroire, Graph Algorithms, 18h ETD, Master 2, International Track Ubinet, Uni-

versité Côte d’Azur, France;

• Master: Frédéric Giroire, Machine learning for networks, 34.5 h ETD, Master 2, International Track

Ubinet, Université Côte d’Azur, France;

• Master: Frédéric Giroire, ICT and Environment, Green algorithm design, 4.5h ETD, Master 2, minor,

Université Côte d’Azur, France;

• Master: Nicolas Nisse, Graphs, 36h ETD, M1 Informatique et Interaction, Université Côte d’Azur,

France;

• Master: Nicolas Nisse, Algorithms for Telecoms, 15h ETD, M2 Ubinet, Université Côte d’Azur, France;

• Master: Michel Syska, Databases for big data, 20h ETD, M1 MIAGE - Université Côte d’Azur, France;

• Master: Michel Syska, Cloud computing, 45h ETD, M2 MIAGE MBDS - Université Côte d’Azur,

France.

40

Inria Annual Report 2023

11.2.3 Supervision

PhD thesis

• PhD in progress: Tiago da Silva Barros, Joint Training Design and Network Resource Allocation for
Distributed Machine Learning , since October 2022. Co-supervisors: Ramon Aparicio and Frederic
Giroire;

• PhD in progress: Ilias Driouich, Privacy-preserving algorithms for cross-device federated learning.

Co-supervisors: Frédéric Giroire and Chuan Xu. CIFRE grant with Amadeus;

• PhD in progress: Henrique Lovisi Ennes, Calcul quantique en topologie, since October 2023. Co-

supervisors: Clément Maria (DataShape) and Nicolas Nisse;

• PhD in progress: Lucas Picasarri-Arrieta , Digraph colouring, since October 2021. Supervisor:

Frédéric Havet;

• PhD in progress: Clément Rambaud, Colourong digraphs, since September 2023. Supervisor:

Frédéric Havet;

• PhD in progress: Aurora Rossi, Algorithmic aspects and random network models for temporal brain

networks, since October 2022. Supervisor: David Coudert;

• PhD defended September 13 2023: Arthur Carvalho Walraven da Cunha, Pruning random structures.

Supervisor: Emanuele Natale;

• PhD defended September 21 2023: Igor Dias da Silva, Optimisation of UAVs deployment and
coordination for exploration and monitoring applications [57]. Co-supervisors: Christelle Caillouet
and David Coudert;

• PhD defended September 25 2023: Thomas Dissaux, Graph decompositions: Treelength and pursuit-

evasion games [58]. Supervisor: Nicolas Nisse.

Internships

• License (tutorship): Andranik Arakelov, Kishan Turpin, Adrien Escoubeyrou, Development of games
for Terra Numerica, M2 IoT CPS, Université Côte d’Azur, France, from October 2023 until March
2024. Supervisor: Luc Hogie;

• Licence: Teiki Rigaud, Problème d’ordonnancement pour la technologie LoRa, L3 ENS PSL, June-July,

2023. Supervisors: Christelle Caillouet, Frédéric Havet, Lucas Picasarri-Arrieta;

• Licence: Justine Cauvi, Bornes inférieures pour la largeur de coupe des graphes, L3 ENS Lyon,

June-July, 2023. Supervisor: David Coudert;

• Licence: Maël Clergue, Scientific Machine Learning for World Dynamics Modeling, ENS Lyon,

June-July, 2023. Supervisor: Emanuele Natale;

• Master 1 (tutorship): Dimitri Morelle, Differential privacy and byzantine resilience in federated
learning, M1 Computer Science, Digital Systems for Humans (DS4H) Graduate school - Université
Côte d’Azur, France, from October 2023 until December 2023. Supervisor: Chuan Xu;

• Master 1: Lilian Fortas, Pathlength of chordal graphs, année de césure Centrale-Supélec (entre 2 et

3me année), from September 2023 to February 24. Supervisor: Nicolas Nisse;

• Master 2 (TER): Valentin Mascaro, Sadmi Joudet, On the Use of Digital Twins for the Decentralized
Management of Large Multihop Mobile Networks, M2 IoT CPS, Université Côte d’Azur, France, from
October 2023 until March 2024. Supervisor: Luc Hogie;

• Master 2 (TER): Valentin Mascaro, Sadmi Joudet, On the Use of Digital Twins for the Decentralized
Management of Large Multihop Mobile Networks, M2 IoT CPS, Université Côte d’Azur, France, from
October 2023 until March 2024. Supervisor: Luc Hogie;

Project COATI

41

• Master 2: Pietro Ventrella, Study of Large Distributed Storage Systems, Ubinet international track,
Université Côte d’Azur, France, from October 2023 until December 2023. Supervisors: Frédéric
Giroire and Stéphane Pérennes;

• Master 2 (TER): Fatima Laaziz, Privacy on-demand and Security preserving Federated Generative
Networks or Models, Ubinet, Université Côte d’Azur, France, from October 2023 until December
2023. Supervisors: Chuan Xu and Frédéric Giroire;

• Master 2 (TER): Sohaib Idalin, Differential privacy and byzantine resilience in federated learning,
Ubinet, Université Côte d’Azur, France, from October 2023 until December 2023. Supervisors:
Chuan Xu and Giovanni Neglia.

11.2.4 Juries

• Christelle Caillouet:

– Member of the Comité de suivi individuel of Masoud Taghavian, IMT Atlantique, June 13,

2023;

– Member of the PhD committee of Nina Santi, FUN team Inria Lille, 19 December 2023;

– Member of the PhD committee of Alessandro Aimi, CNAM Paris, 19 September 2023.

• David Coudert:

– Member of the Comité de suivi individuel of Zahraa Al Atar, IMT Atlantique and Université de

Rennes 1, May 5, 2023;

– Member of the PhD committee of Fabrice Lécuyer on Ordering nodes to scale to large real-

world networks, Sorbonne Université, LIP6, Paris, France, July 6, 2023.

• Frédéric Giroire:

– President of the PhD committee of Othmane Marfoq on Tackling Heterogeneity in Federated
Learning Systems, Université Côte d’Azur, Neo team Inria, Sophia Antipolis, France, December
7, 2023;

– President of the PhD committee of François Doré on Drawing graphs on surfaces of null and
higher genus, Université Côte d’Azur, Inria, Sophia Antipolis, France, December 11, 2023;

– Member of the PhD committee of Chen Dang on Heuristics Learning for Solving Network
Optimization Problems, Université Paris Dauphine-PSL, Paris, France, December 8, 2023;

– Member of the PhD committee of Arthur C. W. da Cunha on Pruning random structures,

Université Côte d’Azur, COATI team Inria, Sophia Antipolis, France, September 13, 2023;

– Member of the Comité de suivi individuel of Pierre-Marie Lechevalier, IMT Atlantique and

Université de Rennes 1, May 2, 2023;

– Member of the Comité de suivi individuel of Angelo Rodio, Université Côte d’Azur, Neo team

Inria, Sophia Antipolis, France, June 16, 2023;

– Member of the Comité de suivi individuel of Younes Ben Mazzianne, Université Côte d’Azur,

Neo team Inria, Sophia Antipolis, France, May 16, 2023;

– Member of the Comité de suivi individuel of Aymeric Picard Marchetto, Université Côte d’Azur,

I3S, Sophia Antipolis, France, June 30, 2023.

• Frédéric Havet:

– Member of the PhD committee of Giannos Stamoulis, Université de Montpellier, France,

December 12, 2023;

– Reviewer of the PhD committee of Rémi Pellerin, ENS Lyon, France, December 11, 2023;

– Member of the PhD committee of Jonas Costa Ferreira da Silva, Universidade Federal do

Ceara, Brasil, May 25, 2023;

42

Inria Annual Report 2023

– Member of the Comité de suivi individuel of François Doré, Université Côte d’Azur, I3S, Sophia

Antipolis, France, July 12, 2023;

– Member of the Comité de suivi individuel of Nacim Oijid, Université Lyon 1, France, May 12,

2023.

• Joanna Moulierac:

– Member of the Comité de suivi individuel of Killian Castillon, Université Côte d’Azur, France,

May 12, 2023.

• Emanuele Natale:

– Member of Prokopchik Konstantin’s PhD jury. Date of defense: March 24th 2023. Institution:
GSSI (L’Aquila, Italy). Thesis title: Hypergraph-based Methods for Semi-Supervised Learning.

• Nicolas Nisse

– Member of the Comité de suivi individuel of Evangelos Protopapas, LIRMM, Université Mont-

pellier, France, September 21, 2023.

11.3 Popularization

Participants: Caroline Brosse, Michel Cosnard, Frédéric Giroire, Frédéric Havet,
Lucas Picasarri-Arrieta,

Joanna Moulierac, Nicolas Nisse,
Stéphane Pérennes, Clément Rambaud, Michel Syska.

COATI is deeply involved in Terra Numerica. Its members are very active in content creation, dissem-

ination to the public, training of teaching or facilitating staff, and project governance.

Frédéric Havet and Nicolas Nisse are also involved in the ANR project ASMODEE (Analyse et concep-

tion de situations de médiation en informatique débranchée) headed by the LIRIS laboratory.

11.3.1 Internal or external Inria responsibilities

Frédéric Havet is co-head of Terra Numerica and one of the responsible of the “Comité Scientifique,
Pédagogique et Technique” ; Nicolas Nisse is a member of this committee ; Joanna Moulierac is the
referent of Terra Numerica for higher education ; Luc Hogie is in charge of hardware and software
development.

Frédéric Havet is member of the editorial board of 1024, le bulletin de la SIF (Société Informatique de

France, in which he draws cartoons to illustrate some articles.

11.3.2 Articles and contents

Press articles related to Terra Numerica can be found at terra-numerica.org/presse/. Members of COATI
have contributed to several of them.

11.3.3 Education

Most of the members of COATI are involved in Terra Numerica. During the year 2023, more than 300 events
held, Terra Numerica has been visited by 290 classes (about 8000 primary school/college/highschool
student, for 2 hours in average). We have trained about 360 persons (including 250 teachers) and touched
more than 15000 people during events such as Fête de la science, etc.

Project COATI

11.3.4 Interventions

43

Many members of COATI (C. Brosse, M. Cosnard, F. Giroire, F. Havet, J. Moulierac, N. Nisse, L. Picasarri-
Arrieta, S. Pérennes, C. Rambaud, M. Syska) participated some general audience science fairs, such
as the Fête de la science in October 2024 (we were present on the “Village des Sciences” in Antibes-
Juan-les-Pins, Valbonne, Villeneuve-Loubet, Vinon-sur Verdon) or some stages of the Science Tour Terra
Numerica (20 days in several places : Digne-les-Bains, Forcalquier, Manosque, Aups, La Seyne sur Mer,
Brignoles, Draguignan, Salernes, Roquebillière, Saint Martin de Vésubie, Breil sur Roya, Tende. They also
occasionally act as scientific facilitator at Terra Numerica.

Frédéric Havet also gave general audience conferences in several cities (Bonson, Brignoles, Draguigan,
Falicon, Menton, Rians, Vinon-sur-Verdon) as well as in for Esope 21, Science pour Tous 06, and Terra
Numerica.

12 Scientific production

12.1 Major publications

[1] L. Becchetti, A. Clementi, E. Natale, F. Pasquale and L. Trevisan. ‘Finding a Bounded-Degree
Expander Inside a Dense One’. In: Proceedings of the thirty-first Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA). Salt Lake City, United States, Jan. 2020. URL: https://hal.archives
-ouvertes.fr/hal-02002377.

[2]

[3]

[4]

J. Bensmail, V. Campos, A. K. Maia, N. Nisse and A. Silva. ‘Deciding the Erd˝os-Pósa property in
3-connected digraphs ⋆’. In: WG 2023 - 49th International Workshop on Graph-Theoretic Concepts
in Computer Science. LNCS. Fribourg (CH), Switzerland, 28th June 2023. URL: https://inria.ha
l.science/hal-04084227.

J. Bensmail, A. Harutyunyan, T.-N. Le and S. Thomassé. ‘Edge-partitioning a graph into paths:
beyond the Barát-Thomassen conjecture’. In: Combinatorica 39.2 (Apr. 2019), pp. 239–263. DOI:
10.1007/s00493-017-3661-5. URL: https://hal.archives-ouvertes.fr/hal-01744515.

J.-C. Bermond, F. Giroire and N. Nisse. ‘Graphes et Télécommunications’. In: Bibliothèque Tangente.
Hors Serie 75 La recherche opérationnelle Hors Serie 75 (2021), pp. 120–125. URL: https://hal.a
rchives-ouvertes.fr/hal-03455881.

[5] N. Bousquet, F. Havet, N. Nisse, L. Picasarri-Arrieta and A. Reinald. ‘Digraph redicolouring’. In:
European Journal of Combinatorics 116 (Feb. 2024), p. 103876. DOI: 10.1016/j.ejc.2023.103876.
URL: https://hal.science/hal-04306893.

[6] C. Caillouet, F. Giroire and T. Razafindralambo. ‘Efficient Data Collection and Tracking with Flying
Drones’. In: Ad Hoc Networks. Ad Hoc Networks 89.C (2019), pp. 35–46. DOI: 10.1016/j.adhoc.2
019.01.011. URL: https://hal.inria.fr/hal-02043136.

[7] D. Coudert, G. Ducoffe and N. Nisse. ‘To Approximate Treewidth, Use Treelength!’ In: SIAM Journal
on Discrete Mathematics 30.3 (2016), p. 13. DOI: 10.1137/15M1034039. URL: https://hal.inria
.fr/hal-01348965.

[8] D. Coudert, G. Ducoffe and A. Popa. ‘P-FPT algorithms for bounded clique-width graphs’. In: ACM
Transactions on Algorithms 15.3 (June 2019), pp. 1–57. DOI: 10.1145/3310228. URL: https://hal
.archives-ouvertes.fr/hal-02152971.

[9] A. da Cunha, E. Natale and L. Viennot. ‘Proving the Strong Lottery Ticket Hypothesis for Convolu-
tional Neural Networks’. In: ICLR 2022 - 10th International Conference on Learning Representations.
Virtual, France, 25th Apr. 2022. URL: https://hal.archives-ouvertes.fr/hal-03548226.

[10] F. Dross and F. Havet. ‘On the unavoidability of oriented trees’. In: Journal of Combinatorial Theory,
Series B 151 (Nov. 2021), pp. 83–110. DOI: 10.1016/j.jctb.2021.06.003. URL: https://hal.in
ria.fr/hal-03269226.

[11] F. Giroire, F. Havet and J. Moulierac. ‘On the Complexity of Compressing Two Dimensional Routing
Tables with Order’. In: Algorithmica 80.1 (Jan. 2018), pp. 209–233. DOI: 10.1007/s00453-016-024
3-7. URL: https://hal.inria.fr/hal-01686641.

44

Inria Annual Report 2023

[12] M. Heusse, T. Attia, C. Caillouet, F. Rousseau and A. Duda. ‘Capacity of a LoRaWAN Cell’. In:
Proceedings of the 23rd International ACM Conference on Modeling, Analysis and Simulation of
Wireless and Mobile Systems (MSWiM 2020). MSWiM ’20. alicante, Spain: Association for Computing
Machinery, Nov. 2020, pp. 131–140. DOI: 10.1145/3416010.3423228. URL: https://hal.archi
ves-ouvertes.fr/hal-03010556.

[13] L. Hogie, M. Syska and N. Chleq. ‘BigGraphs: distributed graph computing’. IDDN.FR.001.410005.000.-

S.P.2015.000.31235 (France). 6th Sept. 2016. URL: https://hal.archives-ouvertes.fr/hal-0
1360649.

[14] H. Lesfari and F. Giroire. ‘Nadege: When Graph Kernels meet Network Anomaly Detection’. In: IEEE
International Conference on Computer Communications (INFOCOM). London, United Kingdom,
2nd May 2022. URL: https://hal.inria.fr/hal-03655867.

[15] M. Rifai, N. Huin, C. Caillouet, F. Giroire, J. Moulierac, D. Lopez Pacheco and G. Urvoy-Keller.
‘Minnie : An SDN world with few compressed forwarding rules’. In: Computer Networks 121 (July
2017), pp. 185–207. DOI: 10.1016/j.comnet.2017.04.026. URL: https://hal.inria.fr/hal-
01576133.

12.2 Publications of the year

International journals

[16] A. Al Zoobi, D. Coudert and N. Nisse. ‘Finding the k Shortest Simple Paths: Time and Space trade-
offs’. In: ACM Journal of Experimental Algorithmics 28 (7th Oct. 2023), p. 23. DOI: 10.1145/3626567.
URL: https://hal.science/hal-03196830.

[17]

J. Araujo, J. Bensmail, V. Campos, F. Havet, A. K. Maia, N. Nisse and A. Silva. ‘On Finding the Best and
Worst Orientations for the Metric Dimension’. In: Algorithmica 85.10 (Oct. 2023), pp. 2962–3002.
DOI: 10.1007/s00453-023-01132-0. URL: https://hal.science/hal-04271379.

[18] F. Benevides, J.-C. Bermond, H. Lesfari and N. Nisse. ‘Minimum lethal sets in grids and tori under
3-neighbour bootstrap percolation’. In: European Journal of Combinatorics (Sept. 2023), p. 18. DOI:
10.1016/j.ejc.2023.103801. URL: https://inria.hal.science/hal-04368240.

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

J. Bensmail. ‘A notion of vertex equitability for proper labellings’. In: Discrete Applied Mathematics
346 (2024), pp. 228–247. URL: https://hal.science/hal-04012367.

J. Bensmail. ‘Maximising 1’s through Proper Labellings’. In: Discussiones Mathematicae Graph
Theory (2023). URL: https://hal.science/hal-04086726.

J. Bensmail. ‘Some Properties of Minimal Arbitrarily Partitionable Graphs’. In: The Australasian
Journal of Combinatorics 86.1 (2023), pp. 149–168. URL: https://hal.science/hal-03654327.

J. Bensmail, T. Das, D. Lajou, S. Nandi and S. Sen. ‘On the pushable chromatic number of various
types of grids’. In: Discrete Applied Mathematics 329 (2023), pp. 140–154. DOI: 10.1016/j.dam.20
23.01.013. URL: https://hal.science/hal-03531789.

J. Bensmail, F. Fioravantes, F. Mc Inerney, N. Nisse and N. Oijid. ‘The Maker-Breaker Largest
Connected Subgraph Game’. In: Theoretical Computer Science 943 (2023), pp. 102–120. DOI: 10.10
16/j.tcs.2022.12.014. URL: https://hal.science/hal-03993562.

J. Bensmail, H. Hocquard and D. Lajou. ‘On the algorithmic complexity of determining the AVD
and NSD chromatic indices of graphs’. In: Theoretical Computer Science 939 (2023), pp. 105–118.
DOI: 10.1016/j.tcs.2022.10.017. URL: https://hal.science/hal-03609262.

J. Bensmail, H. Hocquard, D. Lajou and É. Sopena. ‘A proof of the Multiplicative 1-2-3 Conjecture’.
In: Combinatorica 43 (2023), pp. 37–55. DOI: 10.1007/s00493-023-00003-0. URL: https://hal
.science/hal-03324458.

J. Bensmail, H. Hocquard and P.-M. Marcille. ‘On inducing degenerate sums through 2-labellings’.
In: Graphs and Combinatorics (2024). URL: https://hal.science/hal-03957100.

J.-C. Bermond, T. Kodate and J. Yu. ‘Gossiping with interference in radio ring networks’. In: Discrete
Mathematics and Theoretical Computer Science 25.2 (2023), #5. DOI: 10.46298/dmtcs.9399. URL:
https://hal.science/hal-04206040.

Project COATI

45

[28] S. Bessy, J. Pardey, L. Picasarri-Arrieta and D. Rautenbach. ‘Unbalanced Spanning Subgraphs in
Edge Labeled Complete Graphs’. In: The Electronic Journal of Combinatorics 30.1 (2023), pp. 1–35.
DOI: 10.37236/10866. URL: https://hal.science/hal-04172966.

[29] N. Bousquet, F. Havet, N. Nisse, L. Picasarri-Arrieta and A. Reinald. ‘Digraph redicolouring’. In:
European Journal of Combinatorics 116 (Feb. 2024), p. 103876. DOI: 10.1016/j.ejc.2023.103876.
URL: https://hal.science/hal-04306893.

[30] C. Carvalho, J. Costa, R. Lopes, A. K. Maia, N. Nisse and C. L. Sales. ‘From branchings to flows: a
study of an Edmonds’ like property to arc-disjoint branching flows’. In: Discrete Mathematics and
Theoretical Computer Science vol. 25:1.10 (2nd May 2023), p. 15. DOI: 10.46298/dmtcs.9302. URL:
https://hal.science/hal-03031759.

[31] T. Dissaux, G. Ducoffe, N. Nisse and S. Nivelle. ‘Treelength of series–parallel graphs’. In: Discrete
Applied Mathematics 341 (Dec. 2023), pp. 16–30. DOI: 10 . 1016 / j . dam . 2023 . 07 . 022. URL:
https://hal.science/hal-04268050.

[32] F. Giroire, S. Pérennes and T. Trolliet. ‘A Random Growth Model with any Real or Theoretical
Degree Distribution’. In: Theoretical Computer Science 940.Part A (9th Jan. 2023), pp. 36–51. DOI:
10.1016/j.tcs.2022.10.036. URL: https://inria.hal.science/hal-03858432.

[33] M. Heusse, C. Caillouet and A. Duda. ‘Performance of Unslotted ALOHA with Capture and Multiple
Collisions in LoRaWAN’. In: IEEE Internet of Things Journal 10.20 (15th Oct. 2023), pp. 17824–17838.
DOI: 10.1109/JIOT.2023.3280393. URL: https://hal.science/hal-04119710.

[34] L. Picasarri-Arrieta. ‘Strengthening the Directed Brooks’ Theorem for oriented graphs and con-
sequences on digraph redicolouring’. In: Journal of Graph Theory (6th Dec. 2023). DOI: 10.1002/j
gt.23066. URL: https://inria.hal.science/hal-04337440.

International peer-reviewed conferences

[35] R. A. Alliche, T. da Silva Barros, R. Aparicio-Pardo and L. Sassatelli. ‘prisma-v2: Extension to Cloud
Overlay Networks’. In: ICTON 2023 - 23rd International Conference on Transparent Optical Net-
works. Bucarest, Romania: IEEE, 2nd July 2023. DOI: 10.1109/ICTON59386.2023.10207272. URL:
https://hal.science/hal-04135985.

[36]

[37]

[38]

J. Araujo, F. Havet, C. L. Sales, K. Suchan and N. Nisse. ‘Semi-proper orientations of dense graphs’.
In: LAGOS 2023 6 XII Latin-American Algorithms, Graphs and Optimization Symposium. Vol. 223.
Huatulco, Mexico, 2023, pp. 231–240. DOI: 10.1016/j.procs.2023.08.233. URL: https://hal
.science/hal-04304901.

J. Bensmail, V. Campos, A. K. Maia, N. Nisse and A. Silva. ‘Deciding the Erd˝os-Pósa property in
3-connected digraphs’. In: WG 2023 - 49th International Workshop on Graph-Theoretic Concepts
in Computer Science. LNCS. Fribourg (CH), Switzerland, 28th June 2023. URL: https://inria.ha
l.science/hal-04084227.

J. Bensmail, H. Hocquard and P.-M. Marcille. ‘The Weak (2,2)-Labelling Problem for graphs with
forbidden induced structures’. In: Lecture Notes in Computer Science. CALDAM 2023 - 9th Annual
International Conference on Algorithms and Discrete Applied Mathematics. Gandhinagar, India:
Springer, 9th Feb. 2023. DOI: 10.1007/978-3-031-25211-2_16. URL: https://hal.science/h
al-03869508.

[39] A. Carvalho Walraven da Cunha, F. d’Amore and E. Natale. ‘Polynomially Over-Parameterized
Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets’. In: 37th
Conference on Neural Information Processing Systems (NeurIPS 2023). New Orleans, United States,
10th Dec. 2023. URL: https://hal.science/hal-04143024.

[40] A. Carvalho Walraven da Cunha, E. Natale and L. Viennot. ‘Neural Network Information Leakage
through Hidden Learning’. In: Communications in Computer and Information Science (CCIS) series.
OLA2023 - International Conference on Optimization and Learning. Vol. 1824. Communications in
Computer and Information Science. Malaga, Spain: Springer Nature Switzerland, 27th Feb. 2023,
pp. 117–128. DOI: 10.1007/978-3-031-34020-8_8. URL: https://hal.science/hal-031571
41.

46

Inria Annual Report 2023

[41] A. da Cunha, D. Rivet, E. Natale and A. Rossi. ‘Une implémentation GPU de la méthode de recherche
approximative FlyHash’. In: CAID 2023 - 5e Conference on Artificial Intelligence for Defense. Actes
de la conférence CAID 2023. Rennes, France, 22nd Nov. 2023. URL: https://hal.science/hal-0
4328529.

[42] A. C. W. da Cunha, F. d’Amore, F. Giroire, H. Lesfari, E. Natale and L. Viennot. ‘Revisiting the Random
Subset Sum problem’. In: 31st Annual European Symposium on Algorithms (ESA 2023). 31st Annual
European Symposium on Algorithms (ESA 2023). Amsterdam, Netherlands: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 4th Sept. 2023, 37:1–37:11. DOI: 10.4230/LIPIcs.ESA.2023.37.
URL: https://hal.science/hal-03654720.

[43] C. Di Giusto, D. Ferré, E. Lozes and N. Nisse. ‘Weakly Synchronous Systems with Three Machines Are
Turing Powerful’. In: Lecture Notes in Computer Science. RP 2023 - 17th International Conference on
Reachability Problems. Vol. LNCS-14235. Reachability Problems 17th International Conference, RP
2023, Nice, France, October 11–13, 2023, Proceedings. Nice, France: Springer Nature Switzerland,
5th Oct. 2023, pp. 28–41. DOI: 10.1007/978-3-031-45286-4_3. URL: https://hal.science/h
al-04273451.

[44] T. Dissaux, F. Fioravantes, H. Gahlawat and N. Nisse. ‘Recontamination Helps a Lot to Hunt a
Rabbit’. In: Leibniz International Proceedings in Informatics (ISSN 1868-8969). MFCS 2023 - 48th
International Symposium on Mathematical Foundations of Computer Science. Vol. LIPICS-272.
48th International Symposium on Mathematical Foundations of Computer Science. Bordeaux,
France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, 42:1–42:14. DOI: 10.4230/LIPIc
s.MFCS.2023.42. URL: https://hal.science/hal-04271418.

[45]

J. Duron, F. Havet, F. Hörsch and C. Rambaud. ‘On the minimum number of inversions to make
a digraph k-(arc-)strong’. In: MUNI journals. EUROCOMB 2023 - European Conference on Com-
binatorics, Graph Theory and Applications. Proceedings of the 12th European Conference on
Combinatorics, Graph Theory and Applications. Prague, Czech Republic: Masaryk University Press;
Masaryk University Press, 28th Aug. 2023, pp. 386–392. DOI: 10.5817/CZ.MUNI.EUROCOMB23-054.
URL: https://hal.science/hal-04352250.

[46] F. Giroire, N. Nisse, K. Ohulchanskyi, M. Sulkowska and T. Trolliet. ‘Preferential attachment hyper-
graph with vertex deactivation’. In: IEEE Computer society digital library. MASCOTS 2023 - 31st
International Symposium on the Modeling, Analysis, and Simulation of Computer and Telecom-
munication Systems. Vol. 2023. 2023 31th International Symposium on Modeling, Analysis, and
Simulation of Computer and Telecommunication Systems (MASCOTS). New York, United States,
16th Oct. 2023. URL: https://hal.science/hal-04372316.

[47] F. Havet, L. Picasarri-Arrieta and C. Rambaud. ‘On the Minimum Number of Arcs in 4-Dicritical
Oriented Graphs’. In: Lecture Notes in Computer Science. WG 2023 - International Workshop on
Graph-Theoretic Concepts in Computer Science. Vol. LNCS-14093. Graph-Theoretic Concepts
in Computer Science 49th International Workshop, WG 2023, Fribourg, Switzerland, June 28–30,
2023, Revised Selected Papers. Fribourg, Switzerland: Springer, 28th June 2023, pp. 376–387. DOI:
10.1007/978-3-031-43380-1_27. URL: https://hal.science/hal-04352253.

[48] M. Heusse and C. Caillouet. ‘Adjusting the Redundancy Level of LoRaWAN transmissions’. In: CoRes
2023 - 8èmes Rencontres Francophones sur la Conception de protocoles, l’évaluation de performances
et l’expérimentation de Réseaux de communication. CoRes 2023 - 8èmes Rencontres Francophones
sur la Conception de protocoles, l’évaluation de performances et l’expérimentation de Réseaux de
communication. Cargese, France, 22nd May 2023. URL: https://hal.science/hal-04090723.

[49] L. Hogie. ‘A Decentralized Web Service Infrastructure for the Interoperability of Applications in
Multihop Dynamic Networks’. In: CIoT 2023 - 6th Conference on Cloud and Internet of Things.
Lisbon, Portugal: IEEE, 20th Mar. 2023, pp. 211–218. DOI: 10.1109/CIoT57267.2023.10084876.
URL: https://hal.science/hal-04075895.

Project COATI

47

[50] Z. Ma, F. Giroire, G. Urvoy-Keller and S. Roubia. ‘Q-learning for Waiting Time Control in CDN/V2V
Live streaming’. In: 2023 IFIP Networking Conference (IFIP Networking). Vol. 2023. 2023 IFIP
Networking Conference (IFIP Networking). Barcelona, Spain: IEEE, 12th June 2023, pp. 1–9. DOI:
10.23919/IFIPNetworking57963.2023.10186429. URL: https://inria.hal.science/hal-
04309215.

[51] L. Picasarri-Arrieta. ‘Strengthening the Directed Brooks’ Theorem for oriented graphs and con-
sequences on digraph redicolouring’. In: Eurocomb 2023 - 12th European Conference on Combinat-
orics, Graph Theory and Applications. Eurocomb 2023 - 12th European Conference on Combin-
atorics, Graph Theory and Applications. Prague, Czech Republic: Masaryk University Press, 2023,
pp. 760–765. DOI: 10.5817/CZ.MUNI.EUROCOMB23-105. URL: https://hal.science/hal-042
04446.

[52] A. Rossi, S. Deslauriers-Gauthier and E. Natale. ‘Temporal Hyperbolic Graphs as Null Models for
Brain Dynamics’. In: Temporal Hyperbolic Graphs as Null Models for Brain Dynamics. The 12th
International Conference on Complex Networks and their Applications - CNA 2023. Menton, France,
28th Nov. 2023. URL: https://hal.science/hal-04343066.

[53] F. Tabatabaeimehr, L. Velasco, M. Ruiz, H. Khalili and R. Aparicio-Pardo. ‘Dynamic Traffic Predic-
tion Model Retraining for Autonomous Network Operation’. In: ICTON 2023 - 23rd International
Conference on Transparent Optical Networks. Bucharest, Romania: IEEE, 2nd July 2023. DOI:
10.1109/ICTON59386.2023.10207375. URL: https://hal.science/hal-04135969.

National peer-reviewed Conferences

[54]

[55]

J.-C. Bermond, M. Cosnard, D. Coudert and F. Havet. ‘Groupage sur le chemin pour borner la largeur
de coupe’. In: AlgoTel 2023 - 25èmes Rencontres Francophones sur les Aspects Algorithmiques des
Télécommunications. Cargese, France, 2023, p. 4. URL: https://inria.hal.science/hal-040
76999.

I. Dias da Silva, Y. Busnel and C. Caillouet. ‘Optimisation de plan de vol de drones autonomes
pour une recharge rapide de capteurs’. In: AlgoTel 2023 - 25èmes Rencontres Francophones sur les
Aspects Algorithmiques des Télécommunications. AlgoTel 2023 - 25èmes Rencontres Francophones
sur les Aspects Algorithmiques des Télécommunications. Cargese, France, 22nd May 2023. URL:
https://hal.science/hal-04087105.

Conferences without proceedings

[56] P. Crescenzi, H. Lesfari, E. Natale, A. Rossi and P. Serafim. ‘Un framework open-source écrit en Julia
pour la modélisation d’évaluation globale intégrée’. In: ROADEF 2023 - 24ème édition du congrès
annuel de la société française de recherche opérationnelle et d’aide à la décision. Rennes, France,
20th Feb. 2023. DOI: 10.5281/zenodo.7093581. URL: https://hal.science/hal-04008491.

Doctoral dissertations and habilitation theses

[57]

I. Dias da Silva. ‘Optimization of UAVs deployment and coordination for exploration and monitoring
applications’. Université Côte d’Azur, 21st Sept. 2023. URL: https://theses.hal.science/tel-
04257344.

[58] T. Dissaux. ‘Graph decompositions : treelength and pursuit-evasion games’. Université Côte d’Azur,

25th Sept. 2023. URL: https://theses.hal.science/tel-04282042.

Reports & preprints

[59] P. Aboulker, T. Bellitto, F. Havet and C. Rambaud. On the minimum number of arcs in k-dicritical

oriented graphs. 28th July 2022. URL: https://hal.science/hal-03985818.

[60] O. Baudon, J. Bensmail and M. Boivin. Interplays between variations of arbitrarily partitionable
graphs under minimality constraints. Université côte d’azur; Université de Bordeaux, 2023. URL:
https://hal.science/hal-04260165.

48

[61]

[62]

[63]

[64]

[65]

[66]

[67]

Inria Annual Report 2023

J. Bensmail. Arbitrarily Edge-Partitionable Graphs. 19th Jan. 2024. URL: https://hal.science/h
al-04405426.

J. Bensmail. Toughness Properties of Arbitrarily Partitionable Graphs. Université côte d’azur, 2023.
URL: https://hal.science/hal-04312057.

J. Bensmail, T. Filasto, H. Hocquard and P.-M. Marcille. Irregularity Notions for Digraphs. Université
côte d’azur; Université de bordeaux; Université paris saclay, 2023. URL: https://hal.science/h
al-04210649.

J. Bensmail, H. Hocquard and P.-M. Marcille. Adding Direction Constraints to the 1-2-3 Conjecture.
Université côte d’azur; Université de Bordeaux, 2023. URL: https://hal.science/hal-0390026
0.

J. Bensmail, H. Hocquard, P.-M. Marcille and S. Meyer. On 1-2-3 Conjecture-like problems in 2-
edge-coloured graphs. Université côte d’azur; Université de bordeaux; ENS Paris - Ecole Normale
Supérieure de Paris, 2023. URL: https://hal.science/hal-04223866.

S. Bessy, J. Bang-Jensen and L. Picasarri-Arrieta. Constrained Flows in Networks. 2nd Oct. 2023. URL:
https://inria.hal.science/hal-04379871.

S. Bessy, F. Havet and L. Picasarri-Arrieta. Dichromatic number of chordal graphs. 29th Sept. 2023.
URL: https://inria.hal.science/hal-04379896.

[68] N. Bousquet, F. Havet, N. Nisse, L. Picasarri-Arrieta and A. Reinald. Digraph redicolouring. Inria,

2nd Oct. 2023. URL: https://hal.science/hal-04281467.

[69] D. Coudert, S. Coulomb and G. Ducoffe. Leanness Computation: Small Values and Special Graph

Classes. 12th Nov. 2023. URL: https://hal.science/hal-04281128.

[70] P. Crescenzi, E. Natale, A. Rossi and P. B. Serafim. WorldDynamics.jl: A Julia Package for Developing
and Simulating Integrated Assessment Models. 5th June 2023. URL: https://hal.science/hal-0
4117509.

[71] P. Crescenzi, A. Rossi and E. Natale. An open source implementation of the Earth4All integrated

assessment model. 18th Nov. 2023. URL: https://hal.science/hal-04293350.

[72] A. da Cunha, E. Natale, D. Rivet and A. Rossi. Une implémentation GPU de l’algorithme FlyHash:
Des mouches plus rapides pour la fouille de données massives. INRIA; CNRS; I3S; Université Côte
d’Azur, 2023. URL: https://hal.science/hal-03987919.

[73] T. Dissaux, F. Fioravantes, H. Galhawat and N. Nisse. Further results on the Hunters and Rabbit
game through monotonicity. Inria - Sophia Antipolis, 18th Feb. 2023. URL: https://hal.science
/hal-03995642.

[74]

J. Moulierac, G. Urvoy-Keller, M. Dinuzzi and Z. Ma. What is the carbon footprint of one hour of video
streaming? Université Côte d’Azur, 3rd Apr. 2023. URL: https://hal.science/hal-04069500.

[75] N. Nisse, L. Picasarri-Arrieta and I. Sau. Redicolouring digraphs: directed treewidth and cycle-

degeneracy. Inria, 13th July 2023. URL: https://hal.science/hal-04271445.

[76] L. Picasarri-Arrieta and M. Stiebitz. Minimum number of arcs in k-critical digraphs with order at

most 2k − 1. 5th Oct. 2023. URL: https://inria.hal.science/hal-04379883.

Other scientific publications

[77] A. Rossi. ‘Temporal Graph Neural Networks with GraphNeuralNetworks.jl’. In: Julia and Optimiza-
tion Days 2023. Paris, France, 4th Oct. 2023. URL: https://hal.science/hal-04230797.

[78] A. Rossi, S. Deslauriers-Gauthier and E. Natale. Temporal Brain Networks Database. 2nd Mar. 2023.

DOI: 10.57745/PR8VUV. URL: https://hal.science/hal-04011895.

[79] A. Rossi, E. Natale and S. Deslauriers-Gauthier. ‘Temporal Brain Networks Dataset’. In: NeuroMod

meeting 2023. Antibes, France, 28th June 2023. URL: https://hal.science/hal-04130380.

Project COATI

49

12.3 Cited publications

[80]

[SW REL.] R. A. Alliche, T. da Silva Barros, R. Aparicio-Pardo and L. Sassatelli, Packet Routing
Simulator for Multi-Agent Reinforcement Learning (PRISMA) (Version v0.1) version v0.1, May 2022.
LIC: GNU General Public License version 2. DOI: 10.5281/zenodo.7660362, HAL: 〈hal-0399884
2v1〉, URL: https://hal.science/hal-03998842, VCS: https://github.com/rapariciopar
do/PRISMA, SWHID: 〈swh:1:dir:53e77bdd5593e2ef85805c8520626cfddb113fa9;origin=h
ttps://hal.archives-ouvertes.fr/hal-03998842;visit=swh:1:snp:c4feb2a2b2254e4
1f7187021d2905e65d12d07a6;anchor=swh:1:rel:29f812793e523375296b6ff52ffc50ce6
8250a98;path=/〉.

[81] R. A. Alliche, T. da Silva Barros, R. Aparicio-Pardo and L. Sassatelli. ‘PRISMA: A Packet Routing
Simulator for Multi-Agent Reinforcement Learning’. In: 4th Intl Workshop on Network Intelligence
collocated with IFIP Networking 2022. Proceedings IFIP Networking Conferance 2022. Catania,
Italy, June 2022. DOI: 10.23919/IFIPNetworking55013.2022.9829797. URL: https://hal.sc
ience/hal-03709948.

[82]

S. Angelopoulos, N. Nisse and D. M. Thilikos. ‘Preface to special issue on Theory and Applications
of Graph Searching’. In: Theoretical Computer Science 794 (Nov. 2019), pp. 1–2. DOI: 10.1016/j.tc
s.2019.09.043. URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-02342745.

[83] D. Balouek, A. C. Amarie, G. Charrier, F. Desprez, E. Jeannot, E. Jeanvoine, A. Lèbre, D. Margery,
N. Niclausse, L. Nussbaum, O. Richard, C. Perez, F. Quesnel, C. Rohr and L. Sarzyniec. ‘Adding
Virtualization Capabilities to the Grid’5000 Testbed’. In: Cloud Computing and Services Science. Ed.
by I. I. Ivanov, M. van Sinderen, F. Leymann and T. Shan. Cham: Springer International Publishing,
2013, pp. 3–20.

[84]

[85]

[86]

J. Bang-Jensen and S. Bessy. ‘(Arc-)disjoint flows in networks’. In: Theoretical Computer Science 526
(2014), pp. 28–40. DOI: https://doi.org/10.1016/j.tcs.2014.01.011. URL: https://www.s
ciencedirect.com/science/article/pii/S0304397514000280.

J. Bang-Jensen, F. Havet and A. Yeo. ‘The complexity of finding arc-disjoint branching flows’. In:
Discrete Applied Mathematics 209 (2016). 9th International Colloquium on Graph Theory and
Combinatorics, 2014, Grenoble, pp. 16–26. DOI: https://doi.org/10.1016/j.dam.2015.10.0
12. URL: https://www.sciencedirect.com/science/article/pii/S0166218X15004990.

J. Bensmail, F. Fioravantes, F. Mc Inerney and N. Nisse. ‘The Largest Connected Subgraph Game’.
In: WG 2021 - The 47th International Workshop on Graph-Theoretic Concepts in Computer Science.
Vol. 12911. Lecture Notes in Computer Science. Warsaw, Poland: Springer, June 2021, pp. 296–307.
DOI: 10.1007/978-3-030-86838-3\_23. URL: https://inria.hal.science/hal-03219636.

[87] F. V. Fomin, P. Fraigniaud, N. Nisse and D. M. Thilikos. Forewords: Special issue on Theory and
Applications of Graph Searching Problems. Vol. 655. Part A. Elsevier, Dec. 2016. DOI: 10.1016/j.tc
s.2016.11.001. URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483703.

[88] A. O. Mohammed, F. F. Dragan and H. M. Guarnera. ‘Fellow Travelers Phenomenon Present in Real-
World Networks’. In: 10th International Conference on Complex Networks and Their Applications
COMPLEX NETWORKS 2021. Vol. 1015. Studies in Computational Intelligence. Springer, 2021,
pp. 194–206. DOI: 10.1007/978-3-030-93409-5\_17. URL: https://doi.org/10.1007/978-
3-030-93409-5%5C_17.

[89]

J. Y. Yen. ‘Finding the k Shortest Loopless Paths in a Network’. In: Management Science 17.11 (1971),
pp. 712–716. DOI: 10.1287/mnsc.17.11.712.
<scratchpad>
- Main topic: COATI (Combinatorics, Optimization and Algorithms for Telecommunications) project-team
- Key points:
  - Focus on designing networks and communication algorithms
  - Research fields: Algorithmics, Discrete Mathematics, and Combinatorial Optimization
  - Applications: telecommunications networks, social networks, and other areas
  - Collaborations with industry partners, universities, and other research teams
- Structure: The document is divided into several sections, including project-team information, research program, application domains, social and environmental responsibility, and collaborations with other fields.
- Potential artifacts to ignore: web-related elements, such as links, HTML tags, and unnecessary text
</scratchpad>

<final_summary>
The COATI project-team focuses on designing networks and communication algorithms, with a strong emphasis on algorithmics, discrete mathematics, and combinatorial optimization. The team's research has applications in telecommunications networks, social networks, and other areas, and they collaborate with industry partners, universities, and other research teams to advance their work. The COATI project-team is committed to sustainability and social responsibility, with initiatives such as evaluating the environmental impact of their research activities and promoting scientific activities to disseminate their domain knowledge to a general audience. Overall, the COATI project-team is dedicated to advancing the field of telecommunications networks and optimization problems through innovative research and collaboration.
The COATI project-team focuses on designing networks and communication algorithms, with a strong emphasis on algorithmics, discrete mathematics, and combinatorial optimization. The team's research has applications in telecommunications networks, social networks, and other areas, and they collaborate with industry partners, universities, and other research teams to advance their work. The COATI project-team is committed to sustainability and social responsibility, with initiatives such as evaluating the environmental impact of their research activities and promoting scientific activities to disseminate their domain knowledge to a general audience. Overall, the COATI project-team is dedicated to advancing the field of telecommunications networks and optimization problems through innovative research and collaboration.