Section: New Results

Algorithms

Participants : Julio Araújo, Janna Burman, Nathann Cohen, David Coudert, Gianlorenzo d'Angelo, Frédéric Giroire, Frédéric Havet, František Kardoš, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes, Ronan Pardo Soares, Leonardo Sampaio.

Mascotte 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.

Coloring Graphs

Almost all graph coloring problems are NP-hard and most of them are even hard to approximate. Hence, to solve them efficiently, we aim at designing general exponential-time algorithms as well as polynomial-time algorithms for special classes. This is examplified by the following results.

$L(p,q)$-labeling

An $L(p,q)$-labeling of $G$ is an integer assignment $f$ to the vertex set $V\left(G\right)$ such that $\left|f\right(u)-f(v\left)\right|\ge p$, if $u$ and $v$ are adjacent, and $\left|f\right(u)-f(v\left)\right|\ge q$, if $u$ and $v$ have a common neighbor. Such a concept is a modeling of a simple channel assignment, in which the separation between channels depends on the distance. The goal is to find an $L(p,q)$-labeling $f$ of $G$ with minimum span (i.e. $max\left\{f\right(u)-f(v),u,v\in V(G\left)\right\}$). It is well known that for all $k\ge 4$, deciding if a graph has an $L(p,1)$-labeling with minimum span $k$ is NP-complete. In [42] , we present exact exponential time algorithms that are faster than existing ones.

Counting and Enumerating Total and Edge Colorings

In [89] , we are interested in computing the number of edge colorings and total colorings of a graph. We prove that the maximum number of $k$-edge-colorings of a $k$-regular graph on $n$ vertices is $k·{(k-1!)}^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$-edge-colorings of a $k$-regular graph using a time $O^{*}\left({(k-1!)}^{n/2}\right)$ and polynomial space. In particular, we obtain a algorithm on time $O^{*}\left(2^{n/2}\right)=O^{*}(1.{4143}^n)$ and polynomial space to enumerate all the 3-edge colorings of a cubic graph, improving the running time of $O^{*}(1.{5423}^n)$ of the algorithm due to Golovach et al. We also show that the number of 4-total-colorings of a connected cubic graph is at most $3.2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the 4-total-colorings of a connected cubic graph.

Coloring Graphs of Special Classes

For some coloring problems that are known to be NP-hard for general graphs, we give some polynomial-time algorithms for the restriction to some graph classes. These graph classes defined in terms of forbidden induced subgraphs. In [95] , [79] , we provide linear algorithms for coloring $P_5$-free graphs. In [58] , we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of $(q,q-4)$-graphs. Such graphs are those such that no set of at most $q$ vertices induces more than $q-4$ distinct P4’s.

Complexity and Computation of Graph Parameters

We used graph theory to model various networks' problems. In general 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 where the problems are polynomial-time solvable.

Path Vertex Cover

A subset $S$ of vertices of a graph $G$ is called a $k$-path vertex cover if every path of order $k$ in $G$ contains at least one vertex from $S$. The $k$-path vertex cover problem consists in finding such a set with minimum cardinality in $G$. In [25] , it is shown that this problem is NP-complete for each $k\ge 2$ while it can be solved in linear-time in trees. The particular case of $k=3$ is studied in [44] , where an exact algorithm is given with running time $O^{*}(1.{5171}^n)$ in $n$-node graphs. In [44] , we also design a polynomial time randomized approximation algorithm with an expected approximation ratio of $\frac{23}{11}$ for the minimum 3-path vertex cover.

Convexity in Graphs

The geodesic convexity of graphs naturally extends the notion of convexity in euclidean metric spaces. A set $S$ of vertices of a graph $G=(V,E)$ is convex if any vertex on a shortest path between two vertices of $S$ also belongs to $S$. The convex hull of $S\subseteq V$ is the smallest convex set containing $S$. Finally, a hull set of a graph is a set of vertices the convex hull of it is $V$. The hull number of a graph $G$ is the minimum size of a hull set in $G$. In [86] , [49] , we prove that computing the hull number is NP-complete in bipartite graphs. We also provide bounds and design various polynomial-time algorithms for this problem in different graph classes as co-bipartite graphs, $P_4$-sparse graphs, etc.

Induced Subdivision in Digraphs

In [51] , we consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $G$, does it contain an induced subdivision of a prescribed digraph $D$? The complexity of this problem depends on $D$ and on whether $H$ must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.

Circuits in Grids

A circuit in a simple undirected graph $G=(V,E)$ is a sequence of vertices $\{v_1,v_2,\cdots ,v_{k+1}\}$ such that $v_1=v_k+1$ and $\{v_i,v_{i+1}\}\in E$ for $i=1,\cdots ,k$. A circuit $C$ is said to be edge-simple if no edge of $G$ is used twice in $C$. In [30] , we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of an infinite square grid, there exists an edge-simple circuit visiting the $k$ vertices in the prescribed order? We prove that $k=10$. To this end, we first provide a counterexample implying that $k<11$. To show that $k\ge 10$, we introduce a methodology, based on the notion of core graph, to reduce drastically the number of possible vertex configurations, and then we test each one of the resulting configurations with an ILP solver.

Graph Searching, Cops and Robber Games

Pursuit-evasion encompasses a wide variety of combinatorial problems related to the capture of a fugitive residing in a network by a team of searchers. The goal consists in minimizing the number of searchers required to capture the fugitive in a network and in computing the corresponding capture strategy. This can also be viewed as cleaning the edges of a contaminated graph. We investigated several variants of these games.

Process Number and Routing Reconfiguration in WDM Networks

Graph searching, where the fuggitive is arbitrary fast and moves simultaneously to the searchers, has been widely studied for its close relationship with graph decompositions. More recently, a variant of graph searching, namely the graph processing game, has been widely studied as a model for the routing reconfiguration in WDM networks (see Section  6.1.1.2 ). In [32] , we give a linear time (resp. polynomial-time) algorithm to recognize graphs (resp., digraphs) with process number at most 2, along with a characterization in terms of forbidden minors, and a structural description. In [31] , we give a polynomial (both in terms of time complexity and in the number of exchanged messages) distributed algorithm to compute the process number of trees. By slightly modifying the intial parameter of the algorithm, it also allows to compute various parameters of trees as pathwidth, search number, etc.

Cops and Robber Games

The "Cops and Robber Games" are turn-by-turn games where a team of cops purchase a robber in a graph. We investigated two generalizations of the game introduced by Quilliot, Nowakoski and Winkler in 1983. We provided structural characterizations of graphs where one cop is sufficient to capture a fast fugitive able to hide [27] . In particular, one of these characterizations relies on hyperbolicity of the considered graph.

A surprising application of "Cops and Robber"-like games is the problem for a web-browser to download documents in advance while an internaut is surfing on the Web. In [92] , we provide a modelling of the prefetching problem in terms of Cops and Robber games. The parameter to be optimized is then the download-speed necessary for the Internaut only accesses to already download webpages. This allows us to provide several complexity results and polynomial-time algorithms in some graph classes.

Distributed Algorithms

We investigated algorithmic problems arising in complex networks like the Internet or social networks. In this kind of networks, problems are becoming harder or impracticable because of the size and the dynamicity of these networks. One way to handle the dynamicity is to provide (distributed) fault tolerant algorithms. Studying the mobile agents paradigm seems to be a promissing approach (somehow related to Cops and Robber in Section  6.4.3 ) to adress some models of distributed computing. We considered self-stabilizing algoritms for the gathering problem, and algorithms for updating routing tables.

Besides, the more an algorithm uses local information, the easier it is to update/correct the behaviour of the algorithm. In this direction, we investigated communication problems through game theory. We also studied the power of a communication model using only localized information, i.e., we study what can be computed using this communication model.

Mobile Agents and Self-stabilization

In [64] , we consider a recent model of robot-based computing which makes use of identical, memoryless mobile robots placed on nodes of anonymous graphs. The robots operate in Look-Compute-Move cycles that are performed asynchronously for each robot. In particular, we consider the case of gathering robots on an anonymous ring. We provide a new distributed approach which turns out to be very interesting as it neither completely falls into symmetry-breaking nor into symmetry-preserving techniques.

We address dynamic large scale emerging networks, e.g., mobile sensor (agent) networks. The agents are resource limited and prone to failures. They move almost unpredictably and communicate in pairs. Population Protocol model is a communication model suited for such networks. We use a recently proposed version of this model where every agent is associated with a parameter called Cover Time. Cover Times abstract the interaction characteristics of mobile agents and allow the design of fast converging protocols and the evaluation of their convergence times (this is impossible in the original model). We take advantage of this model and perform first analytical analysis of a data collection protocol used in the ZebraNet project for the wild-life tracking of zebras. We propose alternative data collection protocols for ZebraNet and we analysis their time complexities [72] , [53] , [54] . To achieve fault-tolerance in population protocols, we develop a generic self-stabilizing transformer [22] . This is an automatic technique to convert a protocol to its self-stabilizing version.

In addition, we address important problems of coordination and synchronization. We present and prove correct two self-stabilizing deterministic protocols solving the classical mutual exclusion problem and the group mutual exclusion one [54] .

Distributed Update of Routing Tables

In [62] , we propose a simple and practical distributed algorithm for computing and updating routing tables for shortest path routing. This algorithm can be combined with every distance vector shortest paths routing algorithm, and allows to reduce the total number of messages sent. We give experimental evidence that it leads to an important gain in terms of the number of messages sent at the price of a little increase in terms of space occupancy per node.

Arc-Flags is a data structure used to speed-up the shortest paths computation in a graph. In [67] , we introduce a new data structure, named Road-Signs, which allows us to efficiently update the Arc-Flags of a graph in a dynamic scenario. Road-Signs can be used to compute Arc-Flags, can be efficiently updated and do not require large space consumption for many real-world graphs.

Models of Distributed Computation

Since, we need to face both locality and dynamicity issues, we are developing new techniques allowing to obtain global structural information from local (partial) views of the network. In [55] , [73] , we has investigated the question of determining which graph properties can or cannot be computed using only local information. We consider the following model: each of the $n$ nodes of a graph which only knows its own ID and the IDs of its neighbours is allowed to send a message of $O\left(logn\right)$ bits to some central entity, called the referee. We then investigate whether the referee is able to decide some basic structural properties of the network topology $G$ or not. We show that simple questions like, "does $G$ contain a square?", "does $G$ contain a triangle?" or "Is the diameter of G at most 3?” cannot be solved in general [55] , [73] . On the other hand, the referee can decode the messages in order to have full knowledge of $G$ when $G$ belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded degeneracy graphs [55] , [73] . Following our framework, we are able to simulate asynchronicity of the network. In particular, we have exhibited a hierarchy of problems and distributed models of computation [87] .