During the fourth year of the AlDyNet associated team between COATI and the Universidad Adolfo Ibáñez (Santiago, Chile), we have pursued ongoing research work on the study of graph decompositions and, more precisely, on the design of exact and heuristic algorithms for computing them. We have also worked on the computation of other graph properties such as the recognition of graphs with a distance preserving ordering, and on the cycle-convexity in graphs.
We have also worked on optimization problems having applications in wireless backhaul network, among other, 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 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 first focused on path-decompositions with the design an efficient branch and bound algorithm for computing them  and on some of their properties in directed graphs .
Our main contributions concern the study of tree-decompositions where some metric properties are imposed to the pieces of the decompositions. Precisely, we are not interested by keeping the pieces small (treewidth) but to make them having a small diameter (treelength) or small radius (treebreadth). We prove that, in large graph classes, the treelength may be used to approximate the treewidth of graphs . Then, we have proved that deciding whether the treebreadth of a graph is at most one is NP-hard in general graphs but can be solved in polynomial-time in bipartite graphs or planar graphs . All these results are crucial in the way to obtain efficient approximation algorithms to compute tree-decompositions.
- Other graph parameters. Working on graphs often requires to have a “good” ordering of the vertices, i.e., with interesting properties. Typical examples are the search-traversal (BFS, DFS, Lex-BFS…) that are used as corner-stone of many algorithms. We have investigated the distance preserving orderings which encompass many well known vertex-ordering (perfect elimination orderings, dismantable orderings, etc.). We proved that deciding if a graph admits such an ordering is NP-complete .
A convexity in graphs can be roughly described as the rules of propagation of an infection process on the vertices. Many different notions of convexity have been proposed depending on the infection process. Recently, cycle convexity in graphs has been defined for its applications in Knot Theory. In , we investigate the computational complexity of corresponding graph parameters. We prove they are NP-complete in general and give polynomial-time and FPT algorithms in many graph classes.
- Optimization in wireless networks. The reliability of a fixed wireless backhaul network is the probability that the network can meet all the communication requirements considering the uncertainty (e.g., due to weather) in the maximum capacity of each link. In , 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 consider the problem of determining the topology and configuration of a backhaul network that maximizes reliability subject to a limited budget.
In , we study the disconnection of a moving vehicle from a linear access network composed by cheap WiFi Access Points in the context of the telecommuting in massive transportation systems. In particular, we carry out a sensitivity analysis and supply a guide for operators when choosing the parameters of the networks.
- Optimization in geographical networks. In our collaboration with Chilean government, we have collected data on education, transportation, urban infrastructure, etc. An interesting first task have been that of correcting errors in the maps created by human users of ArcGIS. This exercise was not trivial, given de scale of networks to be corrected and the nature of problems ranging from erroneous coordinates and duplicate or missing nodes and edges to wrong street orientation. The Master 2 internship of V. Zaika  has been devoted to this task.
- Nicolas Nisse, Ronan Pardo Soares: On the monotonicity of process number.
Discrete Applied Mathematics 210: 103-111 (2016)
David Coudert, Dorian Mazauric, Nicolas Nisse: Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth.
ACM Journal of Experimental Algorithmics 21(1): 1.3:1-1.3:23 (2016)
David Coudert, Guillaume Ducoffe, Nicolas Nisse: To Approximate Treewidth, Use Treelength!
SIAM J. Discrete Math. 30(3): 1424-1436 (2016)
Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse: On the Complexity of Computing Treebreadth.
In 27th International Workshop on Combinatorial Algorithms (IWOCA 2016): LNCS 9843, Springer, 3-15, 2016.
Frédéric Giroire and Juan-Carlos Maureira. Analysis of the Failure Tolerance of Linear Access Networks.
IEEE Global Communications Conference (GLOBECOM), 2016
- Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, and Karol Suchan. On interval number in cycle convexity. Research Report, Inria Sophia Antipolis. 2016.
- David Coudert, James Luedtke, Eduardo Moreno and Konstantinos Priftis. Computing and maximizing the exact reliability of wireless backhaul networks. Research Report, Inria Sophia Antipolis. 2016.
- David Coudert, Guillaume Ducoffe, Nicolas Nisse, and Mauricio Soto. Distance-preserving orderings in graphs. RR-8973, Inria Sophia Antipolis. 2016.
- 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, March-August, 2016.
Visits in 2016
- Chile to France
- Eduardo Moreno: 15-23rd September, 2016
E. Moreno gave a seminar on September 20th, 2016 at Inria Sophia Antipolis, on Reliable network design under dependent failures.
- Eduardo Moreno: 15-23rd September, 2016
- France to Chile