Post-doc projet ANR Graphes Ordonnés, Décomposition, Algorithmes et Structure (M/F)

Job Description

Missions

The recruited researcher will work within the framework of the ANR project Ordered Graphs, Decompositions, Algorithms and Structures (GODASse).

Due to their simple definition and versatility in modeling complex systems, graphs play a central role in both theoretical and applied computer science. Complexity theory indicates that the design of efficient algorithms relies on exploiting the intrinsic combinatorial properties of the input data. It is often observed that algorithms with optimal running times include a preprocessing step consisting of equipping the input with additional structure. In graph algorithms, vertex orderings constitute such a structural enrichment, both simple and important. For instance, in the Kosaraju–Sharir algorithm, an ordering of the vertices obtained through a Depth-First Search (DFS) is used to compute the strongly connected components of a directed graph.

Interestingly, a vertex ordering may reveal useful hidden properties and provide characterizations of graph classes. For example, a graph is a forest if and only if there exists an ordering of its vertices such that every vertex has at most one neighbor among the preceding vertices. Another example is the classical Gallai–Roy–Vitaver theorem, which states that a graph is k-colorable if and only if there exists an ordering of its vertices that contains no forward path of length k.

These two examples motivate the definition of ordered graphs as a means of providing finite characterizations of graph classes. An ordered graph is a graph (G) equipped with a total ordering of its vertices. A (induced) pattern is an (induced) ordered subgraph of an ordered graph.

Given a fixed set (P) of ordered graphs, an ordering of the vertices of a graph is said to be P-free (or induced P-free) if the corresponding ordered graph excludes every pattern (or induced pattern) belonging to (P). Observe that the Gallai–Roy–Vitaver theorem characterizes the chromatic number of a graph through the existence of a vertex ordering excluding the forward path as an ordered subgraph.

We emphasize here an important dichotomy that will play a central role in the organization of our research project. On the one hand, as illustrated by the previous examples, we seek to determine an ordering of the vertices of a given graph in order to certify a property or design an efficient algorithm. The study of how to order a graph will constitute the main theme of the first work package (WP1).

On the other hand, a graph may come equipped with its own ordering, either explicit or intrinsic. For example, when a graph is stored in a computer, the memory addresses associated with its vertices implicitly define an ordering that may influence the execution of an algorithm (for instance, the order in which vertices are explored during a search procedure). An ordering also naturally arises when a graph is used to model a temporal or dynamic process. Furthermore, many graph classes are defined as intersection graphs of geometric objects; in such cases, the coordinates of these objects naturally induce an ordering of the vertices.

Remarkably, intersection graphs generally form well-structured graph classes on which it is often possible to design efficient algorithms for problems that are NP-hard in the general case. Our second work package (WP2) will be devoted to the study of such ordered graphs.

Many combinatorial or algorithmic graph properties can be expressed through the exclusion of a small graph. For example, planarity is equivalent to forbidding the two Kuratowski graphs as minors. Graph inclusion relations are therefore fundamental for understanding the combinatorics of graph classes. Among the most classical are monotone classes (closed under the subgraph relation), hereditary classes (closed under the induced subgraph relation), and minor-closed classes. The first two notions generalize directly to ordered graphs, and the ordered analogue of the minor relation plays an important role in this project.

Moreover, in order to express more general properties, we will also allow graphs to be equipped with a partial order on their vertices rather than a total order. The first such extension that we will consider is that of tree-orderings, used in the definition of the tree-depth parameter. As we shall see, orderings, tree-orderings, and inclusion relations for ordered graphs provide alternative and remarkably simple definitions of important structural parameters such as path-width and tree-width (see Section 1.2). This perspective thus offers a novel viewpoint on many existing results.

The above discussion can be extended in several directions that we intend to explore. The third work package (WP3) is therefore devoted to ordered structures beyond graphs. First, instead of undirected graphs, we will consider directed graphs and matrices, which can be viewed as weighted directed graphs. Furthermore, rather than ordering vertices, one may choose to order the edges of a graph; consequently, another research topic will be that of temporal graphs. These choices are deliberate, although many other extensions could also have been considered, notably toward scheduling problems or streaming algorithms.

As illustrated by the preceding discussion, orderings can be used to provide concise certificates for a wide variety of graph properties. While some known results are explicitly formulated in terms of orderings, many more fit naturally within this framework. This strongly suggests that the concept of ordered graphs and its various extensions is of fundamental importance and deserves systematic investigation.

Although a number of results on graph orderings and ordered graphs already exist, they remain scattered throughout the literature, and a unified theory is still lacking. The primary objective of this project is precisely to establish such a theory, encompassing both structural and algorithmic aspects.

Activity

- Carry out research in algorithms and graph theory, including literature surveys, the preparation of scientific publications, and participation in international conferences and workshops.
- Contribute to the scientific life of the ALGCO team through participation in seminars, working groups, and related activities.
- Participate in workshops and scientific events organized as part of the ANR GODASse project.

Your Profil

Skills

Applicants must hold a PhD in graph theory and algorithms.
A strong background in logic, graph decompositions, parameterized complexity, graph minor theory, and the theory of partial orders will be highly desirable.

Your Work Environment

The successful candidate will become a member of the ALGCO research team at the LIRMM. The team comprises 12 permanent faculty members and researchers, as well as several PhD students and postdoctoral fellows, and is active in the fields of graph theory and graph algorithms.

The GODASse project is a collaborative research initiative involving the MC2 team at the LIP (ENS Lyon) and the GA team at the IRIF (Paris).

Compensation and benefits

Compensation

From 3072 Euros gross per month depending on experience

Annual leave and RTT

44 jours

Remote Working practice and compensation

Pratique et indemnisation du TT

Transport

Prise en charge à 75% du coût et forfait mobilité durable jusqu’à 300€

About the offer

About the CNRS

The CNRS is a major player in fundamental research on a global scale. The CNRS is the only French organization active in all scientific fields. Its unique position as a multi-specialist allows it to bring together different disciplines to address the most important challenges of the contemporary world, in connection with the actors of change.

CNRS

The research professions