PhD scholarship on Constraints, Graphical Models and Algorithms

Title: New Decompositions to Solve Graphical Models

Laboratory: Laboratoire des Sciences de l’Information et des Systèmes (LSIS) – UMR CNRS 7296

Advisors: Philippe Jégou, Cyril Terrioux

The topic of this research project is at the border of Mathematics and Computer Science. Although located in

the domain of the foundations of constraint programming, this subject is based on the fundamental problem

of graph (and hypergraph) decomposition (Robertson & Seymour 1986) (Gottlob et al 2000) (Jégou &

Terrioux 2003). It is well known that constraint satisfaction problems (CSPs), also called constraint

networks, or more generally, Graphical Models (Dechter 2013, Koller & Friedman 2009) are represented by

graphs or hypergraphs. While solving Graphical Models is a NP-hard task, when the structure of the

networks representing the problem has some nice topological properties, it can be solved efficiently using

decomposition (Jégou & Terrioux 2016). In summary, the subject proposed here focuses on the

improvement of techniques for solving constraint satisfaction problems using decomposition. The integration

of such a technique induces practical problems, but also more fundamental questions related to the concept

of decomposition of graphs (or hypergraphs). Indeed, last years, several new mathematical tools have been

developed by theorists. One may cite, by their associated graph parameters, branch-width (Seymour &

Thomas 1994), clique-width (Courcelle & Olariu 2000), rank-width (Oum 2005), boolean-width (Bui-Xuan

et al. 2011), matching-width (Jeong et al 2015), modular-width (Gajarsky et al. 2013), treecut-width (Wollan

2015), or tree-depth (Nesetril & Ossona de Mendez, 2012), just to name a few. Unfortunately, there is a real

gap between such works, and their application to practical and efficient methods to solve Graphical Models.

One of the ambition of this line of research is to reduce this gap. The Ph.D. student based at LSIS will work

on the theoretical and practical aspects of new decompositions. We have seen the difficulties that may arise

passing from a graph decomposition, first introduced on a purely theoretical level, to the development of

solving methods efficient in practice. The design, the theoretical study, the implementation (even based on

toulbar2), experiments and improvements of this type of method is a work both difficult and substantial

which requires considerable time on the one hand, and a mastering of the whole context, from theoretical

foundations to experimental aspects.

Location: University of Aix-Marseille, Faculty of Sciences, LSIS, Marseille

These works are developed in the frame of the DEMOGRAPH programme, which is funded by the French

National Research Agency and associates three laboratories namely the Université de Montpellier - LIRMM -

UMR CNRS (Christophe Paul, Ignasi Sau, Dimitrios Thilikos, Christian Bessière, and Mamadou Kanté), the

UR875 INRA Toulouse (Thomas Schiex, Simon de Givry, George Katsirelos and David Allouche and the

LSIS (Marseille). DEMOGRAPH is the acronym (in French) for « Décomposition de Modèles Graphiques ».

The applicant will be member of INCA team at LSIS (this research team has been ranked A+ by the French

National Agency for Evaluation of Research (AERES) in 2012, its research has been considered as excellent

by the last evaluation (January, 2017 ; no ranking was considered this year).

Funding: the Ph.D. fellowship is funded for 3 years and is monthly funded about approximatively 1600 €.

Candidate Profile: Applicants should have (or in the process of getting) a M.Sc. in Computer Science,

Computer Engineering or a closely-related discipline (as Discrete Mathematics). Strong algorithmic and

mathematical skills are required. C++ or C development skills are desirable. The knowledge of French is

not required.

Start date: the position starts preferably in September / October 2017.

Application and contacts: Candidates must send their application before June 20th 2017 midnight:

- CV (at most 3 pages),

- Results and ranking for the M.Sc. (join a copy of marks),

- a cover letter,

- reference letters.

Applications must be sent by email with pdf files to philippe.jegou@univ- amu.fr and cyril.terrioux@univ-

amu.fr

2017-05-18
archive