Inria Associated Team AlDyNet

AlDyNet
Algorithm for large and Dynamic Networks
Programme INRIA "Equipes Associées" 2013-2015

Team project INRIA : COATI	Foreign Partner: Universidad Adolfo Ibáñez, Santiago
Centre de recherche INRIA : INRIA Sophia Antipolis 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 6070 of the CNRS and the University of Nice-Sophia Antipolis)	Adolfo Ibáñez University Facultad de Ingeniería y Ciencias Santiago, Chile.
Address	Projet COATI, commun Inria, I3S(CNRS/UNSA) INRIA Sophia-Antipolis 2004, route des Lucioles -- B.P. 93 06902 Sophia-Antipolis Cedex France	Universidad Adolfo Ibáñez 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.suchan.info/en_ksuchan.html
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

Participants

Inria: David Coudert, Frédéric Giroire, Bi Li (Ph.D. student) , Nicolas Nisse , Stéphane Pérennes , Ronan Pardo Soares (Ph.D. student)
Adolfo Ibáñez: Marcos Goycoolea, José Merino (student), Eduardo Moreno, Esteban Roman (Ph.D. student), Karol Suchan

Proposal and Common Publications

Publications of the Project

Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra, Nicolas Nisse and Karol Suchan. A unified approach for different tasks on rings in robot-based 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 Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), Elsevier, to appear in Electronic Note Discrete Maths, 2013.

Related Links

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 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.