AlDyNet — Bilan 2017

During the fifth year of the AlDyNet associated team between COATI and the Universidad Adolfo Ibáñez (Santiago, Chile), we have pursued ongoing research on the computation of graph properties related to hyperbolicity or graph convexity.
We have also worked on optimization problems having applications in wireless backhaul network, among others, to provide connectivity for wireless communications in buses or urban trains.
Finally, we have progressed in our implementations and simulations on the properties of the geographical network of Santiago.

  • On graph parameters.

    Gromov hyperbolicity is a graph parameter reflecting the metric structure of a graph. While this parameter can be computed in polynomial-time (super-cubic in the size of the graph), existing algorithms are not efficient for large graphs (thousand of vertices). We proposed an algorithm which is efficient in practice [1]. Hyperbolicity has important practical effects for routing in graphs [2], we also considered this aspect via particular embeddings of graphs [3]. Besides, we have also continued our work on graph convexity [4] that we started last year through AlDyNet.
    Graph parameters have an impact on the behavior (time-complexity) of algorithms for many problems. The theory of Parameterized complexity intends to formalize it through the design of Fixed Parameter Tractable algorithms (roughly, given a parameter k and on input of size n, an algorithm is FPT if its time-complexity is f(k)nO(1) for some computable function). Mostly NP-hard problems have been studied via this approach and, only recently, researchers have started to address problems in P. We also contributed to this hot topic [5].

  • On graph decompositions. Graph decompositions are a way to decompose graphs into small pieces (subsets of nodes) that are arranged in order to preserve the connectivity properties. They are widely used by dynamic programming algorithms (divide and conquer) in order to solve efficiently graph problems that are difficult in general. One prerequisite for running this kind of algorithms is the computation of good graph decompositions, which itself is a NP-hard problem.
    We have focused on the computation of tree-decompositions with minimum number of pieces [6]. Precisely, the maximum size of a piece being fixed, we aim at finding a decomposition of a graph minimizing the number of such pieces. This problem appears to be NP-hard in general graphs and the case of trees is still open [6].
    We also have worked on path-decompositions through their algorithmic interpretation, namely the Graph searching. Roughly, in Graph searching, we aim at computing the minimum number of mobile agents necessary to capture an invisible arbitrary fast intruder. A strategy of such a team of agents is equivalent to a path-decomposition of the graph. We consider a variant of Graph searching where two agents cannot occupy a vertex simultaneously [7]. This leads to the first model of Graph Searching whose complexity differs from the complexity of the classical model [8].
    We finally consider Graph Searching in a distributed setting [9], extending some previous work of the members of AlDyNet.
  • Optimization in telecommunication networks. We have considered several telecommunication networks such as Pair-to-Pair or wireless networks.
    We have studied live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. We propose and analyze simple localized algorithm to repair the diffusion tree to allow an efficient data distribution [10]. N. Nisse will do a seminar on this topic at University Adolfo Ibañez on November 21st 2017.
    We also pursued our study on the reliability of backhaul networks. we provide an algorithm to compute the exact reliability of a backhaul network, given a discrete probability distribution on the possible capacities available at each link. We also have studied the impact of some specific routing constraints (e.g., mono-routing, load balancing, stretch) on the design and reliability of the networks [11].
    Finally, our previous work on the disconnection of a moving vehicle from a linear Wireless access network has been published in an international revue [12].
  • On Eternal Domination in graphs. During the visit of Karol Suchan (February 2017), we have mainly worked on a game on graphs introduced by members of AlDyNet [13] (Fionn Mc Inerney will do a seminar on this topic at University Adolfo Ibañez on November 23rd 2017). This game is closely related to Dominating sets in graph (a set of vertices is a dominating set if every vertex of the graph either belong to this set or is a neighbor of an element of this set) and Eternal Domination. We will continue this study during the visit of COATI members to University Adolfo Ibañez (November 17th to December 1st, 2017).
  • Optimization in geographical networks We aim at considering transportation networks of medium-size cities in order to see the performances of various routing or graph algorithms on them. During the Master internship of Marko Oleksiyenko, we have extracted data of the city of Nice (mainly from OpenStreetMap) and applied to it the hub-labeling algorithm of Kosowski and Viennot (Inria Paris) [14]. A way to obtain better performances is to partition such a network into smaller cells. We have used Linear Programme for this purpose. However, we think that our work on graph Domination (at some distance) may help to obtain different (possibly better) partitions

Publications 2017

  1. Nathann Cohen, David Coudert, Guillaume Ducoffe, and Aurélien Lancin. Applying clique-decomposition for computing Gromov hyperbolicity. Theoretical Computer Science, Elsevier, 2017, 690, pp.114-139
  2. 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.
  3. David Coudert and Guillaume Ducoffe. A simple approach for lower-bounding 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.
  4. Kolja Knauer, Nicolas Nisse. Computing metric hulls in graphs. Research Report] Inria – Sophia Antipolis. 2017
  5. Lélia Blin, Janna Burman and Nicolas Nisse. Exclusive Graph Searching.
    Algorithmica, Volume 77(3), pages 942-969, 2017.
  6. Euripides Markou, Nicolas Nisse and Stéphane Pérennes. Exclusive Graph Searching vs. Pathwidth.
    Information and Computation, Volume 252, pages 243-260, 2017
  7. Gianlorenzo D’Angelo, Alfredo Navarra and Nicolas Nisse. Gathering and Exclusive Searching on Rings under Minimal Assumptions.
    Distributed Computing, Volume 30(1), pages 17-48, 2017.
  8. Frédéric Giroire, Remigiusz Modrzejewski, Nicolas Nisse and Stéphane Pérennes, Maintaining Balanced Trees For Structured Distributed Streaming Systems. Discrete Applied Maths 232: 176-188 (2017).
  9. 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/hal-01394593, 2017.
  10. 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.
  11. Marko Oleksiyenko, Bicycle-oriented itinerary computation for smart cities. Master thesis, Univ. Nice Sophia Antipolis, March-August, 2017.

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.

Comments are closed.