During the second year of the AlDyNet associated team between COATI and the Universidad Adolfo Ibáñez (Santiago, Chile), we have pursued ongoing research work on the design of exact and heuristic algorithms for computing path-decompositions of graphs. We have also worked on the computation of other graph parameters such as the minimum size of a tree decomposition and the hyperbolicity of large graphs. We have also finalized our work on distributed computing through the coordination of mobile agents on graphs.
- Path-decompositions of graphs.
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. More precisely, many NP-hard problems (coloring, maximum independent set…) can be solved in linear time in the class of graphs with small width (the size of the pieces).
One prerequisite for running this kind of algorithms is the computation of good graph decompositions, which itself is a NP-hard problem.
Our contribution here concerns the computation of good path-decompositions of graphs. Informally, a path-decomposition of a graph corresponds to a linear ordering of its vertices associated to a measure (its width). Since this is a NP-hard problem, we have focused on the design of an exact branch-and-bound algorithm and a set of heuristics. Our algorithm outperforms all previous work and it is able to compute the exact pathwidth of all graphs with up to 80 vertices . During its internship in the COATI team (from December 2013 till February 2014), Klaus Jaschan has implemented other algorithms that will be used to evaluate the performance of our algorithm . During its visit in the COATI team (May-July 2014), Esteban Roman has pursued these investigations.
Our work has been validated in an international conference .
- Tree-decompositions with small size.
Computing efficiently good tree-decomposition of graphs is a very challenging problem. To tackle this problem, we focus on tree-decompositions that must satisfy extra constraints.
In , we designed an efficient polynomial-time algorithm that either find a large cycle in a graph or compute a tree-decomposition whose pieces have particular structural properties. We can use such structure to design efficient compact routing schemes.
Then, during the visit of members of COATI in Santiago (Nov. 2013), we started investigating the problem of minimizing the size of tree-decompositions (minimizing the number of pieces with fixed size). Since then, we have obtained several complexity results and algorithms for this problem .
An extended abstract of this work has been presented in an international conference  and a full version is currently submitted.
- Computation of hyperbolicity in large graphs.
The Gromov hyperbolicity of a graph is a parameter that is related to its metric (roughly, to the distribution of the distances in the graph). More precisely, the hyperbolicity of a graph G measures how the metric of G is close to the metric of a tree. It is well known that, in graphs with small hyperbolicity (such as the Autonomous Systems network of the Internet), very simple routing schemes (e.g., greedy routing) perform very well. Computing the hyperbolicity of a graph can be done in polynomial time. However, the best known algorithm has complexity n3,69 which is far to be efficient for large scale networks. Hence, better algorithms are needed that are dedicated to networks with particular structural properties.
First, we have applied the so-called clique-minimal decomposition to speed-up the computation of the parameter . Our algorithm has been implemented in Python and has allowed to compute the exact hyperbolicity of large scale networks such as the AS network. We then improved the time complexity for the recognition of graphs with small hyperbolicity, and we proved our new algorithm is optimal under subcubic reductions . Our lower bound relies on the fact that deciding whether a graph has hyperbolicity 1/2 is equivalent to find induced cycles of 4 nodes in graphs.
This work is the starting point of one of our objectives for next year. Namely, we aim at relating metric properties of graphs (hyperbolicity) with their topological properties (treewidth). See Section 3.
Part of this work has been published in an international revue . The other part is currently submitted .
- Distributed computing.
The work on distributed computing models that has been the main part of the first year of the project has been published in several international conferences and revues. Our work on the coordination of mobile agents in graphs has been published in an international conference  and an international revue . Our work on testing graph properties in a distributed setting has been published in an international revue .
- David Coudert, Guillaume Ducoffe. On the recognition of \(C_4\)-free and \(1/2\)-hyperbolic graphs.
SIAM J. Discrete Math. 28(3): 1601-1617 (2014)
Bi Li, Fatima Zahra Moataz, Nicolas Nisse and Karol Suchan, Minimum Size Tree-Decompositions.
Extended abstract in 9th International colloquium on graph theory and combinatorics (ICGT), 2014. [Research Report], 2014, pp. 23. hal-01074177
David Coudert, Dorian Mazauric and Nicolas Nisse. Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth.
To appear in Proceedings of the 13rd Symposium on Experimental Algorithms (SEA), LNCS, Springer, pages 46-58, 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 75-86, 2014.
- 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 149-164, 2014.
- Nathann Cohen, David Coudert, Guillaume Ducoffe, and Aurélien Lancin. Applying clique-decomposition for computing Gromov hyperbolicity. [Research Report], 2014, pp. 30. RR-8535
- Esteban Roman Catafau, Analysis of a Branch and Bound algorithm for pathwidth, internship report, May-July 2014.
- Klaus Jaschan, Implementing a Vertex Separation algorithm for trees in Sagemath, internship report, Dec. 2013- Feb. 2014.
- Bi Li, Tree Decompositions and Routing Problems. Ph.D. thesis, Univ. Nice Sophia Antipolis, November 12th, 2014.
- Nicolas Nisse, Algorithmic complexity: Between Structure and Knowledge How Pursuit-evasion Games help. HDR, Univ. Nice Sophia Antipolis, May 26th, 2014.
- Chile to France
- France to Chile
- David Coudert: November 14th to November 30th, 2014.
- Nicolas Nisse: November 14th to December 14th, 2014.
- Guillaume Ducoffe: November 14th to December 14th, 2014.
G. Ducoffe presented his work during the CMM seminar on November 28th, 2014 on the diameter of minimal separators in a graph, and during the UAI seminar on December 9th, 2014 on Convergence of Coloring Games with Collusions