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