Christine Solnon

AIJ Journal 2026 Journal Article

LAD2025, A constraint-based solver for the subgraph isomorphism problem

• Christine Solnon

The Subgraph Isomorphism Problem (SIP) is an N P -complete problem that aims at finding a copy of a pattern graph in a target graph. It may be modelled as a constraint satisfaction problem in a very straightforward way, and exact approaches for solving SIPs usually propagate constraints to reduce the search space. In particular, PathLAD is a solver introduced in 2016 that combines Locally All Different (LAD) constraints with path-based supplemental constraints. In this paper, we introduce LAD2025, which combines a complete refactoring of PathLAD with new features: new supplemental constraints, a weight-based variable ordering heuristic, random restarts with nogood recording, a new value ordering heuristic and a rule for selecting the level of filtering.

SAT Conference 2025 Conference Paper

Anytime and Exact Search for Planning Problems: How to Explore a DP-based State Transition Graph with A*, CP and LS? (Invited Talk)

• Christine Solnon

Many planning problems may be solved with Dynamic Programming (DP) by decomposing the problem into subproblems which are recursively solved. These decompositions induce state transition graphs which are closely related to decision diagrams [J. N. Hooker, 2013], and where optimal solutions correspond to best paths in these graphs. A* is a well known algorithm which extends Djikstra’s algorithm with heuristics for guiding the path search [Hart et al. , 1968]. It is exact (provided that the heuristic function is admissible), but it is not anytime. In other words, it computes a best path but it does not output sub-optimal paths while computing it. Hence, when state transition graphs have exponential sizes, A* may run out of time or memory without producing any solution. Various anytime extensions of A* have been proposed to compute a sequence of paths of increasing quality until finding an optimal path and proving its optimality. In this talk, we will provide an overview of these exact and anytime extensions of A*, with a more detailed focus on Anytime Column Search (ACS) [Vadlamudi et al. , 2012], and Iterative Memory Bounded A* (IMBA*) [L. Libralesso and F. Fontan, 2021]. Both approaches iterate A* searches while bounding the number of states that are stored or expanded at each iteration. We will also show how to combine them with Local Search (LS) in order to find better paths faster, and with bounding and constraint propagation in order to prune the graph, as proposed in [R. Fontaine et al. , 2023]. This will be illustrated using the Travelling Salesman Problem (TSP) as a running example. The DP formulation introduced by Bellman in [Bellman, 1962] for the TSP has been extended to handle Time Windows (TWs) in [Christofides et al. , 1981], and Time Dependent (TD) cost functions in [Malandraki and Dial, 1996]. It has also been extended to {Vehicle Routing Problems} (VRPs) in [van Hoorn, 2016] and to TD-VRPs in [Rifki et al. , 2020]. We will finish by presenting an experimental comparison with state-of-the-art approaches for solving the TSP with TWs on classical benchmarks and on a new benchmark which contains hard Euclidean instances located in the phase transition zone [O. Rifki and C. Solnon, 2025].

JAIR Journal 2025 Journal Article

On the Phase Transition of the Euclidean Travelling Salesman Problem with Time Windows

• Omar Rifki
• Christine Solnon

Algorithms are often evaluated on randomly generated instances to study scale-up properties with respect to features such as the size, for example. Also, machine learning based approaches often train models on randomly generated instances as they need large sets of training instances. In this paper, we consider the Euclidean Travelling Salesman Problem with Time Windows (TSPTW), and we study the impact of parameters used to randomly generate TSPTW instances on hardness and feasibility. We first consider the decision version of the problem, where feasibility depends on start and end times of time windows. We introduce two parameters, α and β, for controlling the tightness of the time horizon and the time windows. We show that instance hardness is related to a phase transition phenomenon: as we increase α and β, we pass from an unfeasible region (where almost all generated instances have no solution) to a feasible region (where almost all generated instances have solutions), and the hardest instances are located within the transition zone. We formally relate this transition zone with respect to α and β, thus allowing us to control hardness and feasibility when randomly generating instances. Then, we study the optimization problem, the goal of which is to find the smallest tour that satisfies all time windows. We show that the empirical hardness is still related to the phase transition: hardness increases when moving from the infeasible region to the transition zone, as in the decision problem. However, unlike the decision problem, some hard instances are also located in the feasible region where instances are very loosely constrained.

JAIR Journal 2023 Journal Article

Non-Crossing Anonymous MAPF for Tethered Robots

• Xiao Peng
• Olivier Simonin
• Christine Solnon

This paper deals with the anonymous multi-agent path finding (MAPF) problem for a team of tethered robots. The goal is to find a set of non-crossing paths such that the makespan is minimal. A difficulty comes from the fact that a safety distance must be maintained between two robots when they pass through the same subpath, to avoid collisions and cable entanglements. Hence, robots must be synchronized and waiting times must be added when computing the makespan. We show that bounds can be efficiently computed by solving linear assignment problems. We introduce a variable neighborhood search method to improve upper bounds, and a Constraint Programming model to compute optimal solutions. We experimentally evaluate our approach on three different kinds of instances.

JAIR Journal 2020 Journal Article

A Global Constraint for the Exact Cover Problem: Application to Conceptual Clustering

• Maxime Chabert
• Christine Solnon

We introduce the exactCover global constraint dedicated to the exact cover problem, the goal of which is to select subsets such that each element of a given set belongs to exactly one selected subset. This NP -complete problem occurs in many applications, and we more particularly focus on a conceptual clustering application. We introduce three propagation algorithms for exactCover, called Basic, DL, and DL+: Basic ensures the same level of consistency as arc consistency on a classical decomposition of exactCover into binary constraints, without using any specific data structure; DL ensures the same level of consistency as Basic but uses Dancing Links to efficiently maintain the relation between elements and subsets; and DL+ is a stronger propagator which exploits an extra property to filter more values than DL. We also consider the case where the number of selected subsets is constrained to be equal to a given integer variable k, and we show that this may be achieved either by combining exactCover with existing constraints, or by designing a specific propagator that integrates algorithms designed for the NValues constraint. These different propagators are experimentally evaluated on conceptual clustering problems, and they are compared with state-of-the-art declarative approaches. In particular, we show that our global constraint is competitive with recent ILP and CP models for mono-criterion problems, and it has better scale-up properties for multi-criteria problems.

AIJ Journal 2020 Journal Article

Computing AES related-key differential characteristics with constraint programming

• David Gerault
• Pascal Lafourcade
• Marine Minier
• Christine Solnon

Cryptanalysis aims at testing the properties of encryption processes, and this usually implies solving hard optimization problems. In this paper, we focus on related-key differential attacks for the Advanced Encryption Standard (AES), which is the encryption standard for block ciphers. To mount these attacks, cryptanalysts need to solve the optimal related-key differential characteristic problem. Dedicated approaches do not scale well for this problem, and need weeks to solve its hardest instances. In this paper, we improve existing Constraint Programming (CP) approaches for computing optimal related-key differential characteristics: we add new constraints that detect inconsistencies sooner, and we introduce a new decomposition of the problem in two steps. These improvements allow us to compute all optimal related-key differential characteristics for AES-128, AES-192 and AES-256 in a few hours.

JAIR Journal 2018 Journal Article

When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases

• Ciaran McCreesh
• Patrick Prosser
• Christine Solnon
• James Trimble

The subgraph isomorphism problem involves deciding whether a copy of a pattern graph occurs inside a larger target graph. The non-induced version allows extra edges in the target, whilst the induced version does not. Although both variants are NP-complete, algorithms inspired by constraint programming can operate comfortably on many real-world problem instances with thousands of vertices. However, they cannot handle arbitrary instances of this size. We show how to generate "really hard" random instances for subgraph isomorphism problems, which are computationally challenging with a couple of hundred vertices in the target, and only twenty pattern vertices. For the non-induced version of the problem, these instances lie on a satisfiable / unsatisfiable phase transition, whose location we can predict; for the induced variant, much richer behaviour is observed, and constrainedness gives a better measure of difficulty than does proximity to a phase transition. These results have practical consequences: we explain why the widely researched "filter / verify" indexing technique used in graph databases is founded upon a misunderstanding of the empirical hardness of NP-complete problems, and cannot be beneficial when paired with any reasonable subgraph isomorphism algorithm.

IJCAI Conference 2017 Conference Paper

Using Constraint Programming to solve a Cryptanalytic Problem

• David Gerault
• Marine Minier
• Christine Solnon

We describe Constraint Programming (CP) models to solve a cryptanalytic problem: the chosen key differential attack against the standard block cipher AES. We show that CP solvers are able to solve these problems quicker than dedicated cryptanalysis tools, and we prove that a solution claimed to be optimal in two recent cryptanalysis papers is not optimal by providing a better solution.

TCS Journal 2013 Journal Article

Polynomial algorithms for open plane graph and subgraph isomorphisms

• Colin de la Higuera
• Jean-Christophe Janodet
• Émilie Samuel
• Guillaume Damiand
• Christine Solnon

Graphs are used as models in a variety of situations. In some cases, e. g. to model images or maps, the graphs will be drawn in the plane, and this feature can be used to obtain new algorithmic results. In this work, we introduce a special class of graphs, called open plane graphs, which can be used to represent images or maps for robots: they are planar graphs embedded in the plane, in which certain faces can be removed, are absent or unreachable. We give a normal form for such graphs and prove that one can check in polynomial time if two normalised graphs are isomorphic, or if two open plane graphs are equivalent (their normal forms are isomorphic). Then we consider a new kind of subgraphs, built from subsets of faces and called patterns. We show that searching for a pattern in an open plane graph is tractable if and only if the faces are contiguous, that is, we prove that the problem is NP -complete otherwise.

TCS Journal 2011 Journal Article

Efficient search of combinatorial maps using signatures

• Stéphane Gosselin
• Guillaume Damiand
• Christine Solnon

In this paper, we address the problem of computing canonical representations of n -dimensional combinatorial maps and of using them for efficiently searching for a map in a database. We define two combinatorial map signatures: the first one has a quadratic space complexity and may be used to decide an isomorphism with a new map in linear time whereas the second one has a linear space complexity and may be used to decide an isomorphism in quadratic time. We show that these signatures can be used to efficiently search for a map in a database.

AIJ Journal 2010 Journal Article

AllDifferent-based filtering for subgraph isomorphism

• Christine Solnon

The subgraph isomorphism problem involves deciding if there exists a copy of a pattern graph in a target graph. This problem may be solved by a complete tree search combined with filtering techniques that aim at pruning branches that do not contain solutions. We introduce a new filtering algorithm based on local all different constraints. We show that this filtering is stronger than other existing filterings — i. e. , it prunes more branches — and that it is also more efficient — i. e. , it allows one to solve more instances quicker.

ECAI Conference 2000 Conference Paper

Solving Permutation Constraint Satisfaction Problems with Artificial Ants

• Christine Solnon

LOPSTR Conference 1994 Conference Paper

Propagation of Inter-argument Dependencies in "Tuple-distributive" Type Inference Systems

• Christine Solnon
• Michel Rueher

Abstract Many type inference systems for Prolog programs are based on the tuple-distributive closure abstraction which ignores inter-argument dependencies. Thus, dependencies specified by head-only shared variables cannot be handled, and the inferred types are often very inaccurate. In this paper, we define an unfolding process which propagates such inter-argument dependencies: each call to a predicate that contains head-only shared variables is replaced by its definition. Hence, dependencies are actually propagated and the accuracy of the inferred types is improved. This unfolding process is repeated until a fix-point is reached in the computation of the type system. Termination is ensured by an abstraction function which limits the depth of recursive structures.

LPAR Conference 1993 Conference Paper

Extracting Inheritance Hierarchies from Prolog Programs: A System Based on the Inference of Type Relations

• Christine Solnon
• Michel Rueher

Abstract We propose in this paper a type inference system for extracting inheritance hierarchies from Prolog programs. The inferred types define a superset of the denotation of the program, and a subset of the least fixed point of the tuple-distributive closure of the immediate consequence operator T P (i. e. , 1fp( α (T P )). The types are described by means of their relationships with other types of the program rather than by their instances. Thus, we infer a collection of not resolved formulas that describe set relationships between the terms appearing in the program. We have nevertheless defined an interpretation function from the type relations into the Herbrand universe that allows us to actually compute the set of ground terms associated with each type. The inferred type relations are used for defining two inheritance hierarchies. The first one is obtained through a formal comparison of the type relations, and is independent of the program's data, whereas the second one is obtained through the comparison of the interpretations of the types and is directly dependent of the program's data. These two hierarchies provide a scheme of the program that enables a better understanding of the underlying structure. Their comparison may outline some errors or incompleteness of the program.

LOPSTR Conference 1992 Conference Paper

Using a Prolog Prototype for Designing an Object Oriented Scheme

• Christine Solnon
• Michel Rueher

Abstract The purpose of this paper is to define a reverse engineering technique for recovering structural design information through the analysis of a Prolog prototype. Prolog is widely used for making prototypes due to its high level of abstraction, and object oriented programming has emerged as a successful paradigm for software development. However, object oriented modelling is difficult to achieve. Thus, we propose to extract an object oriented scheme from the Prolog prototype. We show that the identification of the inclusion polymorphism expressed by Prolog clauses allows us to define an inheritance hierarchy. In the first section, we define a polymorphic denotational type system for Prolog, and we show that a Prolog program expresses relationships between types which allow us to capture inclusion polymorphism. In the second section, we present an algorithm that infers relationships between types expressed in a Prolog program. These relationships are used to define an object oriented scheme, where the inheritance hierarchy only depends on the semantic relations specified by the clauses of the program. Finally, we compare our approach with some related works, and we show the advantage of our system for well capturing inheritance relations.