AlDyNet

Algorithm for large and Dynamic Networks

Programme INRIA “Equipes Associées” 2013-2015, extended for three years 2016-2018

 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 team-project COATI, common team
INRIA Sophia Antipolis – I3S (UMR 7271 of the CNRS and the University of Nice-Sophia Antipolis)
Santiago, Chile.
Projet COATI, commun Inria, I3S(CNRS/UNSA)

INRIA Sophia-Antipolis

2004, route des Lucioles — B.P. 93

06902 Sophia-Antipolis Cedex

France

Av. Diagonal Las Torres 2640, Oficina 215-B

Peñalolén 7941169, Santiago

Chile

URL http://www-sop.inria.fr/members/Nicolas.Nisse/ http://www.uai.cl/docentes/karol-suchan
Phone +33 4 97 15 53 28 +56 2 331-1533
email name dot surname arobase inria dot fr name dot surname arobase uai dot cl

Visits in 2017

• Chile to France
• France to Chile
• David Coudert: November 17th to December 1st, 2017.
D. Coudert gave a seminar on November 30th, 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 23rd, 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.

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 n-node 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 large-scale networks to achieve better performances. Indeed, it is well known that many telecommunication, social, and biological networks share structural properties such as logarithmic diameter, power-law 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 large-scale (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.

Work-program

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 tree-decompositions 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 tree-decompositions, 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 tree-decompositions 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 real-world networks.