|
|
|
|
|
Sorbonne Université |
|
I am a lecturer (maître de conférences) in computer science at LIP6, Sorbonne University, in Paris. I am a member of the Operation Research team and of the research axis Theory and mathematics of computing. My research involves graph theory, algorithmics, complexity, combinatorics, optimisation, operations research and geometry. My recent works focus mostly on generalizations of graphs, such as coloring of directed graphs or routing problems in forbidden-transition graphs. |
A coloring of a digraph is a partition of its vertex set such that each class induces a digraph with no directed cycles. A digraph is k-chromatic if k is the minimum number of classes in such partition, and a digraph is oriented if there is at most one arc between each pair of vertices. Clearly, the smallest k-chromatic digraph is the complete digraph on k vertices, but determining the order of the smallest k-chromatic oriented graphs is a challenging problem. It is known that the smallest 2-, 3- and 4-chromatic oriented graphs have 3, 7 and 11 vertices, respectively. In 1994, Neumann-Lara conjectured that a smallest 5-chromatic oriented graph has 17 vertices. We solve this conjecture and show that the correct order is 19.
The dichromatic number of a digraph D is the least integer k such that D can be partitioned into k directed acyclic digraphs. A digraph is k-dicritical if its dichromatic number is k and each proper subgraph D′ of D has dichromatic number k-1. An oriented graph is a digraph with no directed cycle of length 2. For integers k and n, we denote by o(k,n) the minimum number of edges of a k-critical oriented graph on n vertices (with the convention o(k,n)=+∞ if there is no k-dicritical oriented graph of order n). The main result of this paper is a proof that o(3,n)≥7n+23 together with a construction witnessing that o(3,n)≤⌈5n/2⌉ for all n≥12. We also give a construction showing that for all sufficiently large n and all k≥3, o(k,n)≤(2k−3)n, disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all k≥2, o(k,n) ≥ (k - 3/4- 1/(4k-6)) n + 3/(4(2k-3)}, improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.
Homomorphically full graphs are those for which every homomorphic image is isomorphic to a subgraph. We extend the definition of homomorphically full to oriented graphs in two different ways. For the first of these, we show that homomorphically full oriented graphs arise as quasi-transitive orientations of homomorphically full graphs. This in turn yields an efficient recognition and construction algorithms for these homomorphically full oriented graphs. For the second one, we show that the related recognition problem is GI-hard, and that the problem of deciding if a graph admits a homomorphically full orientation is NP-complete. In doing so we show the problem of deciding if two given oriented cliques are isomorphic is GI-complete.
A dominating set in a directed graph is a set of vertices S such that all the vertices that do not belong to S have an in-neighbour in S. A locating set S is a set of vertices such that all the vertices that do not belong to S are characterized uniquely by the in-neighbours they have in S, i.e. for every two vertices u and v that are not in S, there exists a vertex s∈S that dominates exactly one of them. The size of a smallest set of a directed graph D which is both locating and dominating is denoted by γ^{LD}(D). Foucaud, Heydarshahi and Parreau proved that any twin-free digraph D satisfies γ^{LD}(D)≤4n5+1 but conjectured that this bound can be lowered to 2n/3. The conjecture is still open. They also proved that if D is a tournament, i.e. a directed graph where there is one arc between every pair of vertices, then γ^{LD}(D)≤⌈n/2⌉.
The main result of this paper is the generalization of this bound to connected local tournaments, i.e. connected digraphs where the in- and out-neighbourhoods of every vertex induce a tournament. We also prove γ^{LD}(D)≤2n/3 for all quasi-twin-free digraphs D that admit a supervising vertex (a vertex from which any vertex is reachable). This class of digraphs generalizes twin-free acyclic graphs, the most general class for which this bound was known.
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a 2^{o(k×log(k))} ×n^{O(1)}-time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3^k ×k^{O(1)}⋅n-time algorithm for FVS using the Cut&Count technique. During their live talk at IPEC 2020, Bergougnoux et al. posed a number of open questions, which we answer in this work:
A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. An eulerian factor of a 2-edge-coloured graph is a collection of vertex disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test if a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u,v)-paths ((u,v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u,v. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. We show that if G is an extension of an M-closed 2-edge-coloured complete graph, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. We also show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. Finally we pose a number of open problems.
A subset A of R² is said to avoid distance 1 if for all x and y in A, ||x-y||≠1. In this paper we study the number m_1(R²) which is the supremum of the upper densities of measurable sets avoiding distance 1 in the Euclidean plane. Intuitively, m_1(R²) represents the highest proportion of the plane that can be filled by a set avoiding distance 1. This parameter is related to the fractional chromatic number χ_f(R²) of the plane.
We establish that m_1(R²) ≤ 0.25646 and χ_f(R²) ≥ 3.8992.
We construct an infinite family of counterexamples to Thomassen's conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red such that the blue subgraph has maximum degree at most 1 and the red subgraph minimum degree at least 1 and contains no path on 4 vertices.
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is
permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted.
Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics.
We initiate the study of fundamental connectivity problems from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth).
On the other hand, we show an algebraic trick that yields tractability with treewidth parameterization of finding a properly colored Hamiltonian cycle in an edge-colored graph; properly colored walks in edge-colored graphs is one of the most studied special cases of compatible walks in forbidden-transition graphs.
The chromatic number of a digraph D is the minimum number of colors needed to color the vertices of D such that each color class induces an acyclic subdigraph of D. A digraph is k-critical if its chromatic number is k but the chromatic number of all its proper subdigraphs is strictly smaller than k. We examine methods for creating infinite families of critical digraphs, the Dirac join and the directed and bidirected Hajós join. We prove that a digraph D has chromatic number at least k if and only if it contains a subdigraph that can be obtained from bidirected complete graphs on k vertices by (directed) Hajós joins and identifying non-adjacent vertices. Building upon that, we show that a digraph D has chromatic number at least k if and only if it can be constructed from bidirected complete graphs of k vertices by using directed and bidirected Hajós joins and identifying non-adjacent vertices (also called Ore joins), thereby transferring a well-known result of Urquhart to digraphs. Finally, we prove a Gallai-type theorem that characterizes the structure of the low vertex subdigraph of a critical digraph, that is, the subdigraph, which is induced by the vertices that have in-degree k−1 and out-degree k−1 in D.
This paper studies the problem of connecting edge-colouring. Given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph i.e. a walk that does not use consecutively two edges of the same colour. We establish that the problem can be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with k colours for every possible value of k.
The weak 2-linkage problem for digraphs asks for a given digraph and vertices s1,s2,t1,t2 whether D contains a pair of arc-disjoint paths P1,P2 such that Pi is an (si,ti)-path. This problem is NP-complete for general digraphs but polynomially solvable for acyclic digraphs. Recently it was shown that if D is equipped with a weight function w on the arcs which satisfies that all edges have positive weight, then there is a polynomial algorithm for the variant of the weak-2-linkage problem when both paths have to be shortest paths in D. In this paper we consider the unit weight case and prove that for every pair constants k1,k2, there is a polynomial algorithm which decides whether the input digraph D has a pair of arc-disjoint paths P1,P2 such that Pi is an (si,ti)-path and the length of Pi is no more than d(si,ti)+ki, for i=1,2, where d(si,ti) denotes the length of the shortest (si,ti)-path. We prove that, unless the exponential time hypothesis (ETH) fails, there is no polynomial algorithm for deciding the existence of a solution P1,P2 to the weak 2-linkage problem where each path Pi has length at most d(si,ti)+c×log^{1+ϵ}(n) for some constant c. We also prove that the weak 2-linkage problem remains NP-complete if we require one of the two paths to be a shortest path while the other path has no restriction on the length.
DP-coloring is a relatively new coloring concept by Dvořák and Postle and was introduced as an extension of list-colorings of (undirected) graphs. It transforms the problem of finding a list-coloring of a given graph G with a list-assignment L to finding an independent transversal in an auxiliary graph whose vertices are the pairs (v,c) with v in V(G) and c in L(v). In this paper, we extend the definition of DP-colorings to digraphs using the approach from Neumann-Lara where a coloring of a digraph is a coloring of the vertices such that the digraph does not contain any monochromatic directed cycle. Furthermore, we prove a Brooks’ type theorem regarding the DP-chromatic number, which extends various results on the (list-)chromatic number of digraphs.
The maximal density of a measurable subset of R^n avoiding Euclidean distance 1 is unknown except in the trivial case of dimension 1. In this paper, we consider the case of a distance associated to a polytope that tiles space, where it is likely that the sets avoiding distance 1 are of maximal density (1/2)^n, as conjectured by Bachoc and Robins. We prove that this is true for n=2, and for the Vor onoï regions of the lattices A_n, n≥2.
This thesis studies combinatorial, algorithmic and complexity aspects of graph theory problems, and especially of problems related to the notions of walks, transitions and distances in graphs.
We first study the problem of traffic monitoring, in which we have to place as few censors as possible on the arcs of a graph to be able to retrace walks of objects. The characterization of instances of practical interests brings us to the notion of forbidden transitions, which strengthens the model of graphs. Our work on forbidden-transition graphs also includes the study of connecting transition sets, which can be seen as a translation to forbidden-transition graphs of the notion of spanning trees.
A large part of this thesis focuses on geometric graphs, which are graphs whose vertices are points of the real space and whose edges are determined by geometric distance between the vertices. This graphs are at the core of the famous Hadwiger-Nelson problem and are of great help in our study of the density of sets avoiding distance 1 in various normed spaces. We develop new tools to study these problems and use them to prove the Bachoc-Robins conjecture on several parallelohedra. We also investigate the case of the Euclidean plane and improve the bounds on the density of sets avoiding distance 1 and on its fractional chromatic number.
Finally, we study the complexity of graph homomorphism problems and establish dichotomy theorems for the complexity of locally-injective homomorphisms to reflexive tournaments.
A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the graph. In this paper, we look for the smallest set of transitions needed to be able to go from any vertex of the given graph to any other. We prove that this problem is NP-hard and study approximation algorithms. We develop theoretical tools that help to study this problem.
For oriented graphs G and H, a homomorphism f: G → H is locally-injective if, for every v in V(G), it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of v. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when H is a reflexive tournament on three or more vertices with a loop at every vertex, and Polynomial when H is a reflexive tournament on two or fewer vertices.
This paper studies the problem of traffic monitoring which consists of differentiating a set of walks on a directed graph by placing sensors on as few arcs as possible. The problem of characterising a set of individuals by testing as few attributes as possible is already well-known, but traffic monitoring presents new challenges that the previous models of separation fall short from modelling such as taking into account the multiplicity and order of the arcs in a walk. We introduce a new and stronger model of separation based on languages that generalises the traffic monitoring problem. We study three subproblems with practical applications and develop methods to solve them by combining integer linear programming, separating codes and language theory.
Despite most recent advances in structural variation discovery, many variants are yet to be discovered. Midsize insertions and deletions pose particularly involved algorithmic challenges. A prior method of ours (CLEVER) pointed out new ways. However, the resulting read alignment clusters tend to be too small and are heavily overlapping, which leads to losses in recall performance rates. Here we present a model based on \emph{weighted cluster editing}, which alleviates these issues: clusters are provably non-overlapping and tend to be larger. In order to render the inherent optimization problem tractable on all, and not just discordant, read alignment data of a genome, we present a novel, principled heuristic, which solves the problem in time linear in the length of the genome. The heuristic is based on an exact polynomial-time algorithm for weighted cluster editing in one-dimensional point graphs. We demonstrate that the new model improves recall rates achieved by CLEVER.