Steven Gay
email: steven.gay@inria.fr

François Fages
email: francois.fages@inria.fr

Thierry Martinez
email: thierry.martinez@inria.fr

Sylvain Soliman
email: sylvain.soliman@inria.fr

Christine Solnon
email: christine.solnon@liris.cnrs.fr

On The Subgraph Epimorphism Problem

Keywords: Subgraph epimorphim, Model reduction, Graph distance, Constraint solving, Systems biology

In this paper we study the problem of deciding the existence of a subgraph epimorphism between two graphs. Our interest in this variant of graph matching problem stems from the study of model reductions in systems biology, where large systems of biochemical reactions can be naturally represented by bipartite digraphs of species and reactions. In this setting, model reduction can be formalized as the existence of a sequence of vertex deletion and merge operations that transforms a first reaction graph into a second graph. This problem is in turn equivalent to the existence of a subgraph (corresponding to delete operations) epimorphism (i.e. surjective homomorphism, corresponding to merge operations) from the first graph to the second. In this paper, we study theoretical properties of subgraph epimorphisms in general directed graphs. We first characterize subgraph epimorphisms (SEPI), subgraph isomorphisms (SISO) and graph epimorphisms (EPI) in terms of graph transformation operations. Then we study the graph distance measures induced by these transformations. We show that they define metrics on graphs and compare them. On the algorithmic side, we show that the SEPI existence problem is NP-complete by reduction of SAT, and present a constraint satisfaction algorithm that has been successfully used to solve practical SEPI problems on a large benchmark of reaction graphs from systems biology.

Introduction

Our interest in subgraph epimorphisms stems from the study of model reductions in systems biology, where large systems of biochemical reactions can be naturally represented by bipartite digraphs of species and reactions [START_REF] Venkatramana | Petri net representations in metabolic pathways[END_REF][START_REF] Hofestädt | A petri net application to model metabolic processes[END_REF]. In this setting, one can define a very general notion of model reduction as a particular form of graph transformation and use it to compare models in systems biology model repositories [START_REF] Gay | A graphical method for reducing and relating models in systems biology[END_REF].

Let us consider, for example, the reduction of Michaelis-Menten in figure 1. The left-hand side graph is a detailed model composed of three reactions where an enzyme E binds in a reversible manner to a substrate S to form a complex ES and release a product P . The righthand side graph reduces this system to a single reaction catalyzed by the enzyme.

The reduced graph can be obtained from the source graph by a sequence of delete and merge operations on species and reaction vertices. These transformations can typically be justified in chemistry by considering: (i) reaction deletions for slow reverse reactions, (ii) reaction mergings for reaction chains with a limiting reaction, (iii) molecular species deletions for species in excess and (iv) molecular mergings for quasi-steady state approximations. This operational view of graph reduction by graph transformation operations is equivalent to the existence of a subgraph (corresponding to delete operations) epimorphism (i.e. surjective homomorphism, corresponding to merge operations) from a source graph to a reduced graph. Subgraph epimorphisms (SEPI) differ from subgraph isomorphisms (SISO) by allowing merge operations in addition to delete operations. On undirected graphs, SEPIs differ from minors [START_REF] Lovász | Graph minor theory[END_REF] with respect to the three following points: (i) non adjacent vertices may be merged, (ii) merging adjacent vertices creates loops, and (iii) arcs cannot be deleted without deleting or merging vertices.

In this paper, we study the theoretical properties of SEPIs in general directed graphs and relate these properties with other standard notions of graph homomorphisms [START_REF] Hell | Graphs and Homomorphisms[END_REF], namely subgraph isomorphisms, minors and graph epimorphisms (EPI).

Main results and overview of the paper. In Section 2, we introduce three partial orders on digraphs respectively based on SEPI, SISO and EPI, and show that, unlike the minor relation, they are not well quasi orders. In Section 3, we introduce three graph distance measures, respectively based on SEPI, SISO and EPI, and we compare them. We show that they are metrics and that these distances are equivalent to graph edit distances defined as the minimum number of edit operations that transform a first graph into another one. In Section 5, we show the NP-completeness of the SEPI existence problem. In Section 6, we present a constraint satisfaction algorithm that has been successfully used to solve practical SEPI problems on a large benchmark of reaction graphs from systems biology. In Section 7, we discuss extensions to non directed and bipartite graphs.

Partial Order Relations SISO, EPI and SEPI

Notations and Definitions

A directed graph, or graph for short in this paper, is a pair (V, A) where V is a finite set of vertices and A ⊆ V × V a set of arcs. The cardinality of a set S is denoted |S|. The size |G| of a graph G = (V, A) is its number of vertices, |G| = |V |.

For the remainder of this section, G and G denote graphs, with G = (V, A) and G = (V , A ). Definition 2.1 (Graph isomorphism). An isomorphism from G to G is a bijective function

f : V → V such that (u, v) ∈ A iff (f (u), f (v)) ∈ A .
Two graphs G and G are isomorphic when there exists a graph isomorphism from G to G . Graph isomorphism is an equivalence relation on directed graphs: we note G the set of all graphs quotiented by this equivalence relation.

Definition 2.2 (Graph epimorphism). An epimorphism ( EPI

) from G to G is a surjective function f : V → V such that • for all u, v ∈ V , if (u, v) ∈ A, then (f (u), f (v)) ∈ A (graph homomorphism),

and,

• for all (u , v ) ∈ A , there exists (u, v) ∈ A such that f (u) = u and f (v) = v (surjectivity on arcs).

If f is bijective, then f is a graph isomorphism. Graph epimorphisms relax the bijection constraint of graph isomorphisms to a surjection constraint on both vertices and arcs (hence the terminology of epimorphism) so that several vertices of G may be mapped on a same vertex of G . Graph epimorphisms are closely related to graph compactions: on the class of irreflexive graphs (graphs without loops), graph epimorphisms are actually equivalent to graph compactions [START_REF] Vikas | Computational Complexity of Graph Compaction[END_REF]. Graph epimorphisms are also closely related to quotient graphs (see Section 4.3).

Definition 2.3 (Induced subgraph). Let U ⊆ V be a subset of vertices of G. The subgraph of G induced by U is G ↓U = (U, A ∩ (U × U )). Definition 2.4 (Subgraph isomorphism). A subgraph isomorphism (SISO) from G to G is an isomorphism f from an induced subgraph G 0 of G to G .
G 0 is the domain of f , denoted by dom f . These notions thus define three relations over directed graphs, we write

Definition 2.5 (Subgraph epimorphism). A subgraph epimorphism (SEPI) from G to G is an epimorphism f from an induced subgraph G 0 of G to G . G 0 is also denoted dom f .
• G EPI G if there exists a graph epimorphism from G to G ; • G SEPI G if there exists a subgraph epimorphism from G to G ; • G SISO G if there exists a subgraph isomorphism from G to G .
One can easily check that the three relations SEPI , EPI and SISO are partial orders over G.

Morphisms and Graph Operations

These relations are also closely related to graph transformations by delete and/or merge operations. The delete operation removes a vertex v from a graph G, together with every arc incident to v. In other words, it reduces G to the subgraph induced by all vertices but v.

Definition 2.6 (Delete). Let u ∈ V . The result of the deletion of u in G is the induced subgraph d u (G) = G ↓V \{u} . We write G → d G whenever ∃u, G = d u (G).
The merge operation removes two vertices from a graph and replaces them with a new one inheriting all incident arcs. Definition 2.7 (Merge). Let u, v ∈ V such that u = v, and let uv be a new symbol such that uv ∈ V . The result of the merge of u and v in G is the graph m

u,v (G)=(V , A ) such that V = V \ {u, v} ∪ {uv} and A = A ∩ (V × V ) ∪ {(uv, w) | (u, w) ∈ A or (v, w) ∈ A} ∪ {(w, uv) | (w, u) ∈ A or (w, v) ∈ A}. We write G → m G whenever ∃u, v, G = m u,v (G).
We have shown in [START_REF] Gay | A graphical method for reducing and relating models in systems biology[END_REF] that these graph operations enjoy the following commutation and association properties:

G G G 1 G 2 G 1 G 3 G 2 G G m u,v m uv,w m v,w m u,vw d v d u d u d v m u,v d uv
These permutation properties establish the equivalence between the existence of a (sub)epimorphism from one graph to another one and the existence a finite sequence of delete and/or merge operations leading from the first graph to the second. This is also true for subgraph isomorphisms:

Definition 2.8. We write G → md G if G → d G or G → m G . Let o ∈ {m, d, md}. We write G ← o G if G → o G , whenever it is convenient. We write G 1 R G 2 R G 3 if G 1 R G 2 ∧ G 2 R G 3 . We write G R * G whenever there is a string of R relations from G to G , i.e whenever G = G or ∃G 1 ∈ G s.t. G R G 1 R * G . Theorem 1 ([8]). G EPI G if and only if G → * m G . G SEPI G if and only if G → * md G . G SISO G if and only if G → * d G .

Properties

SEPI is related to both EPI and SISO since graph epimorphisms and subgraph isomorphisms are subgraph epimorphisms, i.e., ( EPI ∪ SISO ) ⊆

SEPI

Hereditary properties have been widely studied for SISO and there exist many properties that are preserved by vertex deletions [START_REF] Bollobás | Hereditary and monotone properties of graphs[END_REF][START_REF] Borowiecki | Hereditary properties of graphs[END_REF]. However, most of these properties are not preserved when considering both delete and merge operations. This comes from the fact that not only vertex mergings preserve less properties than vertex deletions, but the properties preserved by the two operations are often incompatible.

Nevertheless, one can easily check that SEPIs preserve a few graph properties.

Proposition 2. Graph completeness is preserved by SEPIs.

Proposition 3. Arc symmetry is preserved by SEPIs.

This proposition shows that SEPIs are well defined on undirected graphs.

Definition 2.9 (Non-neighbors). The set of outgoing (respectively incoming) non-neighbors of a vertex u in a graph G is the set of vertices

ON N (u, G) = {v ∈ V | (u, v) / ∈ A} (respectively IN N (u, G) = {v ∈ V | (v, u) / ∈ A}).
These non-neighbor sets are monotonic with respect to SEPI:

Proposition 4. Let f be a SEPI from G to G . Then, for any vertex x ∈ dom f , f (ON N (x, G)) ⊇ ON N (f (x), G ), and f (IN N (x, G)) ⊇ IN N (f (x), G ).
Proof. If ON N (x , G ) = ∅, the case is immediately proved. Suppose ON N (x , G ) = ∅, and let y ∈ ON N (x , G ). By surjectivity of f , let y such that f (y) = y . We have (x , y ) / ∈ A , so, since f is a morphism, (x, y) / ∈ A. Thus y ∈ ON N (x, G), which proves y ∈ f (ON N (x, G)).

The proof for IN N is similar.

It is worth noting that SEPIs differ from minors in several ways: (i) minors allow the deletion of any arcs whereas SEPIs only allow the deletion of vertices with their adjacent arcs (ii) SEPIs allow the merging of non adjacent vertices whereas minors only allow the merging of adjacent vertices and (iii) SEPIs create loops when merging adjacent vertices, whereas minors don't. Being a graph minor is a partial order over the set of undirected graphs and this partial order is a well-quasi-ordering [START_REF] Robertson | Graph minors. XX. Wagner's conjecture[END_REF]. This is not the case for SEPI: Proposition 5. SEPI is not a Well-Quasi-Order.

Proof. One can exhibit an infinite antichain of graphs for SEPI. Let

G n = (V n , A n ) for n ≥ 5, with V n = {1...n} and A n = {(i, j) such that |i -j| > 1[n]}. . . . v 1 v 2 v 3 v 4 v 5 v 1 v 2 v 3 v 4 v 5 v 6 v 1 v 2 v 3 v 4 v 5 v 6 v 7
This family is an infinite antichain for SEPI. First, one can easily check that ∀n, ∀u ∈ V n , |ON N (x, G n )| = 3 (in absence of loop a vertex is in its own ONN set). Let f be a SEPI from G n to G m , with n ≥ m.

Second, f does not delete any vertex. Suppose D = {i | i ∈ dom f } is not empty. D cannot be V n either, or G m would not have any vertex. So there exists i such that one vertex in {i, (i + 1)[n]} is deleted and the other is not. Without loss of generality, say i is not deleted and (i + 1)[n] is. Then, by Property 4, f (i) has at most 2 outgoing non-neighbors in G m : itself and, if defined, the image of (i -1)[n]. This is impossible, since every vertex of G m has exactly 3 outgoing non-neighbors.

Next, f does not merge any vertices. Suppose f merges i with at least another vertex j. i and j have at most two outgoing non-neighbors in common. Indeed, let us remind that G n is defined for n ≥ 5: they have either two outgoing neighbors in common (when |i -j| = 1[n]), one (when |i -j| = 2[n]), or none (when |i -j| > 2[n]). Merging i and j makes them lose their outgoing non-neighbors not in common, thus they lose at least one outgoing non-neighbor, which is once again impossible.

Finally, f must be the identity so that n = m. Corollary 6. EPI and SISO are not Well-Quasi-Orders.

Proof. Just notice that an antichain for SEPI is also an antichain for EPI and SISO.

Graph Edit Distance

Each of the three relations introduced in Section 2 may be used to compare some graphs. However, some other graphs cannot be compared as these relations are not total orders.

The distance between two graphs G 1 and G 2 can be defined in two main ways:

(i) in a denotational way, by means of the size of a largest subgraph common to G 1 and G 2 ;

(ii) in an operational way, by means of the minimum cost sequence of graph edit operations that should be performed to transform

G 1 into G 2 .
In [START_REF] Bunke | On a relation between graph edit distance and maximum common subgraph[END_REF], Bunke has connected these two definitions by introducing a special cost function for the graph edit distance and by showing that under this cost function the graph edit distance problem is equivalent to the maximum common subgraph computation.

While it is always possible to transform one graph into another by performing a sequence of vertex insertion and deletion operations, the size of such a sequence may not be representative of the similarity of the two graphs. Indeed, in some applicative contexts, it is more relevant to measure the distance between two graphs not only by means of vertex insertion and deletion operations but also by means of vertex merge and split operations, thus leading to the extended graph edit distance [START_REF] Ambauen | Graph edit distance with node splitting and merging[END_REF][START_REF] Champin | Measuring the similarity of labeled graphs[END_REF].

In this section, we introduce a graph edit distance corresponding to delete and merge operations. This distance is a simplified case of the extended graph edit distance introduced in [START_REF] Ambauen | Graph edit distance with node splitting and merging[END_REF], which has been defined for labeled graphs and is parameterized by edit costs. In the next section, we shall relate our graph edit distance to SEPI, EPI, and SISO.

Let us first define the edition graphs, which associate a vertex with every graph of G, and an arc with every pair of graphs that can be transformed by applying one operation. Three different edition graphs can be defined according to the different kinds of operation that may be applied, i.e., m (merge), d (delete) or md (merge or delete).

E o = (G, A o ) such that A o = {(G 1 , G 2 ) ∈ G × G | G 1 → o G 2 }.
These edition graphs are not strongly connected. For example, there is no path from any graph G to any graph G that has more vertices than G, as for every arc

G 1 → o G 2 , we have |G 2 | = |G 1 | -1.
This prevents us from defining a metric using paths. However, there is a natural definition using the walks of E o . A path from s to t only crosses arcs forwards, walks extend paths by allowing to cross arcs forwards and backwards: Definition 3.2 (Walk of a graph). Let G = (V, A) be a graph, and s, t be vertices of

G. A walk w from s to t is a finite sequence w = (a 1 . . . a n ) of arcs of A such that ∃x 0 . . . x n ∈ V, x 0 = s, x n = t, and ∀i, 1 ≤ i ≤ n, a i = (x i-1 , x i ) ∨ a i = (x i , x i-1 ).
The length of w is |w| = n.

Let us now define a graph edit distance as the length of a shortest walk.

Definition 3.3 (Distance). Let o ∈ {m, d, md}, and G 1 , G 2 ∈ G. The distance d o : G → N ∪ {+∞} is d o (G 1 , G 2 ) = min{|w| s.t. w is a walk of E o from G 1 to G 2 } if a walk exists d o (G 1 , G 2 ) = +∞ otherwise.
Example 2. On the graphs G and G of the Michaelis-Menten reduction given in the introduction, we have

d md (G, G ) = 3 d m (G, G ) = 3 d d (G, G ) = 5
For o ∈ {d, md}, the distance d o (G, G ) is never +∞, as there always exists a walk from G to G that goes through the empty graph. However, when o = m, it may happen that d o (G, G ) = +∞. This is the case, for example, when G has no arcs whereas G has at least one arc.

One can easily check that d o is a metric on G as it satisfies the non-negativity, symmetry, separability and triangular inequality properties.

Proposition 7. Let G, G ∈ G. Then: d md (G, G ) ≤ d m (G, G ) d md (G, G ) ≤ d d (G, G ) d m (G, G ) ≤ 3d d (G, G )
Proof. The two first inequalities can be proved using E md ⊇ E m and E md ⊇ E d . The third can be proved by simulating every merge operation by the deletion of both vertices to be merged, and addition (undeletion) of the merged vertex.

Relationship between d o and EPI, SEPI and SISO

In [START_REF] Bunke | On a relation between graph edit distance and maximum common subgraph[END_REF], Bunke has shown that the graph edit distance that only considers vertex deletions (i.e., d o when o = d) is related to the size of the maximum common subgraph. In this section, we extend this result to graph edit distances that consider vertex merges (i.e., d o when o ∈ {m, md}) by relating them to EPI and SEPI.

To show this relationship, we show that for any walk w of It is however possible to restrict the exploration of walks to those walks that change directions at most once, by first only going down arcs and then only going up. In order to show this, we introduce quotients of graphs by equivalence relations.

Preliminaries on Equivalence Relations

In this section, S is a finite set. A binary relation α over S is called an equivalence relation over S iff it has the following properties:

• reflexivity : ∀x ∈ S, (x, x) ∈ α • symmetry : ∀x ∈ S, ∀y ∈ S, (x, y) ∈ α ⇒ (y, x) ∈ α • transitivity : ∀x ∈ S, ∀y ∈ S, ∀z ∈ S, (x, y) ∈ α ∧ (y, z) ∈ α ⇒ (x, z) ∈ α
, denoted [x] α , is [x] α = {y ∈ A | (x, y) ∈ α}. The set of classes modulo α, denoted S/α, is S/α = {[x] α | x ∈ S}. Definition 4.2 (Transitive closure). Let α ⊆ X × Y, β ⊆ Y × Z. The composition of α and β is α • β = {(x, z) | ∃y, (x, y) ∈ α ∧ (y, z) ∈ β}.
The transitive closure of α is the relation α + = ∪ ∞ i=1 α i with α 1 = α and ∀i ≥ 2, α i+1 = α•α i . The reflexive transitive symmetric closure of α is the relation

α ≡ = {(x, y) | (x, y) ∈ α ∨ (y, x) ∈ α ∨ x = y} + .
For any α, α ≡ is an equivalence relation, the smallest containing α.

Dimension of an Equivalence Class

For the remainder of this section, let α and β be equivalence classes over S. s is called a spanning of α iff s ≡ = α. s is called a free family (or just free for short) iff it has no loops and no cycles.

As subsets of S × S, spannings are ordered by inclusion. The minimal spannings are free, analogously to minimal generating families in vector spaces. Minimal spannings share a common size, which enables the definition of dimension: Proposition 8. Let s be a spanning of α. Then s is minimal iff s is free.

In We have s ⊆

[x]α∈E/α [x] α × [x] α , so s = [x]α∈E/α s ∩ ([x] α × [x] α ). Since s ∩ ([x] α × [x] α ) is a free spanning of [x] α × [x] α , the argument for n = 1 gives |s ∩ ([x] α × [x] α )| = |[x] α | -1. So |s| = [x]α∈E/α (|[x] α | -1) = |E| -|E/α|.
To conclude, every free spanning has cardinality |E| -|E/α|. If s 0 ⊆ s with s 0 minimal, since s 0 is also free, |s 0 | = |s|, so s = s 0 and s minimal.

From Property 8, one can define the dimension of an equivalence relation as follows:

Definition 4.5. The dimension dim(α) of α is the the size of its minimal spannings |E|-|E/α|.

One can then show a theorem analogous to the incomplete basis theorem: Theorem 9. Let s ⊆ α be a free family. Then there is a minimal spanning t of α that contains s.

Proof. Let us build an increasing sequence of free families of α that contains s. Let s 0 = s. If s n doesn't span α, then for any (x n , y n ) ∈ α -s ≡ n , s n ∪ {(x n , y n )} is free. In this case we define s n+1 = s n ∪ {(x n , y n )}. This sequence grows strictly within a finite set, so it has to stop at some m. Then s m has to span α. Since s m is free, it is minimal.

Next, we show that maximal free families are generating families.

Proposition 10. Let s ⊆ α be free.

If s is a maximal free family, then s is a spanning of α.

If s has size dim(α), then s is a spanning of α.

Proof. For the first assertion, suppose s doesn't span α, that is, ∃(x, y) ∈ α -s ≡ . Then x = y, since s ≡ is reflexive. Since s ∪ {(x, y)} is not free, it must have a cycle that must contain (x, y), with every other arc of the cycle in s. This last statement means that (x, y) ∈ s ≡ , which is absurd.

For the last assertion, suppose free family s ⊆ α has size dim(α). Using Theorem 9, let t be a minimal spanning of α that contains s. Since dim(α) = |t| ≥ |s| = dim(α), we have s = t.

Proposition 11. dim(α * β) ≤ dim(α) + dim(β)
Proof. Let s, t be minimal spannings of α, β. s ∪ t is a spanning of α * β, with |s ∪ t| ≤ |s| + |t|; a minimal spanning will be even smaller.

The equality case gives an interesting result: in this case, for every s, t minimal spannings of α, β, s ∪ t has no cycle.

Quotients of Graphs by Equivalence Relations

In this section, G = (V, A) is a directed graph (i.e. A ⊆ V × V ), and α, β are equivalence classes over V .

G/α = ({[x] α | x ∈ V }, {([x] α , [y] α ) | (x, y) ∈ A}).
Notice that G/α has |V /α| vertices. Graph epimorphisms and graph quotients are strongly linked, in the sense conveyed by the following theorem: Theorem 12. There exists an epimorphism f from G to G iff there exists an equivalence relation

α over V such that G/α is isomorphic to G . Proof. ⇒ Let α = {(x, y) ∈ V 2 | f (x) = f (y)}. Then G/α is isomorphic to G . ⇐ Let f : V → P(V ) such that ∀u ∈ V, f (u) = [u] α . Then f is an epimorphism from G to G/α.
We shall use a classical theorem about equivalence classes.

Theorem 13. Let γ be an equivalence relation with α ⊆ γ. Then γ/α is an equivalence relation over V /α, and dim(γ/α) = dim(γ) -dim(α).

Proof. Showing that γ/α is an equivalence class over V /α is easy. The result on dimensions is less well-known.

Let s be a minimal spanning of α. From Property 8 s is a free family of γ, so by Property 9, there is a t ⊇ s that is a minimal spanning of γ. t being a graph, we can consider quotienting it by α. One can show that t/α is actually a spanning of γ/α. Now t/α generally contains loops and may not be a minimal spanning. Let t 0 = t -s. The arcs s/α are exactly the loops of t/α, which means (t 0 /α) ≡ = (t/α) ≡ = γ/α One can prove that t 0 /α is free, and its size is |t| -|s|, which allows us to conclude on the dimension of γ/α. Proposition 14. Let γ an equivalence relation such that α ⊆ γ. Then (G/α)/(γ/α) is isomorphic to G/γ.

Proof. Notice how the vertices of G/γ are subsets of V , and the vertices of (G/α)/(γ/α) are subsets of subsets of V . It is easy to check that m : X ∈ V /α -→ x∈X x is an isomorphism from the latter graph to the former.

Graph Distances and Homomorphisms

We now show a practical way to compute distances d o by restricting the search space. Let us begin by a simple property of our operations. Let us show that in E d , there is always a short walk with a down-up pattern.

Proposition 16. Let G, G 1 = (V 1 , A 1 ), G 2 = (V 2 , A 2 ) ∈ G. If there is a walk w = G 1 ← * d G → * d G 2
, then there exists a graph G and a walk w

= G 1 → * d G ← * d G 2 , with |w | ≤ |w|. Proof. Let V = V 1 ∩ V 2 , and G = G ↓V . There is a deletion string from G 1 (respectively G 2 ) to G , by deleting vertices V 1 \ V 2 (respectively V 2 \ V 1 ). G contains vertices V 1 ∪ V 2 ,
but it also has the vertices that have been deleted on both paths to G 1 and to G 2 , so that

|G| ≥ |V 1 ∪ V 2 |.
Using Property 15, w has length

|G| -|G 1 | + |G| -|G 2 | ≥ |V 1 ∪ V 2 | -|V 1 | + |V 1 ∪ V 2 | -|V 2 | = |V 1 ∪ V 2 | -|V 1 ∩ V 2 |, and w has length |V 1 | -|V 1 ∩ V 2 | + |V 2 | -|V 1 ∩ V 2 | = |V 1 ∪ V 2 | -|V 1 ∩ V 2 |. Thus |w | ≤ |w|. Theorem 17. If there is a walk w of E d from G 1 to G 2 , then there is a graph G c and a walk w = G 1 → * d G c ← * d G 2 not longer than w.
Proof. By recursion on the number of maximal 'peaks' of w, i.e. the number of maximal subwords of w ∈→ d • ← d : using Property 16 decreases the number of maximal peaks, and at each step the resulting walk from G 1 to G 2 is shorter or has the same length.

To show the same kind of properties for merge operations, graph quotients come into play.

Proposition 18. Let G, G 1 , G 2 ∈ G. If there is a walk w = G 1 ← * m G → * m G 2 , then there exists a graph G and a walk w = G 1 → * m G ← * m G 2 , with |w | ≤ |w|.
Proof. This illustrates the construction:

G G 1 G 2 G α 1 α 2 β = (α 1 * α 2 ) α 1 γ = (α 1 * α 2 ) α 2 π = α 1 * α 2
Using Theorem 12, we see a string of merge operations as one graph quotient. Let α 1 and

α 2 such that G 1 = G/α 1 and G 2 = G/α 2 . Let π = α 1 * α 2 .
With β = π/α 1 and γ = π/α 2 , we have, using Property 14,

G/π = G 1 /β = G 2 /γ in other words, G α 1 * α 2 = G α 1 / (α 1 * α 2 ) α 1 = G α 2 / (α 1 * α 2 ) α 2 .
So, by transitivity, G has epimorphisms from G 1 and G 3 . And since β and γ have respectively smaller dimensions than α 1 and α 2 (by Properties 11 and 13), the dotted lines in the figure above are shorter than the dashed lines, hence the property. This result works for the merge operation. However, it can be extended to the merge and delete operations at the same time. In short, vertex deletion can be simulated by merging with a dummy vertex. Definition 4.7 (Dummy vertices, pointed graphs). Let ⊥ be a fresh symbol that is not a vertex of any graph in G.

Let

• ⊥ : G ∈ G -→ G ⊥ = (V ⊥ , A ⊥ ), where V ⊥ = V ⊥ and A ⊥ = A (V × {⊥}) ({⊥} × V ) {(⊥, ⊥)}.
We call dummy vertex of a graph G one that has all possible arcs to/from the other vertices of G and to itself. In G ⊥ , ⊥ is always a dummy vertex.

We write the set of pointed graphs G ⊥ = {G ⊥ | G ∈ G}. We extend the merge operation on G ⊥ with no special treatment for ⊥ : a priori, the image of ⊥ can be any vertex, and the antecedents of ⊥ can be any vertex.

Proposition 20. • ⊥ is an isomorphism from E m to (E ⊥ ) m : G → md G if and only if G ⊥ → m G ⊥ .
Proof. The left to right implication is straightforward. Let µ : G -→ G the function corresponding to the operation, merging or deletion. If the operation is a merging, then sending ⊥ to ⊥ is valid. If it is a deletion, sending ⊥ to ⊥ and sending the deleted vertex to ⊥ makes the operation a merging. So µ ⊥ :

  v ∈ dom(µ) -→ µ(v) v ∈ V -dom(µ) -→ ⊥ ⊥ -→ ⊥   is a merging from G ⊥ to G ⊥ .
The converse implication should be done carefully. Let us call µ ⊥ : G ⊥ -→ G ⊥ the function corresponding to the merging. Notice that µ ⊥ (⊥) is not necessarily ⊥. However µ ⊥ (⊥) is necessarily a dummy vertex, so that ω :

  v / ∈ {µ ⊥ (⊥), ⊥} -→ v µ ⊥ (⊥) -→ ⊥ ⊥ -→ µ ⊥ (⊥)   is a graph isomorphism of G ⊥ . Let ρ = ω • µ ⊥ : it is a merging from G ⊥ to G ⊥ with ρ(⊥) = ⊥. One can check that µ : v -→ ρ(v) if ρ(v) = ⊥
is either a merging (when ρ -1 (⊥) = {⊥}), or a deletion of u (when ρ -1 (⊥) = {⊥, u}).

Theorem 21. If there is a walk w of E md from G 1 to G 2 , then there is a graph G c and a walk w = G 1 → * md G c ← * md G 2 not longer than w.

Proof. Combining Theorem 19 and Property 20 yields the result.

These results on down-up walks lead to an interesting corollary when considering morphisms:

Corollary 22. Let G, G ∈ G. • d d (G, G ) = |G| + |G | -2 max{|G c | s.t. G SISO G c ∧ G SISO G c } • d m (G, G ) = |G| + |G | -2 max{|G c | s.t. G EPI G c ∧ G EPI G c } • d md (G, G ) = |G| + |G | -2 max{|G c | s.t. G SEPI G c ∧ G SEPI G c } Proof.
Use Theorem 1 to transpose Theorems 17, 19 and 21 to morphisms, then use Property 15 for cardinalities.

The first equality is already known: the deletion distance between G and G is the number of deletions to the maximum common induced subgraph G c [START_REF] Bunke | On a relation between graph edit distance and maximum common subgraph[END_REF], which is the greatest lower bound of G and G for the SISO partial order.

The other two equalities are new: G c is a greatest lower bound of maximal cardinality for the EPI (respectively SEPI) partial orders. Note that there may be several common graphs of maximum cardinality.

Computational Complexity

The SISO and EPI decision problems are NP-complete [START_REF] Vikas | Computational Complexity of Graph Compaction[END_REF] We prove the NP-completeness of the SEPI decision problem by direct reduction of SAT [START_REF] Cook | The complexity of theorem-proving procedures[END_REF]. For a finite set of variables X, let ¬X = {¬x 1 , . . . , ¬x m } denotes the set of negative literals constructed upon X. For a Boolean formula in conjunctive normal form

φ = c 1 ∧ • • • ∧ c n over X, we have for all 1 ≤ i ≤ n, c i = i,1 ∨ • • • ∨ i,n i , and for all 1 ≤ j ≤ n i , i,j ∈ X ∪ ¬X. Let us write C φ = {i ∈ N | 1 ≤ i ≤ n} and L φ = {(i, j) ∈ N 2 | 1 ≤ i ≤ n, 1 ≤ j ≤ n i }.
Lemma 24. A Boolean formula φ in conjunctive normal form is satisfiable, if and only if there exists a subset X ⊆ L φ such that

• for all 1 ≤ i ≤ n, there exists 1 ≤ j ≤ n i such that (i, j) ∈ X,
• for all (i, j), (i , j ) ∈ X, i ,j = ¬ i,j . Proof. If µ : V → {0, 1} satisfies φ, we pose for all x ∈ V , µ(¬x) = 1 -µ(x) and then it suffices to observe that X = {(i, j) ∈ L | µ( i,j ) = 1} satisfies the conditions of the lemma. Conversely, given a subset X ⊆ L φ satisfying these conditions, we pose µ : V → {0, 1} such that for all x ∈ V , µ(x) = 1 if there exists (i, j) ∈ X such that i,j = x and 0 otherwise. Then, we observe that µ satisfies φ.

We say that φ is satisfied by X if X is a subset of L φ satisfying these conditions.

Theorem 25. The subgraph epimorphism problem is NP-complete.

Proof. The subgraph epimorphism problem is NP since, given two graphs G = (V, A) and G = (V , A ) and function f : V → V , checking whether f is a subgraph epimorphism or not can be done in polynomial time. Therefore, it suffices to show that the subgraph epimorphism problem is NP-hard.

Let us assume a SAT instance given by a Boolean formula in conjunctive normal form φ over a finite set of variables X. Let G and G be the following two graphs.

G = (L φ , {{(i, j), (i , j )} ⊆ L φ | i = i ∧ j = j ∨ i ,j = ¬ i,j }) G = (C φ , ∅)
This construction is depicted in figure 2. The theorem is then an immediate consequence of the following lemma.

Lemma 26. φ is satisfiable if and only if there exists a SEPI from G to G .

Suppose that φ is satisfied by a set K ⊆ L φ . Let K = {(i, min{j | (i, j) ∈ K}) | 1 ≤ i ≤ n}.
K is a matching, i.e. for all i ∈ C φ , there exists a unique j i , with (i,

j i ) ∈ L φ such that (i, j i ) ∈ K . Notice that K still satisfies φ. Let µ : (i, j) ∈ K → i ∈ C φ .
We show that µ is a SEPI from G to G . Indeed, µ is surjective, since K satisfies φ. Furthermore, the subgraph of G induced by K has no edges: if (i, j) and (i , j ) are in K, then either i = i , and then j = j because K is a matching, or i = i , and then i ,j = ¬ i,j because K ⊆ K. Since there are no edges to preserve, µ is trivially a morphism. So µ is a SEPI from G to G .

Conversely, suppose that µ is a SEPI from G to G . Let K = µ -1 (C φ ). We show that K satisfies φ. First, µ is onto, so |K| ≥ n. Then, if for some i there are distinct (i, j), (i, j ) ∈ K, the edge between (i, j) and (i, j ) could not be preserved by µ, so there is at most one (i, j) ∈ K for each i ∈ {1, . . . n}. We deduce |K| = n, so there is exactly one (i, j) ∈ K for each i.

Furthermore, if i ,j = ¬ i,j for some (i, j) and (i , j ) ∈ K, then the arc between the two vertices could not be preserved by µ. So K satisfies φ.

It is worth noticing that in this proof, the existence of a SEPI from G to G is equivalent to the existence of a SISO from G to G . Therefore, this reduction shows the NP-hardness of both SEPI and SISO.

Constraint Logic Program

Despite its theoretical computational complexity, SEPI problems can be efficiently solved for some applications. In this section, we present a constraint logic program that has been successfully used to solve practical SEPI problems on a large benchmark of reaction graphs from systems biology [START_REF] Gay | A graphical method for reducing and relating models in systems biology[END_REF]. This program implemented in GNU-Prolog [START_REF] Diaz | GNU Prolog user's manual[END_REF] uses the built-in constraints relation and element var described in the next section.

Preliminaries on Constraint Satisfaction Problems

Definition 6.1 (CSP). A constraint satisfaction problem (CSP for short) is a triple P = (V, D, C), where:

• V is a set of variables • D is a family of domains indexed by variables from V : ∀X ∈ V , D X is a finite set. • C is a set of constraints, each c ∈ C is defined by its arity ar(c) ∈ N, a tuple of variables X(c) ∈ V ar(c) and a relation R(c) ⊆ ar(c) i=1 D X i (c) . Definition 6.2 (Solution of a CSP). An assignment η : X ∈ V -→ η(X) ∈ D X is a solution of P when ∀c ∈ C, (η(X 1 ), . . . , η(X n )) ∈ R(c), with X(c) = (X 1 , . . . , X n ).
Graph matching problems can be easily modeled as constraint satisfaction problems [START_REF] Vianney Le Clément | Constraint-based graph matching[END_REF]. One variable per vertex in the source graph is introduced, its domain is the set of vertices of the target graph. Symbolic constraints on these variables are then used to express the matching problem and to actively prune the search space by filtering the domain of these variables during search.

We shall use the following symbolic constraints and their associated domain filtering algorithms (available in GNU-Prolog [START_REF] Diaz | GNU Prolog user's manual[END_REF]):

• relation constrains variables using a relation given in extension. The constraint c = relation( Y , R), where Y is a tuple of variables and R is a relation, is defined by:

-ar(c) = arity of Y = arity of R = n -X(c) = Y -R(c) = R ∩ n i=1 D Y i ,
• element var constrains a list of variables f describing a function to have Y as the image of its X-th element. The constraint c = element var(X, f, Y ), where X, Y ∈ V and

f = (f 1 , . . . , f n ) ∈ V n , is defined by -ar(c) = n + 2 -X(c) = (X, f 1 , . . . , f n , Y ) -R(c) = {(index, η 1 , . . . , η n , image) ∈ D X × ( n i=1 D f i ) × D Y | η index = image} 6.2

. SEPI as a Constraint Satisfaction Problem

The graph epimorphism problem between two graphs G and G can be modeled as a constraint satisfaction problem P = (V, D, C) as follows. Variables are associated to the vertices of G and G and to the edges of G

V = {X v | v ∈ V (G)} {Y v | v ∈ V (G )} {Y e | e ∈ E(G )}, with domains respectively D(X v ) = V (G ⊥ ), D(Y v ) = {1, . . . , |V (G)|}, D(Y e ) = {1, . . . , |E(G)|}.
The constraints are

C = {relation((X u , X v ), E(G ⊥ )) | (u, v) ∈ E(G)} ∪ {element var(Y v , X(V (G)), v ) | v ∈ V (G )} ∪ {element var(Y (u ,v ) , π 1 (X(E(G))), u ) | (u , v ) ∈ E(G )} ∪ {element var(Y (u ,v ) , π 2 (X(E(G))), v ) | (u , v ) ∈ E(G )}
where X(V (G)) is an arbitrarily ordered list containing the elements of Proof. We prove that a variable assignment η is a solution to P if and only if the restriction of

{X v | v ∈ V (G)}, X(E(G)) is a list representation of the set {(X u , X v ) | (u, v) ∈ E(G)},
η to {u ∈ V (G) | η(u) ∈ V (G )} = η V (G ) V (G) is a subgraph epimorphism from G to G . If η is a solution to P, then η V (G ) V (G) preserves the arcs of G since for each (u, v) ∈ E(G), relation((X u , X v ), E(G )) enforces (η(X u ), η(X v )) ∈ E(G ). Moreover, η V (G ) V (G) is surjective on vertices of G , since for each v ∈ V (G ), element var(Y v , X(V (G)), v ) forces the Y v -th element of V (G)
to have v as its image, and similarly surjectivity on arcs of G is enforced by the remaining constraints.

Conversely, suppose there is a subgraph epimorphism f from G to G . Let g : V (G ) → V (G) be any inverse of f on the vertices (i.e. ∀v ∈ V (G )f (g(v )) = v ), and h : E(G ) → E(G) any inverse of f on the arcs. Let η such that:

• ∀v ∈ V (G), η(X v ) = f (v), • ∀v ∈ V (G ), η(Y v ) = i s.t. V (G) i = g(v ), • ∀(u , v ) ∈ E(G ), η(Y (u ,v ) ) = j s.t. E(G) j = h((u , v )).
Then η is a solution to the CSP P.

Interestingly, the ⊥ vertices used to reduce SEPI to EPI in the proof of Proposition 20 are also used in this coding of subgraph epimorphism as a CSP: without the dummy vertices, we obtain a CSP encoding of the EPI problem.

The CSP Framework: Propagation and Enumeration

In order to solve a real-world CSP problem, the enumeration of tuples η is not a viable possibility. Constraint solvers use the fact that from the reduction of the domain of some variables, one can deduce information about the other variables: in particular, one can deduce forbidden values for other variables.

As an example, consider the CSP with variables {X, Y, Z} and constraints (X, Y ) ∈ {(1, 1), (2, 3)}, (Y, Z) ∈ {(1, 2), (1, 3)}. Instantiating X to 1 allows the deduction of Y = 1, so we never need to test Y = 2: this deduction has been propagated from X = 1. To continue the solving process, we have no choice but to let Y = 2, and we can choose the next value to try for Z: Z = 2 is a valid choice.

If at first we had tried X = 2, the first constraint would have forbidden Y = 1, and the second constraint would have forbidden every value of Z. This is a failure: on failure, constraint solvers backtrack to the last instantiation V ar = val where there was a choice, removes val from the domain of V ar, and tries another value for V ar. If no value remains, the backtracking process has to return to an even earlier choice point, and if there is no such choice point, then there is no solution to the CSP.

Searching for a solution by constraint solving alternates between propagation and enumeration steps. The general searching scheme is described in the following function Search C (D): this function returns a solution η in the domain family D if such a solution exists, and fails otherwise.

function

Search C (D) D ← Propagate C (D) if ∃X | D X = ∅ then fail else if ∀X, |D X | = 1 then return η such that ∀X, D X = {η(X)} else (X, d) ← VariableValueSelection(D ) try D ← (X → d; Y = X → D Y ) Search C (D ) on failure D ← (X → D X \ d; Y = X → D Y ) Search C (D ) end try end if end function
Propagation is assumed to be monotonic (Propagate C (D X ) = D X ⊆ D X for all X ∈ V ) and correct (if the condition ∀X, |D X | = 1 holds, then the resulting η is a solution). Enumeration is assumed to be strictly monotonic (d D X ) and inhabited (d = ∅). The function VariableValueSelection should never select a singleton variable: VariableValueSelection(D) = (X, d) ⇒ |D X | > 1. Therefore, Search C (D) terminates.

In the worst case, with no propagation (D = D), the search procedure is equivalent to a non-deterministic labeling in O(d n ) where d is the size of the largest domain (the maximum between the number of vertices in G and the number of arcs in G) and n the number of variables (the sum of the number of vertices in G and arcs in G ).

We consider propagation algorithms that ensures the domain-arc-consistency of the domain family D = Propagate C (D) with respect to the set of constraints C. A domain family D is domain-consistent with respect to a set of constraints C when for every variable X ∈ V and

else if ∃v ∈ V (G) | |D Xv | > 1 ∧ D Xv = {⊥} then return (X v , ⊥) end if end function
Proposition 29. For a SEPI CSP, the search strategy with VariableValueSelection antecedents yields a solution once every antecedent variable has been instantiated, by instantiating the remaining non-singleton source vertex variables to ⊥.

Proof. First, suppose we have enumerated only the antecedent variables, and failed. Once again, it is obvious that there is no SEPI from the source graph to the target graph.

Conversely, if the enumeration on antecedent variables succeeded, then some source vertex variables already have singleton domains. The induced subgraph formed by the source vertices that correspond to these variables are sufficient to cover G , and the correctness of the relation propagator ensures that the variables code a morphism. If we put the ⊥ value for every remaining source vertex variable, we get a SEPI from the source graph to the target graph.

An enumeration of the source vertex variables is enough to enforce arc surjectivity. However, compared to enumerating the antecedents variables beforehand, the former strategy checks the surjectivity quite late. Enumerating antecedent variables is sufficient provided we fill the remaining source vertex variables with ⊥. This "antecedents first" strategy works best in practice.

Implementation and Evaluation

The preceding constraint satisfaction algorithm can be directly coded in GNU-Prolog [7] using the built-in constraint propagators for the relation and element var constraints. Some redundant constraints, such as the all different constraint of [START_REF] Régin | A filtering algorithm for constraints of difference in CSPs[END_REF], the neighborhood constraint of [START_REF] Larrosa | Constraint satisfaction algorithms for graph pattern matching[END_REF] or other global constraints [START_REF] Sorlin | A parametric filtering algorithm for the graph isomorphism problem[END_REF][START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF][START_REF] Solnon | AllDifferent-based filtering for subgraph isomorphism[END_REF] have been proposed to improve the domain filtering process on graph matching problems, and in some cases to outperform dedicated algorithms such as Vflib [START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF][START_REF] Solnon | AllDifferent-based filtering for subgraph isomorphism[END_REF]. However, the results reported here concern the constraint logic program described in the previous section without global constraints.

Our benchmark for evaluation comes from the repository of models biomodels.net that is widely used in systems biology. Most of these models are biochemical reaction networks from which one can extract a bipartite reaction graph with 'species' and 'reaction' vertices. The domain constraints ensure that the morphism map species vertices to species vertices, and reaction vertices to reaction vertices.

We have shown in [START_REF] Gay | A graphical method for reducing and relating models in systems biology[END_REF] that SEPIs faithfully represent reduction relationships between models of biochemical reaction systems, and that they can be used to relate the models in this repository and organize them in a hierarchy of more or less detailed models.

On the 241 curated models of this repository, 131 are reaction models from which non trivial reaction graphs can be extracted. The average size of the graphs is 56 vertices, with a minimum of 9, a median of 37, and a maximum of 315 vertices.

Our GNU-Prolog program was used to decide the existence of SEPIs in all 131*130 pairs of reaction graphs. Of these 17030 comparisons, 329 were not computed within a time out of 20mn, and 16659 were computed in less than 5 seconds [START_REF] Gay | A graphical method for reducing and relating models in systems biology[END_REF].

Generalization to Undirected Graphs and Bipartite Graphs

Undirected Graphs

In undirected graphs, with loops allowed, the definition of SEPI is almost the same, with epimorphisms now preserving adjacency instead of successors.

Property 3 shows that the classical encoding of undirected graphs as symmetric directed graphs helps the conversion to undirected graphs.

The notion of outgoing and incoming non-neighbors can be traded for a notion of nonneighbors. Property 4 can be translated for non-neighbors. The infinite antichain given as proof of Property 5 is symmetric, so it also translates as an infinite antichain of undirected graphs.

The operations we consider in the proofs for distances d r preserve arc symmetry, which makes the lub characterization of distance work for undirected graphs.

The SEPI existence problem between two undirected graphs is also NP-complete since the proof of Theorem 25 uses symmetric graphs.

Bipartite Graphs

Our interest in subgraph epimorphisms came from an application in bioinformatics that uses bipartite directed graphs. In this setting, epimorphisms have to preserve bipartition of the vertices. Here, every vertex has one of two labels (say 'circle' and 'square'), vertices with the same label can not be adjacent, and epimorphisms have to preserve these labels.

The infinite antichain in Property 5 can be adapted: instead of taking complete graphs minus maximal cycles, we can consider complete (n, n)-bipartite graphs minus maximal cycles, that is: G n = (V n , A n ), with V n = {1 . . . n} {1 . . . n } and A n = {(i, j ), (j , i) | i = j }.

The distances are defined the same way. The lub characterizations are the same for d d and d m . However, the construction to go from EPI to SEPI needs a slight modification: we add two ⊥ vertices instead of one, a circle-labeled one and a square-labeled one. The ⊥ vertex of each type is to be linked with every vertex of the other type. This makes the encoding of SEPI in EPI valid.

Finally, the SEPI decision problem can be proved NP-complete by modifying the proof a little. First, we can suppose there are no clauses that contains both x and ¬x in the SAT instance. We take the same C and L as in the main proof, there are n clauses in the instance.

Then, we modify the source graph G 1 = (V 1 , A 1 ) by changing cliques to bicliques:

circle(V 1 ) = L square(V
A 2 = {(c i , x i ) | 1 ≤ i ≤ n} ∪ {(x i , d i ) | 1 ≤ i ≤ n}
If the SAT instance is satisfiable, deducing a SEPI from G 1 to G 2 is trivial. If there is a SEPI µ from G 1 to G 2 , then µ -1 (X ) satisfies Lemma 24, concluding the proof.

Conclusion

The operations of deleting and merging vertices are natural operations for reducing a graph. While graph reductions through a sequence of vertex deletions (respectively mergings) characterize subgraph isomorphisms (respectively graph epimorphisms), sequences of both vertex deletion and merging operations characterize subgraph epimorphisms. Our proposal is thus to use subgraph epimorphism for comparing graphs in applications where a more flexible notion than the classical notion of subgraph isomorphism is required.

We have shown that SEPIs preserve graph completeness and arc symmetry and that, just like SISO and EPI, SEPI is not a well quasi order. We have defined the SEPI, EPI and SISO distances between two graphs as the size of the largest SEPI (respectively EPI, SISO) lower bound graphs. These distances are equal to the minimum number of respectively vertex deletion and/or merging operations that are necessary to obtain isomorphic graphs. They are also metrics on graphs, and we have d d ≥ d md and d m ≥ d md .

From a computational point of view, we have shown that the existence of a SEPI between two graphs is an NP-complete problem, and have presented a constraint logic program for solving it with good performance in practice on a large benchmark of SEPI model reduction problems from systems biology.

It is worth noticing that, given two graphs G and G , the greatest lower SEPI bounds and the least upper SEPI bounds are also interesting to compute since they represent "intersection" and "union" graphs for the SEPI relation. For instance, in our motivating application in systems biology, these objects correspond to the intersection (respectively union) of models at different levels of details for a given biochemical process. These graphs are not unique but we are confident that the constraint satisfaction algorithm we have presented can be interestingly generalized to compute them.

Figure 1 :

 1 Figure 1: A catalytic mechanism, and the Michaelis-Menten reduced mechanism

Example 1 .

 1 The two graphs given in the introduction for the reduction of Michaelis-Menten are related by a SEPI where the induced subgraph of the first graph is obtained by deleting the vertices ES and d, and where both vertices c and p are mapped to the vertex c of the second graph.

Definition 3 . 1 (

 31 Edition graph). Let o ∈ {m, d, md}. We define the edition graph

  E o from G to G , there always exists a walk w from G to G such that |w| ≥ |w | and w changes directions at most once, i.e., it first only crosses arcs forward and then only crosses arcs backward. The vertex of E o that separates forwards and backwards arc crossings corresponds to an upper bound of G and G with respect to the partial ordering relations EPI, SEPI, or SISO. Now, how can one compute the distance d o between two graphs G, G ? If o ∈ {d, md}, the simplest walk through the empty graph is of size |G| + |G |, d o (G, G ) ≤ |G| + |G |, so it is sufficient to explore the graphs from size 0 to |G| + |G |. When o = d, one can actually bound the search to graphs of the same size as |G| + |G |.

Definition 4 . 1 .

 41 Let α be an equivalence relation over a set S and x ∈ S. The class of x modulo α

Definition 4 . 3 .

 43 Let α, β be equivalence relations over S. The product of equivalence relations is α * β = (α ∪ β) + . It is an equivalence relation, the smallest (inclusion-wise) containing both α and β.

Definition 4 . 4 .

 44 Let s be a binary relation over S.

Definition 4 . 6 (

 46 Quotient Graph). The quotient of G by α is:

Proposition 15 .

 15 If there is a sequence of merge and delete operations that transforms G into G , then this sequence has |G| -|G | operations. Proof. Each merge or delete operation decrements the number of vertices of G by 1.

Theorem 19 .

 19 If there is a walk w of E m from G 1 to G 2 , then there is a graph G c and a walkw = G 1 → * m G c ← * m G 2 notlonger than w. Proof. Same proof as Theorem 17, using Property 18.

  Corollary 23. d o (G, G ) has the same parity as |G| + |G |.

Definition 5 . 1 .

 51 , and computing d SISO or d EPI is NP-hard since d o (G, G ) = |G|-|G | if and only if G r G , by Proposition 15 and Corollary 22. The subgraph epimorphism problem is the following decision problem: " given two graphs G and G , is G SEPI G or not ?".

4 GFigure 2 :

 42 Figure 2: Reduction from the SAT instance φ = (a ∨ b ∨ ¬c) ∧ (a ∨ ¬b ∨ d) ∧ (¬a ∨ ¬c ∨ ¬d) ∧ (¬a ∨ c ∨ ¬d) to SEPI

  1 ) = C ∪ B with B = {((i 1 , j 1 ), (i 2 , j 2 ) ∈ L 2 | i 1 ,j 1 = ¬ i 2 ,j 2 } A 1 = {(c, l) ∈ C × L | l = (c, •)} ∪{(l, p) ∈ L × B | p = (l, •) ∨ p = (•, l)}. the target graph pattern is then G 2 = (V 2 , A 2 ) circle(V 2 ) = X = {x 1 , . . . x n } square(V 2 ) = C ∪ D , with C = {c 1 , . . . c n } and D = {d 1 , . . . d n }

Acknowledgements

We acknowledge support from the national OSEO BioIntelligence and ANR Calamar (ANR-08-SYSC-003) projects and fruitful discussions with the many participants of these projects.

every value v ∈ D X , there exists an assignment η such that η(X) = v and η respects every constraint in C.

The built-in constraint propagators of GNU Prolog indeed maintain arc-consistency for the constraints relation and element var.

Search Strategy for SEPI

Here we discuss the choice of VariableValueSelection for SEPI CSPs.

The default choice could be to use a generic strategy for enumerating both source vertices and antecedent vertices and arcs as follows:

function

Actually, the enumeration of only one of the sets is sufficient. Let us consider the following enumeration function:

Proposition 28. For a SEPI CSP, the search strategy with VariableValueSelection X(V (G)) yields a solution once the source vertex variables are instantiated, for any instantiation of the antecedent variables in their domains.

Proof. First, suppose we have tried to enumerate the source vertex variables, and failed. Then, the correctness of constraint propagation ensures that there is no SEPI from the source graph to the target graph.

Conversely, if on the contrary the enumeration on source vertex variables succeeded, then there is obviously a morphism. Is it surjective? The domain-arc-consistency of element var removes values v ∈ V (G) (respectively (u, v) ∈ E(G)) from antecedent variables of v (respectively (u , v )) as soon as it is known that the image of v (respectively (u, v)) is not v (respectively (u , v )).

Since every source vertex variable is completely instantiated, the domains of antecedent variables are more than a set of possible antecedents: they are the exact sets of antecedents.

From the Search C algorithm, every antecedent variable has a non-empty domain, which means the morphism is surjective, and any value for the antecedent variables will satisfy the constraints.

Let us now consider the enumeration of antecedent variables as follows: function VariableValueSelection antecedents (D)