AlDyNet
Algorithm for large and Dynamic Networks
Programme INRIA “Equipes Associées” 20132015, extended for three years 20162018
Team project INRIA : COATI  Foreign Partner: Universidad Adolfo Ibáñez, Santiago 
Centre de recherche INRIA Sophia Antipolis — Méditerranée
Thème INRIA : Com B 
Country: Chile 
French coordinator  Chilean coordinator  

Name, surname  Nicolas Nisse  Karol Suchan 
Title  Chargé de recherche Inria (Research officer)  Assistant professor 
Institution  teamproject COATI, common team INRIA Sophia Antipolis – I3S (UMR 7271 of the CNRS and the University of NiceSophia Antipolis) 
Adolfo Ibáñez University Facultad de Ingeniería y Ciencias Santiago, Chile. 
Address 
Projet COATI, commun Inria, I3S(CNRS/UNSA)
INRIA SophiaAntipolis 2004, route des Lucioles — B.P. 93 06902 SophiaAntipolis Cedex France 
Universidad Adolfo Ibáñez
Av. Diagonal Las Torres 2640, Oficina 215B Peñalolén 7941169, Santiago Chile 
URL  http://wwwsop.inria.fr/members/Nicolas.Nisse/  http://www.uai.cl/docentes/karolsuchan 
Phone  +33 4 97 15 53 28  +56 2 3311533 
name dot surname arobase inria dot fr  name dot surname arobase uai dot cl 
Activity reports
 Second phase (20162018)
 Final report on first phase (20132015) and Presentation
Participants
 Inria: David Coudert, Guillaume Ducoffe (former Ph.D. student, defended December 2016), Frédéric Giroire, Fionn McInerney (Ph.D. student, since Oct. 2016), Fatima Zahra Moataz (former Ph.D. student, defended Oct. 2015), Nicolas Nisse, Stéphane Pérennes, Bi Li (former Ph.D. student, defended Nov. 2014), Ronan Pardo Soares (former Ph.D. student, defended Nov. 2013)
 Adolfo Ibáñez: Marcos Goycoolea, Eduardo Moreno, Esteban Roman (former Ph.D. student), Karol Suchan, José Merino (former student)
 Associated members at DIM and CMM, Univ. de Chile: Marcos Kiwi, JuanCarlos Maureira, Mauricio Soto (former member).
Documents
Visits in 2017
 Chile to France
 Karol Suchan: February 10th to 25th, 2017.
 France to Chile
 David Coudert: November 17th to December 1st, 2017.
D. Coudert gave a seminar on November 23rd, 2017 at Univ. Adolfo Ibáñez, on the Flinders Hamiltonian Cycle Problem Challenge.  Fionn Mc Inerney: November 17th to December 1st, 2017.
F. Mc Inerney gave a seminar on November 30th, 2017 at Univ. Adolfo Ibáñez, on Spy Games in Graphs.  Nicolas Nisse: November 17th to December 1st, 2017.
N. Nisse gave a seminar on November 21st, 2017 at Univ. Adolfo Ibáñez, on Maintaining Balanced Trees For Structured Distributed Streaming Systems.
 David Coudert: November 17th to December 1st, 2017.
Publications of the Project
International journals

Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, and Karol Suchan. On interval number in cycle convexity.
To appear in Discrete Maths. and Theoretical Computer Science (DMTCS). 2018. 
David Coudert, Guillaume Ducoffe, Nicolas Nisse, and Mauricio Soto. Distancepreserving orderings in graphs.
To appear in Discrete Applied Maths. 2018. 
Bi Li, Fatima Zahra Moataz, Nicolas Nisse and Karol Suchan, Minimum Size TreeDecompositions.
To appear in Discrete Applied Maths, 2017. 
Frédéric Giroire and JuanCarlos Maureira. Analysis of the Failure Tolerance of Linear Access Networks.
IEEE Transactions on Intelligent Transportation Systems, 19(4): 11661175 (2018) 
Sahel Sahhaf, Wouter Tavernier, Dimitri Papadimitriou, Davide Careglio, Alok Kumar, Christian Glacet, David Coudert, Nicolas Nisse, Lluis Fàbrega, Pere Vilà, Miguel Camelo, Pieter Audenaert, Didier Colle, Piet Demeester. Routing at Large Scale: Advances and Challenges for Complex Networks.
IEEE Network, Institute of Electrical and Electronics Engineers, 2017, pp.12 – 22. 
Lélia Blin, Janna Burman and Nicolas Nisse. Exclusive Graph Searching.
Algorithmica, Volume 77(3), pages 942969, 2017. 
Euripides Markou, Nicolas Nisse and Stéphane Pérennes. Exclusive Graph Searching vs. Pathwidth.
Information and Computation, Volume 252, pages 243260, 2017 
Gianlorenzo D’Angelo, Alfredo Navarra and Nicolas Nisse. Gathering and Exclusive Searching on Rings under Minimal Assumptions.
Distributed Computing, Volume 30(1), pages 1748, 2017.  Nathann Cohen, David Coudert, Guillaume Ducoffe, and Aurélien Lancin. Applying cliquedecomposition for computing Gromov hyperbolicity. Theoretical Computer Science, Elsevier, 2017, 690, pp.114139
 Nicolas Nisse, Ronan Pardo Soares: On the monotonicity of process number.
Discrete Applied Mathematics 210: 103111 (2016) 
David Coudert, Dorian Mazauric, Nicolas Nisse: Experimental Evaluation of a BranchandBound Algorithm for Computing Pathwidth and Directed Pathwidth.
ACM Journal of Experimental Algorithmics 21(1): 1.3:11.3:23 (2016) 
David Coudert, Guillaume Ducoffe, Nicolas Nisse: To Approximate Treewidth, Use Treelength!
SIAM J. Discrete Math. 30(3): 14241436 (2016) 
Gianlorenzo D’Angelo, Gabriele Di Stefano, Alfredo Navarra, Nicolas Nisse and Karol Suchan.
Computing on rings by oblivious robots: a unified approach for different tasks.
Algorithmica, Volume 72(4), pages 10551096, 2015. 
Florent Becker, Adrian Kosowski, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, and Ioan Todinca.
Allowing each node to communicate only once in a distributed system: shared whiteboard models.
Distributed Computing, Volume 28(3), pages 189200, 2015. 
Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan. kChordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
Algorithmica, Volume 72(3), pages 758777, 2015. 
Serge Gaspers, Mathieu Liedloff, Maya Stein and Karol Suchan. Complexity of Splits Reconstruction for LowDegree Trees.
Discrete Applied Mathematics, Volume 180, pages 89100 (2015) 
Julio Araujo, Nicolas Nisse and Stéphane Pérennes. Weighted Coloring in Trees.
SIAM J. Discrete Math. 28(4): 20292041 (2014)  David Coudert, Guillaume Ducoffe. On the recognition of \(C_4\)free and \(1/2\)hyperbolic graphs.
SIAM J. Discrete Math. 28(3): 16011617 (2014)
International conferences
 David Coudert, James Luedtke, Eduardo Moreno and Konstantinos Priftis. Computing and maximizing the exact reliability of wireless backhaul networks. In proceedings of International Network Optimization Conference (INOC), https://hal.inria.fr/hal01394593, 2017.
 David Coudert and Guillaume Ducoffe. A simple approach for lowerbounding the distortion in any Hyperbolic embedding. European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’17), Electronic Notes in Discrete Mathematics, 61, pp.293 – 299, 2017.
 Nathann Cohen, Fionn McInerney, Nicolas Nisse and Stéphane Pérennes. Study of a combinatorial game in graphs through Linear Programming. To appear in Proceedings of 28th International Symposium on Algorithms and Computation (ISAAC), 2017.

Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse: On the Complexity of Computing Treebreadth.
In 27th International Workshop on Combinatorial Algorithms (IWOCA 2016): LNCS 9843, Springer, 315, 2016. 
Frédéric Giroire and JuanCarlos Maureira. Analysis of the Failure Tolerance of Linear Access Networks.
IEEE Global Communications Conference (GLOBECOM), 2016 
Mamadou M. Kante, Fatima Zahra Moataz, Benjamin Momège and Nicolas Nisse, Finding Paths in Grids with Forbidden Transitions.
In 41st International Workshop on GraphTheoretic Concepts in Computer Science (WG), LNCS, Springer, 2015. 
Bi Li, Fatima Zahra Moataz, Nicolas Nisse and Karol Suchan, Minimum Size TreeDecompositions.
In 8th LatinAmerican Algorithms, Graphs and Optimization Symposium (LAGOS), 2015. 
David Coudert, Dorian Mazauric and Nicolas Nisse. Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth.
In 13rd Symposium on Experimental Algorithms (SEA), LNCS, Springer, pages 4658, 2014. 
Julio Araujo, Nicolas Nisse and Stéphane Pérennes. Weighted Coloring in Trees.
31st Symposium on Theoretical Aspects of Computer Science (STACS), Schloss Dagstuhl, pages 7586, 2014. 
Bi Li, Fatima Zahra Moataz, Nicolas Nisse and Karol Suchan, Minimum Size TreeDecompositions.
Extended abstract in 9th International colloquium on graph theory and combinatorics (ICGT), 2014 (no Proceedings). [Research Report], 2014, pp. 23. hal01074177  Gianlorenzo D’Angelo, Alfredo Navarra and Nicolas Nisse. Gathering and Exclusive Searching on Rings under Minimal Assumptions. In Proceedings of the 15th International Conference on Distributed Computing and Networking (ICDCN), LNCS, Springer, pages 149164, 2014.
 Gianlorenzo D’Angelo, Gabriele Di Stefano, Alfredo Navarra, Nicolas Nisse and Karol Suchan. A unified approach for different tasks on rings in robotbased computing systems. In Proceedings of the 15th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), IEEE, 2013.
 Nicolas Nisse and Ronan Soares. On the monotonicity of Process Number. In Proceedings of 7th LatinAmerican Algorithms, Graphs and Optimization Symposium (LAGOS), Elsevier, to appear in Electronic Note Discrete Maths, 2013.
Research Reports
 David Coudert, Marcos Kiwi, and Dieter Mitsche. On the hyperbolicity of random hyperbolic graphs. In preparation.
 Patricio Rodríguez, Ricardo Truffello, Karol Suchan, Francisca Varela, Manuel Matas, Javier Mondaca, Javiera Céspedes, Luis Valenzuela, Juan Pablo Valenzuela and Claudio Allende, Apoyando la formulación de políticas públicas y toma de decisiones en educación utilizando técnicas de análisis de datos masivos : el caso de Chile,
 Patricio Rodríguez, Juan Pablo Valenzuela, Karol Suchan, Ricardo Truffello and Nicol Norel, Determinando el acceso real de los estudiantes a establecimientos educacionales efectivos para generar políticas públicas que mejoren la provisión de educación de calidad.
Theses
 Marko Oleksiyenko, Bicycleoriented itinerary computation for smart cities. Master thesis, Univ. Nice Sophia Antipolis, MarchAugust, 2017.
 Guillaume Ducoffe. Propriétés métriques des grands graphes. Ph.D. thesis, Univ. Nice Sophia Antipolis, December 9th, 2016.
 Vladislav Zaika, Optimizing the transport network of a large metropolitan area to improve citizen accessibility. Master thesis, Univ. Nice Sophia Antipolis, MarchAugust, 2016.
 Fatima Zahra Moataz. Towards Efficient and FaultTolerant Optical Networks: Complexity and Algorithms. Ph.D. thesis, Univ. Nice Sophia Antipolis, October 30th, 2015.
 Nicolas Nisse, Algorithmic complexity: Between Structure and Knowledge How Pursuitevasion Games help. HDR, Univ. Nice Sophia Antipolis, May 26th, 2014.
 Bi Li, Tree Decompositions and Routing Problems. Ph.D. thesis, Univ. Nice Sophia Antipolis, November 12th, 2014.
 Esteban Roman Catafau, Analysis of a Branch and Bound algorithm for pathwidth, internship report, MayJuly 2014.
 Klaus Jaschan, Implementing a Vertex Separation algorithm for trees in Sagemath, internship report, Dec. 2013 Feb. 2014.
 Ronan Soares, Pursuitevasion, decompositions and convexity on graphs. Ph.D. thesis, Univ. Nice Sophia Antipolis, November 8th, 2013.
Related Links
 Apoyando la formulación de políticas públicas y toma de decisiones en educación
 Investigadores INRIA y UAI trabajarán en conjunto
Scientific programme and objectives
Context: Current evolution of telecommunication networks leads to new algorithmic challenges. Indeed, both the size of networks as well as the amount of traffic in such networks grow drastically. In this context, numerous problems become challenging to solve even if there exist algorithms that are suitable for smaller networks (in general nnode graphs, algorithms of running time \(O(n^4)\) are not scalable to networks of size \(n=10^4\); at \(n=10^5\) even \(O(n^3)\) is impractical). Therefore, solutions proposed so far do not scale up and new alternatives must be provided. On the one hand, recent results have proposed to design algorithms that take advantage of special structural properties often found in largescale networks to achieve better performances. Indeed, it is well known that many telecommunication, social, and biological networks share structural properties such as logarithmic diameter, powerlaw degree distribution and high clustering coefficient. These properties can be exploited for algorithmic purposes (e.g., for routing). On the other hand, centralized solutions proposed so far do not allow to efficiently face the dynamicity of these networks (variations of both topology and state of connections). Moreover, another important aspect of some of the new networks is that they are not defined in a global way (but, e.g., social networks are defined through local interactions). Hence, it is interesting to propose distributed or even localized solutions, i.e., algorithms based on information that can be retrieved locally and in a distributed way. Many recent works study the tradeoffs between the power of communication and the kind of structural properties that can be computed.
Objectives: The main goal of this Associate Team is to study the structure of networks (modeled by graphs) to design both efficient distributed algorithms and reliable network topologies suitable to applications. We are interested both in largescale (Facebook, Internet, etc.) and in smaller networks (e.g., WDM) that handle heavy traffic. More precisely, we aim at designing new techniques of distributed and localized computing to test structural properties of networks and to compute structures (e.g., decompositions) to be used in applications. Concerning the applications, we will first focus on routing and subgraph packing problems.
There are two main objectives:
 Find efficient localized algorithms to test certain graph properties or to prove that no such algorithms exist. We will formalize several distributed computing models and analyze which properties can and which cannot be tested in them.
 Define graph properties – computable or approximable in distributed systems – such as structures/decompositions/representations. The driving idea is to combine several well studied graph properties in order to obtain more specific structures that we hope to be computable more easily.
To verify the practical efficiency of our results, the designed algorithms will be implemented and compared to existing ones. For this purpose, a particular effort will be put to design and implement algorithms to generate graphs that satisfy properties of interest, in order to use them to test the algorithms.
The originality of the proposal is to combine powerful tools of graphs theory (e.g., FPT complexity) and of combinatorial optimization (Mixed Integer Programming) with distributed computing. One challenge here is to balance between the degree of locality of desired algorithms and the relevance of properties that may be computed.
Workprogram
Last decade have shown promising advances in exploiting the structure of the underlying graph to solve hard problems efficiently. We propose to study structural properties of graphs with two main guidelines: to focus on specific graph classes and to keep in mind the algorithmic applications of the considered properties. We expect to find structures that could be computed easily (by greedy or localized algorithms) and that would allow to design efficient algorithms for important problems like routing or graph packing.
For this purpose, we want to first extend the classical centralized approaches to have a better understanding of graph structures:
 To continue the study of graphs decompositions: in particular, it is important to design simple algorithms to compute (or approximate) decompositions in particular graphs classes: for instance, graphs with small treewidth (generic algorithms of Bodlaender and Kloks being inefficient even in such graphs classes), subclasses of planar graphs (the complexity of computing treewidth of planar graphs is still open).
An approach that we will follow during the first year is the computation of such decompositions via integer programming, branch and bound and separation algorithms. Very few works have considered this direction.  To generalize this study to directed graphs: currently several groups of researchers (e.g., [Ganian et al. 2010]) aim at designing “good” decompositions for directed graphs, i.e., having the same algorithmic performances as treedecompositions in the undirected case.
Most of the graph characteristics used to improve the performances of algorithms are centralized and global structures. We aim at deriving simpler structures and graph characterizations that could be locally computable. In particular, we want to focus on information localized at vertices (or close neighborhoods) that suffices to compute structural properties that support efficient algorithms for applications, therefore:
 To focus on characterizations that may be efficiently computed and used in a distributed setting. For instance, in the case of treedecompositions, the size of the “pieces” of the decomposition is important to obtain efficient generic algorithms using dynamic programming. However, when we are interested in specific problems, it would be more relevant to consider the structure of the pieces instead of their size. For instance, preliminary results show that graphs with bounded chordality admit treedecompositions where each bag has a short dominating path. Moreover, such a decomposition can be computed by a greedy algorithm and has interesting applications for compact routing.
 To propose new characterizations for graphs satisfying a combination of classical properties. It will be crucial to design algorithms to check whether a graph satisfies these combinations, and to generate families of graphs satisfying them. A particular attention will be paid to properties and structures of realworld networks.