AlDyNet — Bilan 2014

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 [6]. 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 [11]. 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 [6].

  • 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 [2], 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 [8].
    An extended abstract of this work has been presented in an international conference [8] 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 [9]. 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 [5]. 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 [5]. The other part is currently submitted [9].

  • 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 [7] and an international revue [3]. Our work on testing graph properties in a distributed setting has been published in an international revue [1].

Publications 2014

Visits 2014

Comments are closed