Section: New Results

Graph Algorithms

Participants : Jean-Claude Bermond, Nathann Cohen, David Coudert, Guillaume Ducoffe, Frédéric Giroire, Nicolas Nisse, Stéphane Pérennes.

Coati is also interested in the algorithmic aspects of Graph Theory. In general we try to find the most efficient algorithms to solve various problems of Graph Theory and telecommunication networks. We use graph theory to model various network problems. We study their complexity and then we investigate the structural properties of graphs that make these problems hard or easy. In particular, we try to find the most efficient algorithms to solve the problems, sometimes focusing on specific graph classes from which the problems are polynomial-time solvable. Many results introduced here are presented in detail in the PhD thesis of Guillaume Ducoffe on Metric properties of large graphs https://team.inria.fr/coati/phd-defense-of-guillaume-ducoffe/.

Graph decompositions

It is well known that many NP-hard problems are tractable in the class of bounded treewidth graphs. In particular, tree-decompositions of graphs are an important ingredient of dynamic programming algorithms for solving such problems. This also holds for other width-parameters of graphs. Therefore, computing these widths and associated decompositions of graphs has both a theoretical and practical interest.

Width parameters of graphs

In [22], we design a Branch and Bound algorithm that computes the exact pathwidth of graphs and a corresponding path-decomposition. Our main contribution consists of several non-trivial techniques to reduce the size of the input graph (pre-processing) and to cut the exploration space during the search phase of the algorithm. We evaluate experimentally our algorithm by comparing it to existing algorithms of the literature. It appears from the simulations that our algorithm offers a significative gain with respect to previous work. In particular, it is able to compute the exact pathwidth of any graph with less than 60 nodes in a reasonable running-time (10 min.). Moreover, our algorithm also achieves good performance when used as a heuristic (i.e., when returning best result found within bounded time-limit). Our algorithm is not restricted to undirected graphs since it actually computes the vertex-separation of digraphs (which coincides with the pathwidth in case of undirected graphs).

Many tree-decomposition-like parameters are related to particular layouts (ordering) of the vertices of the input graph. In [45], we present a new set of constraints for modeling linear ordering problems on graphs using Integer Linear Programming (ILP). These constraints express the membership of a vertex to a prefix rather than the exact position of a vertex in the ordering. We use these constraints to propose new ILP formulations for well-known linear ordering optimization problems, namely the Pathwidth, Cutwidth, Bandwidth, SumCut and Optimal Linear Arrangement problems. Our formulations are not only more compact than previous proposals, but also more efficient as shown by our experimental evaluations on large benchmark instances.

Metric properties of graph decompositions

The decomposition of graphs by clique-minimal separators is a common algorithmic tool, first introduced by Tarjan. Since it allows to cut a graph into smaller pieces, it can be applied to pre-process the graphs in the computation of many optimization problems. However, the best known clique-decomposition algorithms have respective $O\left(nm\right)$-time and $O\left(n^{2.69}\right)$-time complexity, that is prohibitive for large graphs. Here we prove that for every graph G, the decomposition can be computed in $O(T\left(G\right)+min\{n^{2.3729},{\omega }^{2}n\})$-time with $T\left(G\right)$ and $\omega$ being respectively the time needed to compute a minimal triangulation of $G$ and the clique-number of $G$. In particular, it implies that every graph can be clique-decomposed in $O\left(n^{2.3729}\right)$-time. Based on prior work from Kratsch et al., in [46], we prove in addition that computing the clique-decomposition is at least as hard as triangle detection. Therefore, the existence of any $o\left(n^{2.3729}\right)$-time clique-decomposition algorithm would be a significant breakthrough in the field of algorithmic. Finally, our main result implies that planar graphs, bounded-treewidth graphs and bounded-degree graphs can be clique-decomposed in linear or quasi-linear time.

In [21], we establish general relationships between the topological properties of graphs and their metric properties. For this purpose, we upper-bound the diameter of the minimal separators in any graph by a function of their sizes. More precisely, we prove that, in any graph $G$, the diameter of any minimal separator $S$ in $G$ is at most $\lfloor \frac{\ell \left(G\right)}{2}\rfloor ·\left(\right|S|-1)$ where $\ell \left(G\right)$ is the maximum length of an isometric cycle in $G$. We refine this bound in the case of graphs admitting a distance preserving ordering for which we prove that any minimal separator $S$ has diameter at most $2\left(\right|S|-1)$. Our proofs are mainly based on the property that the minimal separators in a graph $G$ are connected in some power of $G$. Our result easily implies that the treelength $tl\left(G\right)$ of any graph $G$ is at most $\lfloor \frac{\ell \left(G\right)}{2}\rfloor$ times its treewidth $tw\left(G\right)$. In addition, we prove that, for any graph $G$ that excludes an apex graph $H$ as a minor, $tw\left(G\right)\le c_H·tl\left(G\right)$ for some constant $c_H$ only depending on $H$. We refine this constant when $G$ has bounded genus. As a consequence, we obtain a very simple $O\left(\ell \right(G\left)\right)$-approximation algorithm for computing the treewidth of $n$-node $m$-edge graphs that exclude an apex graph as a minor in $O\left(nm\right)$-time.

In [32], [50], we study metric properties of the bags of tree-decompositions of graphs. Roughly, the length and the breadth of a tree-decomposition are the maximum diameter and radius of its bags respectively. The treelength and the treebreadth of a graph are the minimum length and breadth of its tree-decompositions respectively. Pathlength and pathbreadth are defined similarly for path-decompositions. In this paper, we answer open questions of [Dragan and Köhler , Algorithmica 2014] and [Dragan, Köhler and Leitert, SWAT 2014] about the computational complexity of treebreadth, pathbreadth and pathlength. Namely, we prove that computing these graph invariants is NP-hard. We further investigate graphs with treebreadth one, i.e., graphs that admit a tree-decomposition where each bag has a dominating vertex. We show that it is NP-complete to decide whether a graph belongs to this class. We then prove some structural properties of such graphs which allows us to design polynomial-time algorithms to decide whether a bipartite graph, resp., a planar graph, has treebreadth one.

Graph hyperbolicity

The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree (the smaller gap the better). It has recently been used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs, and for various applications in network security, computational biology, the analysis of graph algorithms, and the classification of complex networks.

Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection networks. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Motivated by the good performances in practice of these new routing schemes, we propose in [19], [29] the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endomorphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model.

In [20], we investigate more specifically on the hyperbolicity of bipartite graphs. More precisely, given a bipartite graph $B=(V_0\cup V_1,E)$ we prove it is enough to consider any one side $V_i$ of the bipartition of $B$ to obtain a close approximate of its hyperbolicity $\delta \left(B\right)$ — up to an additive constant 2. We obtain from this result the sharp bounds $\delta \left(G\right)-1\le \delta \left(L\right(G\left)\right)\le \delta \left(G\right)+1$ and $\delta \left(G\right)-1\le \delta \left(K\right(G\left)\right)\le \delta \left(G\right)+1$ for every graph $G$, with $L\left(G\right)$ and $K\left(G\right)$ being respectively the line graph and the clique graph of $G$. Finally, promising extensions of our techniques to a broader class of intersection graphs are discussed and illustrated with the case of the biclique graph $BK\left(G\right)$, for which we prove $\left(\delta \right(G)-3)/2\le \delta \left(BK\right(G\left)\right)\le \left(\delta \right(G)+3)/2$.

Combinatorial games on graphs

We study several two-player games on graphs.

Games and graph decompositions

Graph Searching is a game where a team of searchers aims at capturing a fugitive in a graph. Graph Searching games have been widely studied because they are an algorithmic interpretation of tree/path-decompositions of graphs.

In [18], we define a new variant of graph searching, where searchers have to capture an invisible fugitive with the constraint that no two searchers can occupy the same node simultaneously. This variant seems promising for designing approximation algorithms for computing the pathwidth of graphs. The main contribution in [18] is the characterization of trees where k searchers are necessary and sufficient to win. Our characterization leads to a polynomial-time algorithm to compute the minimum number of searchers needed in trees.

We also study graph searching in directed graphs. We prove that the graph processing variant is monotone which allows us to show its equivalence with a particular digraph decomposition [25].

Distributed computing

We also investigate the games described above in a distributed setting.

Consider a set of mobile robots with minimal capabilities placed over distinct nodes of a discrete anonymous ring. Asynchronously, each robot takes a snapshot of the ring, determining which nodes are either occupied by robots or empty. Based on the observed configuration, it decides whether to move to one of its adjacent nodes or not. In the first case, it performs the computed move, eventually. The computation also depends on the required task. In [24], we solve both the well-known Gathering and Exclusive Searching tasks. In the former problem, all robots must simultaneously occupy the same node, eventually. In the latter problem, the aim is to clear all edges of the graph. An edge is cleared if it is traversed by a robot or if both its endpoints are occupied. We consider the exclusive searching where it must be ensured that two robots never occupy the same node. Moreover, since the robots are oblivious, the clearing is perpetual, i.e., the ring is cleared infinitely often. In the literature, most contributions are restricted to a subset of initial configurations. Here, we design two different algorithms and provide a characterization of the initial configurations that permit the resolution of the problems under minimal assumptions.

Spy games in graphs

In [28], we define and study the following two-player game on a graph $G$. Let $k\in {\mathbb{N}}^{*}$. A set of $k$ guards is occupying some vertices of $G$ while one spy is standing at some node. At each turn, first the spy may move along at most $s$ edges, where $s\in {\mathbb{N}}^{*}$ is his speed. Then, each guard may move along one edge. The spy and the guards may occupy same vertices. The spy has to escape the surveillance of the guards, i.e., must reach a vertex at distance more than $d\in \mathbb{N}$ (a predefined distance) from every guard. Can the spy win against $k$ guards? Similarly, what is the minimum distance $d$ such that $k$ guards may ensure that at least one of them remains at distance at most $d$ from the spy? This game generalizes two well-studied games: Cops and robber games (when $s=1$) and Eternal Dominating Set (when $s$ is unbounded). First, we consider the computational complexity of the problem, showing that it is NP-hard and that it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number $k$ of guards and the required distance $d$ when $G$ is a path or a cycle. Our main result is that there exists $\beta >0$ such that $\Omega \left(n^{1+\beta }\right)$ guards are required to win in any $n\times n$ grid.

Complexity of graph problems

We also investigate several graph problems coming from various applications. We mainly consider their complexity in general or particular graph classes. When possible, we present polynomial-time (approximation) algorithms or Fixed Parameter Tractable algorithms.

Bin packing

Motivated by an assignment problem arising in MapReduce computations , we investigate a generalization of the Bin Packing problem which we call Bin Packing with Colocations Problem [41]. Given a set V of items with positive integer weights, an underlying graph G = (V, E), and an integer q, the goal is to pack the items into a minimum number of bins so that (i) the total weight of the items packed in every bin is at most q, and (ii) for each edge (i, j) ∈ E there is at least one bin containing both items i and j. We first show that when the underlying graph is unweighted (i.e., all the items have equal weights), the problem is equivalent to the q-clique problem, and when furthermore the underlying graph is a clique, optimal solutions are obtained from covering designs. We prove that the problem becomes NP-hard even for weighted paths and un-weighted trees and we propose approximation algorithms for particular families of graphs, including: a $(3+\sqrt{5})$-approximate algorithm for weighted complete graphs (improving a previous 8-approximation), a 2-approximate algorithm for weighted paths, a 5-approximate algorithm for weighted trees, and an (1+)-approximate algorithm for unweighted trees. For general weighted graphs, we propose a 3 + 2mad(G)/2-approximate algorithm, where mad(G) is the maximum average degree of G. Finally, we show how to convert any ρ-approximation algorithm for the Bin Packing (resp. the Densest q-Subgraph problem) into an approximation algorithm for the problem on weighted (resp. unweighted) general graphs.

distance preserving ordering

For every connected graph $G$, a subgraph $H$ of $G$ is isometric if for every two vertices $x,y\in V\left(H\right)$ there exists a shortest xy-path of $G$ in $H$. A distance-preserving elimination ordering of $G$ is a total ordering of its vertex-set $V\left(G\right)$, denoted $(v_1,v_2,\cdots ,v_n)$, such that any subgraph $G-i=G\setminus \{v_1,v_2,\cdots ,v_i\}$ with $1\le i<n$ is isometric. This kind of ordering has been introduced by Chepoi in his study on weakly modular graphs. In [47], we prove that it is NP-complete to decide whether such ordering exists for a given graph — even if it has diameter at most 2. Then, we describe a heuristic in order to compute a distance-preserving ordering when it exists one that we compare to an exact exponential algorithm and an ILP formulation for the problem. Lastly, we prove on the positive side that the problem of computing a distance-preserving ordering when it exists one is fixed-parameter-tractable in the treewidth.

cycle convexity

Many notions in graph convexity have been defined and studied for various applications, such as geode-tic convexity (generalizing the classical convexity in Euclidean space to graphs), monophonic convexity (to model spreading of rumor or disease in a network), etc. Each of the convexity notions led to the study of important graph invariants such as the hull number (minimum number of vertices whose hull set is the entire graph) or the interval number (minimum number of vertices whose interval is the whole graph). Recently, Araujo et al. introduced the notion of Cycle Convexity of graphs for its application in Knot Theory. Roughly, the tunnel number of a knot embedded in a plane is equivalent to the hull number of a corresponding planar 4-regular graph in cycle convexity. In [35], we study the interval number of a graph in cycle convexity. Precisely, given a graph G, its interval number in cycle convexity, denoted by incc(G), is the minimum cardinality of a set $S\subseteq V\left(G\right)$ such that every vertex $w\in V\left(G\right)\setminus S$ has two distinct neighbors $u,v\in S$ such that u and v lie in same connected component of $G\left[S\right]$. In this work, first we provide bounds on incc(G) and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $incc\left(G\right)\le k$ is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[1]-hard in bipartite graphs when k is the parameter. As a consequence, we obtain that it cannot be approximated up to a constant factor in the class of split graphs (unless P = N P). On the positive side, we present polynomial-time algorithms to compute incc(G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present FPT algorithms to compute it for (q, q − 4)-graphs, where q is the parameter and for bounded treewidth graphs.