International Workshop on Graphs and Constraints


International Workshop on Graphs and Constraints

Affiliated to and co-located with:

The International Conference on Principles and Practice of Constraint Programming (CP 2018), Lille, France, August 27

Graphs and constraint programming have long been intimately connected in several ways. We only give a non-exhaustive list of such links:

Several of the areas sketched above have made big progress over the last few years. For example, the understanding of the micro structure of CSP instances has been better understood by considering forbidden patterns. Similarly, constraint based techniques for combinatorial problems have shown several conjectures that had been open for a long time. The goal of the International Workshop on Graphs and Constraints is thus to bring together researcher from these and other strains of research to present their work and exchange different perspectives.


We solicit contributions in the form of 1-2-page extended abstracts concerned with all aspects of current research that relates graphs and constraint programming, interpreted in a broad sense. Since there will be no proceedings, we explicitly solicit the submission of talk abstracts describing already published work and work in progress which falls into the scope of our workshop.

Submissions of the extended abstracts will be managed via Easychair:

Authors of accepted contributions are expected to give a talk at the workshop.

Important dates

Invited Speaker

Ciaran McCreesh (University of Glasgow)

Title: When hard subgraph problems are really hard, and why it matters

Abstract: In theory, subgraph finding is hard, but in practice we can solve real-world problems on graphs involving thousands of vertices. I'll explain how to generate "really hard" instances for subgraph problems, and show an unusual case where phase transitions do not explain observed behaviour but constrainedness does. I'll then discuss the real-world implications: I'll explain how over twenty years of research into "filter / verify" systems in graph databases has been futile, thanks to lessons from constraint programming not being heeded by the wider research community.

Program Comittee