DUCOFFE , Guillaume

The square of a given graph $H = (V, E)$ is obtained from $H$ by adding an edge between every two vertices at distance two in $H$. Given a graph class ${\cal H}$, the ${\cal H}$-Square Root problem asks for the recognition of the squares of graphs in ${\cal H}$. In this paper, we answer positively to an open question of [Golovach et al.,...

Let $H=(\mathcal{V},\mathcal{E})$ be a directed hypergraph, sometimes called a dihypergraph. Each vertex $v\in{\mathcal{V}}$ is incident to some hyperarcs in $\mathcal{E}$. Conversely, each hyperarc $E\in{\mathcal{E}}$ is incident to some vertices in $\mathcal{V}$. $H$ is Eulerian if there is a circuit $C$ such that each hyperarc...

The strong pathbreadth of a given graph G is the minimum ρ such that G admits a Robertson and Seymour's path decomposition where every bag is the complete ρ-neighbourhood of some vertex in G. We prove that deciding whether a given graph has strong pathbreadth at most one is NP-complete. The latter answers negatively to a conjecture of [Leitert...

The square of a given graph $H = (V, E)$ is obtained from $H$ by adding an edge between every two vertices at distance two in $H$. Given a graph class $\mathcal{H}$, the $\mathcal{H}$-\textsc{Square Root} problem asks for the recognition of the squares of graphs in $\mathcal{H}$. In this paper, we answer positively to an open question of...

Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies....

We wish to motivate the problem of finding decentralized lower-bounds on the complexity of computing a Nash equilibrium in graph games. While the centralized computation of an equilibrium in polynomial time is generally perceived as a positive result, this does not reflect well the reality of some applications where the game serves to implement...

In this article, we determine when the large generalized de Bruijn cycles BGC(p, d, n) are Hamiltonian. These digraphs have been introduced by Gómez, Padró and Pérennes as large interconnection networks with small diameter and they are a family of generalized p-cycles. They are the Kronecker product of the generalized de Bruijn digraph GB(d, n)...

We answer open questions of [Verbeek and Suri, SOCG'14] on the relationships between Gromov hyperbolicity and the optimal stretch of graph embeddings in Hyperbolic space. Then, based on the relationships between hyperbolicity and Cops and Robber games, we turn necessary conditions for a graph to be Cop-win into sufficient conditions for a graph...

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

Nous démontrons l'influence de propriétés des réseaux d'interconnexion de centres de données sur l'étirement obtenu pour des routages dits "géométriques". Ces routages reposent sur un plongement des sommets du graphe dans un espace métrique "simple" tel que le plan Hyperbolique. Les réseaux d'interconnexions des centres de données sont...

Topologies for data center interconnection 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...

Hyperbolicity is a measure of the tree-likeness of a graph from a metric perspective. Recently , it has been used to classify complex networks depending on their underlying geometry. Motivated by a better understanding of the structure of graphs with bounded hyperbolicity, we here investigate on the hyperbolicity of bipartite graphs. More...

The shortest-path metric d of a connected graph G is 1/2-hyperbolic if, and only if, it satisfies d(u,v) + d(x,y) ≤ max{d(u,x) + d(v,y),d(u,y) + d(v,x)} + 1, for every 4-tuple u,x,v,y of G. We show that the problem of deciding whether an unweighted graph is 1/2-hyperbolic is subcubic equivalent to the problem of determining whether there is a...

We study the complexity of decomposing a graph by means of clique separators. This common algorithmic tool, first introduced by Tarjan, allows to cut a graph into smaller pieces, and so, it can be applied to preprocess the graph in the computation of optimization problems. However, the best-known algorithms for computing a decomposition have...

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(nm)-time...

The shortest-path metric $d$ of a connected graph $G$ is $\frac{1}{2}$-hyperbolic if, and only if, it satisfies $d(u,v) + d(x,y) \leq \max \{ d(u,x) + d(v,y), d(u,y) + d(v,x) \} + 1$, for every $4$-tuple $u,x,v,y$ of $G$. We show that the problem of deciding whether an unweighted graph is $\frac{1}{2}$-hyperbolic is subcubic equivalent to the...

We establish general relationships between the topological properties of graphs and their metric properties. For this purpose, we upper-bound the diameter of the {\it 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...

Recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above mentioned problems...

During the last decade, metric properties of the bags of tree-decompositions of graphs have been studied. 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...

Recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above mentioned problems...

Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as "interval thinness"...

We here investigate on the complexity of computing the tree-length and the tree-breadth of any graph G, that are respectively the best possible upper-bounds on the diameter and the radius of the bags in a tree decomposition of G. Path-length and path-breadth are similarly defined and studied for path decompositions. So far, it was already known...

We study a group-formation game on an undirected complete graph G with all edge-weights in a set W ⊆ R ∪ {−∞}. This work is motivated by a recent information-sharing model for social networks (Kleinberg and Ligett, GEB, 2013). Specifically, we consider partitions of the vertex-set of G into groups. The individual utility of any vertex v is the...

Tree-likeness parameters have proven their utility in the design of efficient algorithms on graphs. In this paper, we relate the structural tree-likeness of graphs with their metric tree-likeness. To this end, we establish new upper-bounds on the diameter of minimal separators in graphs. We prove that in any graph G, the diameter of any minimal...

Parameterized complexity theory has enabled a refined classification of the difficulty of NP-hard optimization problems on graphs with respect to key structural properties, and so to a better understanding of their true difficulties. More recently, hardness results for problems in P were achieved using reasonable complexity theoretic...