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

AllDifferent-based Filtering for Subgraph Isomorphism

Keywords: Subgraph Isomorphism, Constraint Programming, All Different constraint

AllDifferent-based Filtering for Subgraph Isomorphism

Introduction

Graphs are widely used in real-life applications to represent structured objects such as, for example, molecules, images, or biological networks. In many of these applications, one looks for a copy of a pattern graph into a target graph [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. This problem, known as subgraph isomorphism, is NP-complete in the general case [START_REF] Garey | Computers and Intractability[END_REF].

Subgraph isomorphism problems may be solved by a systematic exploration of the search space composed of all possible injective matchings from the set of pattern nodes to the set of target nodes: starting from an empty matching, one incrementally extends a partial matching by matching a non matched pattern node to a non matched target node until either some edges are not matched by the current matching (the search must backtrack to a previous choice point and go on with another extension) or all pattern nodes have been matched (a solution has been found). To reduce the search space, this exhaustive exploration is combined with filtering techniques that aim at removing candidate couples of non matched pattern-target nodes. Different levels of filtering may be considered; some are stronger than others (they remove more nodes), but also have higher time complexities.

In this paper, we describe and compare existing filtering algorithms for the subgraph isomorphism problem, and we introduce a new filtering algorithm which is stronger. We experimentally evaluate this new filtering algorithm on a wide benchmark of instances, and we show that it is much more efficient on many instances.

Definitions and notations

A graph G = (N, E) consists of a node set N and an edge set E ⊆ N × N , where an edge (u, u ) is a couple of nodes. The set of neighbors of a node u is denoted adj(u) and is defined by adj(u) = {u | (u, u ) ∈ E}. In this paper, we implicitely consider non directed graphs, such that (u, u ) ∈ E ⇔ (u , u) ∈ E. The extension of our work to directed graphs is discussed in Section 5.

A subgraph isomorphism problem between a pattern graph G p = (N p , E p ) and a target graph G t = (N t , E t ) consists in deciding whether G p is isomorphic to some subgraph of G t . More precisely, one should find an injective matching f : N p → N t , that associates a different target node to each pattern node, and that preserves pattern edges, i.e., ∀(u, u ) ∈ E p , (f (u), f (u )) ∈ E t

The function f is called a subisomorphism function.

Note that the subgraph is not necessarily induced so that two pattern nodes that are not linked by an edge may be matched to two target nodes which are linked by an edge. This problem is also called subgraph monomorphism or subgraph matching in the literature.

In the following, we assume G p = (N p , E p ) and G t = (N t , E t ) to be the underlying instance of subgraph isomorphism problem, and we assume without loss of generality that N p ∩ N t = ∅. We usually denote u or u (resp. v or v ) nodes of G p (resp. G t ).

We denote #S the cardinality of a set S. We also define N = N p ∪ N t , E = E p ∪ E t , n p = #N p , n t = #N t , e p = #E p , e t = #E t , and d p and d t the maximal degrees of the graphs G p and G t .

Filtering for subgraph isomorphism

Subgraph isomorphism problems may be modelled as constraint satisfaction problems in a very straightforward way. In this section, we first show how to model and solve subgraph isomorphism problems within a constraint satisfaction framework. Then, we describe different filtering algorithms for subgraph isomorphism in Sections 3.3 to 3.6, and we compare them in Section 3.7.

Modeling and solving subgraph isomorphism by means of constraints

A constraint satisfaction problem (CSP) is defined by a set of variables, such that each variable is associated with a domain (i.e., the set of values that it may be assigned to), and a set of constraints (i.e., relations that restrict the set of values that may be assigned to some variables simultaneously). Solving a CSP involves finding an assignment of values to all variables such that all constraints are satisfied.

A subgraph isomorphism problem may be modelled as a CSP by associating a variable (denoted x u ) with every pattern node u. The domain of a variable x u (denoted D u ) contains the set of target nodes that may be matched to u. Intuitively, assigning a variable x u to a value v corresponds to matching the pattern node u to the target node v. The domain D u is usually reduced to the set of target nodes the degree of which is higher or equal to the degree of u as node u may be matched to node v only if #adj(u) ≤ #adj(v).

Constraints ensure that the assignment of variables to values corresponds to a subisomorphism function. There are two kinds of constraints:

• edge constraints ensure that pattern edges are preserved, i.e., ∀(u, u ) ∈ E p , (x u , x u ) ∈ E t

• difference constraints ensure that the assignment corresponds to an injective function, i.e., ∀(u, u ) ∈ N 2 p , u = u ⇒ x u = x u Within this framework, solving a subgraph isomorphism problem involves finding an assignment of the variables that satisfies all constraints. We shall consider that a variable is assigned whenever its domain is reduced to a singleton, i.e., D u = {v} ⇔ x u = v.

Subgraph isomorphism problems modeled as CSPs may be solved by building a search tree that explores all possible variable assignments until finding a so-lution. The size of this search tree may be reduced by using filtering techniques which propagate constraints to remove values from domains.

We briefly recall some basic principles of contraint propagation in Section 3.2. Then, we describe different filtering techniques that may be used to solve subgraph isomorphism problems in Sections 3.3 to 3.6. Note that some of these filterings (i.e., FC(Diff ), GAC(AllDiff ), FC(Edges), and AC(Edges)) are generic constraint propagation techniques that may be used to solve any CSP whereas some others (i.e., LV2002 and ILF(k)) are dedicated to the subgraph isomorphism problem.

Recalls on constraint propagation

Constraint propagation aims at filtering variable domains by removing inconsistent values, that is, values that do not belong to any solution. This constraint propagation step may be done at each choice point of the search. If it removes all values in the domain of a variable, then the search can backtrack to a previous choice.

A pioneering work for constraint propagation has been done in 1972 by Waltz for a scene drawing application [START_REF] Waltz | Generating semantic descriptions from drawings of scenes with shadows[END_REF]. Since then, many different constraint propagation algorithms have been proposed. These algorithms achieve different partial consistencies and also have different time and space complexities. In this section, we do not aim at describing all existing propagation algorithms. We only briefly describe two basic and well known generic techniques, that is, forward-checking and maintaining arc-consistency. The reader may refer to [START_REF] Rossi | Handbook of Constraint Programming (Foundations of Artificial Intelligence)[END_REF][START_REF] Lecoutre | Constraint Networks: Techniques and Algorithms[END_REF] for more information.

Forward-checking

The basic idea of forward-checking is to propagate all constraints involving a variable just after its assignment in order to remove from the domains of the non assigned variables any value which is not consistent with this assignment. More precisely, after the assignment of x i to v i , one propagates binary constraints between x i and any non assigned variable x j by removing from the domain of x j any value v j such that the assignment {(x i , v i ), (x j , v j )} violates the constraint holding between x i and x j . When constraints have arities greater than two, one may propagate constraints such that all variables but one are assigned.

Maintaining arc-consistency A stronger filtering, but also a more expensive one, is obtained by maintaining arc-consistency, also called 2-consistency.

Roughly speaking, a binary CSP is arc-consistent if each value v i in the domain of a variable x i has at least one support in the domain of every other variable, thus ensuring that if x i is assigned to v i then each other variable still has at least one consistent value in its domain. More precisely, given a variable x i ∈ X and a value v i ∈ D(x i ), a support of (x i , v i ) for a variable x j is a value v j ∈ D(x j ) such that the partial assignment {(x i , v i ), (x j , v j )} is consistent. A binary CSP (X, D, C) is arc-consistent if every value in every domain has at least one support in the domain of each other variable.

To maintain arc-consistency while constructing a partial assignment A, we filter variable domains after each variable assignment by removing non supported values. Such a filtering must be repeated until no more domain is reduced: as soon as a value is removed, we must check that this value is not the only support of some other values. There exist many different algorithms for ensuring arc-consistency, which exhibit different time and space complexities. For instance, a widely used algorithm for achieving arc consistency of a set of binary constraints is AC4 [START_REF] Mohr | Arc and path consistency revisited[END_REF] whose time and space complexities are O(ck 2 ), where c is the number of constraints and k the maximum domain size. Although AC4 is worst-case optimal in time, it always reaches this worst case because of its expensive initialisation phase; many improvements have been proposed since AC4, leading for example to AC6, AC7 and AC2001 (see [START_REF] Rossi | Handbook of Constraint Programming (Foundations of Artificial Intelligence)[END_REF] for more details). Arc consistency may also be generalized to non binary CSPs. In this case, it is called generalized arc consistency.

Propagation of difference constraints (FC(Diff) and GAC(AllDiff))

Difference constraints may be propagated by forward-checking (denoted FC (Diff )): each time a pattern node u is matched to a target node v, FC(Diff ) removes v from the domains of all non matched nodes. This may be done in O(n p ).

FC(Diff )

propagates each binary difference constraint separately. A stronger filtering may be obtained by propagating the whole set of difference constraints in order to ensure that all pattern nodes can be assigned to different target nodes. More precisely, achieving the generalized arc consistency of a global AllDifferent constraint (denoted GAC(AllDiff )) removes from the domain of every pattern node u every target node v such that, when u is matched to v, the other pattern nodes cannot be matched to all different target nodes.

In [START_REF] Regin | A filtering algorithm for constraints of difference in CSPs[END_REF], Régin has shown how to use the matching algorithm of Hopcroft and Karp for achieving GAC(allDiff ). The time complexity of this algorithm is O(n 2 p • n 2 t ).

Example 1 Let us consider four variables x 1 , x 2 , x 3 , and x 4 such that D 1 = {a}, D 2 = D 3 = {a, b, c}, and D 4 = {a, b, c, d}.

FC(Diff) removes a from the domains of x 2 , x 3 , and x 4 .

GAC(AllDiff) also removes a from the domains of x 2 , x 3 , and x 4 . It further removes b and c from the domain of x 4 as if x 4 is assigned to b or c, then x 2 cannot be assigned to a value different from both x 3 and x 4 .

3.4 Propagation of edge constraints (FC(Edges) and AC(Edges))

Edge constraints may be propagated by forward checking (denoted FC(Edges)): each time a pattern node u is matched to a target node v, FC(Edges) removes from the domain of every node adjacent to u any target node that is not adjacent to v. This may be done in O(d p • n t ).

One may go one step further and maintain the arc consistency of edges constraints (denoted AC(Edges)) so that

∀(u, u ) ∈ E p , ∀v ∈ D u , ∃v ∈ D u , (v, v ) ∈ E t
As a CSP modeling a subgraph isomorphism problem has e p edge constraints and the maximum domain size is n t , the time complexity of AC(Edges) is O(e p • n 2 t ) when using AC4.

Example 2 Let us consider the subgraph isomorphism problem displayed in Fig. 1. Note that this instance has no solution as G p cannot be mapped into a subgraph of G t . Let us suppose that node 3 has been matched to node E so that D 3 = {E}, and that E has been removed from the domains of all other pattern nodes (e.g., by FC(Diff) or GAC(AllDiff)).

FC(Edges) removes B, C, and F from the domains of nodes 1, 2, and 4 because B, C, and F are not adjacent to E whereas 1, 2, and 4 are adjacent to 3.

Like FC(Edges), AC(Edges) removes B, C, and F from the domains of nodes

F(u, v) = ∪ u ∈adj(u) (D u ∩ adj(v)) F(u, v
) is a superset of the set of nodes that may be matched to nodes that are adjacent to u if u is matched to v. Therefore, one can remove v from D u whenever #F(u, v) < #adj(u). One can also remove v from D u whenever there exists a pattern node u ∈ adj(u) such that D u ∩ adj(v) = ∅, thus enforcing arc consistency of edge constraints. The LV2002 filtering algorithm has a time complexity of O(n 2 p • n 2 t ).

Example 3 Let us consider the subgraph isomorphism problem displayed in Fig. 1. Let us suppose that node 3 has been matched to node E so that D 3 = {E}, and that E has been removed from the domains of all other pattern nodes (e.g., by FC(Diff) or GAC(AllDiff)).

Like AC(Edges), LV2002 removes nodes B, C, F , and G from the domains of nodes 1, 2, and 4. It is also able to remove values A and D from the domain of 1. Indeed,

F(1, A) = (D 2 ∪ D 3 ∪ D 4 ) ∩ adj(A) = {D, E} F(1, D) = (D 2 ∪ D 3 ∪ D 4 ) ∩ adj(D) = {A, E}
As, #F(1, A) < #adj(1) and #F(1, D) < #adj(1), both A and D are removed from D 1 so that the domain of 1 becomes empty and an inconsistency is detected.

Iterated Labelling Filtering (ILF(k))

Zampelli et al have proposed in [START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF] a filtering algorithm (called ILF(k)) which exploits the graph structure in a global way to compute labels that are associated with nodes and that are used to filter domains. More precisely, a compatibility relationship is defined over the set of node labels. This compatibility relationship is used to remove from the domain of a pattern node u every target node v such that the label of u is not compatible with the label of v.

ILF(k) is an iterative procedure that starts from an initial labeling. This initial labeling may be defined by node degrees. In this case, the compatibility relationship is the classical ≤ order. This labeling is used to remove from the domain of a pattern node u every target node v such that #adj(u) ≤ #adj(v) as u cannot be matched to v if u has more adjacent nodes than v.

This initial labeling is extended to filter more values. Given a labeling l and a compatibility relationship between labels of l, one defines a new labeling l such that the new label l (u) of a node u is the multiset which contains all labels of nodes adjacent to u. The compatibility relationship is such that l (u) l (v) if for every occurrence x of a label in l (u) there exists a different occurrence y of a label in l (v) such that x y. The key point relies on the computation of the new compatibility relationship , which is done in

O(n p • n t • d p • d t • √ d t )
thanks to the matching algorithm of Hopcroft and Karp (see [START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF] for more details).

Such labeling extensions are iterated. A parameter k is introduced, that determines the number of labeling extensions. Note that iterated labeling extensions may be stopped before reaching this bound k if some domain has been reduced to an empty set, or if a fixpoint is reached -such that no more value may be filtered. The ILF(k) procedure has a time complexity of

O(min(k, n p • n t ) • n p • n t • d p • d t • √ d t ).
[ZDS10] also introduces a weaker filtering, called ILF*(k). The idea is to approximate, at each iteration, the label compatibility relationship by a total order so that the next compatibility relation may be computed by sorting the multisets and sequentially comparing them. The time complexity of this weaker filtering is

O(min(k, n p • n t ) • n p • n t • d t ).
Example 4 Let us consider the subgraph isomorphism problem displayed in Fig. 1. The initial degree-based labeling is the labeling l such that

• l(5) = l(6) = 2 • l(1) = l(3) = l(C) = l(E) = l(F ) = l(G) = 3 • l(2) = l(4) = l(A) = l(B) = l(D) = 4
and the order over this set of labels is such that

• 2 is compatible with 2, 3, and 4,

• 3 is compatible with 3 and 4,

• 4 is compatible with 4.

Hence, one can remove the target nodes C, E, F , and G from the domains of the pattern nodes 2 and 4.

The extension of this initial degree-based labeling is the labeling l such that

• l (1) = l (3) = l (E) = l (F ) = {{3, 4, 4}} • l (2) = l (4) = {{2, 2, 3, 3}} • l (5) = l (6) = {{4, 4}} • l (A) = {{3, 3, 4, 4}} • l (B) = l (D) = {{3, 3, 3, 4}} • l (C) = {{4, 4, 4}} • l (G) = {{3, 3, 4}}
and the order over this set of labels is such that

• {{3, 4, 4}} is compatible with {{3, 3, 4, 4}} and {{3, 4, 4}} • {{2, 2, 3, 3}} is compatible with {{3, 3, 4, 4}} and {{3, 3, 3, 4}} • {{4, 4}} is compatible with {{3, 3, 4, 4}}, {{4, 4, 4}} and {{3, 4, 4}}
As l (1) is not compatible with l (B), B is removed from D 1 . For the same reasons, B, D and G are removed from the domains of nodes 1, 3, 5 and 6.

This new labeling l can be further extended, thus removing more values, and finally proving the inconsistency of this instance.

Discussion

Most of the algorithms that have been proposed for solving the subgraph isomorphism problem may be described by means of the filtering algorithms described in Sections 3.3 to 3.6. In particular:

• These different filterings achieve different consistencies. Some of them are stronger than others. In particular,

• GAC(AllDiff ) is stronger than FC(Diff );

• LV2002 is stronger than AC(Edges) which is stronger than FC(Edges).

However, GAC(AllDiff ) and FC(Diff ) are not comparable with FC(Edges), AC(Edges), LV2002, and ILF(k) as they do not propagate the same constraints.

The relations between ILF(k) and other filterings that propagate edge constraints (i.e., LV2002, AC(Edges), and FC(Edges)) depend on initial domains: if the initial domain of every variable contains all target nodes, then ILF(k) is stronger than LV2002, provided that the number of labeling extensions k is greater or equal to 21 . However, if some domains have been reduced (which is usually the case when the filtering is done at a node which is not at the root of the search tree), then ILF(k) is not comparable with LV2002 and AC(Edges).

Indeed, ILF(k) does not exploit domains to filter values as labelings and compatibility relationships that are iteratively computed do not depend at all on domains. To allow ILF(k) to propagate some domain reductions, the iterative labeling extension process has been combined, before each labeling extension, with the two following steps:

• Reduction of the target graph with respect to domains: if a target node v does not belong to any domain, then this node and its incident edges are discarded from the target graph. • Strengthening of a labeling with respect to singleton domains: if a domain D u is reduced to a singleton {v}, then nodes u and v are labeled with a new label which is not compatible with any other label, except itself, thus preventing other pattern nodes from being matched with v.

When adding these two steps, ILF(k) is stronger than FC(Edges). However, it is still not comparable with LV2002 and AC(Edges).

To propagate more domain reductions, one may start the iterative labeling extension process from an initial labeling which fully integrates domain reductions in the compatibility relation, so that if a target node v does not belong to the domain of a pattern node u, then the label associated with v is not compatible with the label associated with u. More formally, Zampelli et al have defined in [START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF] such an initial labeling, denoted l dom , as follows:

• a different unique label l x is associated with every different (pattern or target) node x ∈ N p ∪ N t ;

• ∀(u, v) ∈ N p ×N t , l u is compatible with l v iff v ∈ D u and #adj(u) ≤ #adj(v).
They have shown that, in this case, ILF(k) is stronger than LV2002 provided that k ≥ 2. However, if this filtering is stronger, it is also very expensive to achieve as the complexity of ILF(k) highly depends on the number of different labels. Indeed, the theoretical complexity of one iteration of ILF(k

) (i.e., O(n p • n t • d p • d t • √ d t )
) corresponds to the worst case where all nodes have different labels. If the number of different pattern and target labels respectively are l p and l t , then the complexity of one iteration of

ILF(k) is O(e p +l p •l t •d p •d t • √ d t ).

Global neighborhood constraints and LAD-filtering

We introduce a global neighborhood constraint in Section 4.1, and we describe a propagation algorithm which achieves the generalized arc consistency of this constraint in Section 4.2. We compare this consistency with other partial consistencies in Section 4.3.

Global neighborhood constraints

For each subisomorphism function f : N p → N t and for each pattern node u ∈ N p , we have:

(1) ∀u ∈ adj(u), f (u ) ∈ adj(f (u)) (2) ∀(u , u") ∈ adj(u) × adj(u), u = u" ⇒ f (u ) = f (u")
The first property is a direct consequence of the fact that edges are preserved by subisomorphism functions whereas the second property is a direct consequence of the fact that subisomorphism functions are injections.

When considering the CSP associated with a subgraph isomorphism problem, these two properties may be expressed by the following constraint on the neighborhood of u:

x u = v ⇒ ∀u ∈ adj(u), x u ∈ adj(v) ∧allDiff ({x u |u ∈ adj(u)})
Note that the filtering algorithm LV2002 introduced by Larrosa and Valiente in [START_REF] Larrosa | Constraint satisfaction algorithms for graph pattern matching[END_REF] actually propagates this neighborhood contraint (although it has not been explicitely introduced in [LV02]). However, LV2002 only ensures a partial consistency: it basically ensures that the number of nodes adjacent to u is smaller or equal to the number of target nodes that are both adjacent to v and belong to domains of nodes adjacent to u. In Section 4.2, we describe a filtering algorithm which ensures the generalized arc consistency of neighborhood constraints.

Example 5 Let us consider the subgraph isomorphism problem displayed in Fig. 1, and let us define initial domains with respect to node degrees, i.e.

D 1 = D 3 = D 5 = D 6 = {A, B, C, D, E, F, G} D 2 = D 4 = {A, B, D}
The neighborhood constraint for the couple of nodes (1, G) is

x 1 = G ⇒ x 2 ∈ {B, F, E} ∧ x 3 ∈ {B, F, E} ∧ x 4 ∈ {B, F, E} ∧allDiff ({x 2 , x 3 , x 4 })
Achieving the generalized arc consistency of this constraint allows us to remove G from D 1 : if x 1 = G then both x 2 and x 4 must belong to the singleton {B} (corresponding to the intersection of their domains with {B, F, E}) so that x 2 and x 4 cannot be assigned to different values. Note that on this example, the filtering

LV2002 cannot remove G from D 1 as F(1, G) = (D 2 ∪ D 3 ∪ D 4 ) ∩ adj(G) = {B, E, F } so that #F(1, G) ≥ #adj(1).
Note also that a simple allDiff constraint on the set of variables {x 2 , x 3 , x 4 } cannot be used to remove G from D 1 : one has to combine this allDiff constraint with the fact that, if 1 is matched to G, then 2, 3, and 4 must be matched to nodes that are adjacent to G.

A filtering algorithm for propagating global neighborhood constraints

The generalized arc consistency of a neighborhood constraint may be ensured by looking for a covering matching in a bipartite graph, as proposed by Régin in [START_REF] Regin | A filtering algorithm for constraints of difference in CSPs[END_REF] for the AllDifferent global constraint. Let us recall that a matching of a graph G = (N, E) is a subset of edges m ⊆ E such that no two edges of m share a same endpoint. A matching m ⊆ E covers a set of nodes N i if every node of N i is an endpoint of an edge of m. In this case, we shall say that m is a N i -covering matching of G.

For every couple of nodes (u, v) such that v ∈ D u , we define a bipartite graph that associates a node with every node adjacent to u or v and an edge with every couple (u , v ) such that v ∈ D u .

Definition 1 Given two nodes (u, v) ∈ N p × N t such that v ∈ D u , we define the bipartite graph G (u,v) = (N (u,v) , E (u,v) ) such that • N (u,v) = adj(u) ∪ adj(v); • E (u,v) = {(u , v ) ∈ adj(u) × adj(v) | v ∈ D u }
If there does not exist a matching of the bipartite graph G (u,v) that covers adj(u), then the nodes adjacent to u cannot be matched to all different nodes, and therefore v can be removed from D u . This filtering must be iterated. Indeed, when v is removed from D u , the edge (u, v) is removed from other bipartite graphs so that some bipartite graphs may no longer have covering matchings. A key point for an incremental implementation of this filtering lies in the fact that the edge (u, v) only belongs to bipartite graphs G (u ,v ) such that u ∈ adj(u) and v ∈ adj(v) ∩ D(u ). Filtering is iterated until either a domain becomes empty -thus detecting an inconsistency-or reaching a fixpoint such that generalized arc consistency has been enforced, i.e., such that for every couple (u, v) there exists a adj(u)-covering matching of G (u,v) .

Example 6 The bipartite graph G (1,G) used to propagate the neighborhood constraint of Example 5 is displayed in the left part of Fig. 2. There does not exist a matching of this graph that covers adj(1) because both 2 and 4 can only be matched to B. As a consequence, one can remove G from D 1 .

The bipartite graph G (3,E) used to propagate the neighborhood constraint associated with the couple (3, E) is displayed in the right part of Fig. 2. There exists a matching of this graph that covers adj(3) (e.g., m = {(1, G), (2, A), (4, D)}) so that E is not removed from D 3 . However, once G has been removed from D 1 , the edge (1, G) is removed from G (3,E) and there no longer exists a matching that covers adj(3) (as both 1, 2, and 3 can only be matched to A and D).

Hence, E is also removed from D 3 .

Algorithm 1 describes the resulting filtering procedure, called LAD (Local All Different) filtering. This procedure takes in input a set S of couples of pattern/target nodes to be filtered. At the root of the search tree, this set Algorithm 1. LAD-filtering Input: A set S of couples of pattern/target nodes to be filtered Output: failure (if an inconsistency is detected) or success.

In case of success, domains are filtered so that ∀u ∈ N p , ∀v ∈ D u , there exists a matching of G (u,v) that covers adj(u). begin while S = ∅ do Remove a couple of pattern/target nodes (u, v) from S if there does not exist a matching of G (u,v) that covers adj(u) then

Remove v from D u if D u = ∅ then return failure S ← S ∪ {(u , v ) | u ∈ adj(u), v ∈ adj(v) ∩ D u } end end return success end should contain all couples of pattern/target nodes, i.e., S = {(u, v) | u ∈ N p , v ∈ D u }.
Then, at each choice point of the search tree, S should be initialized with the set of all couples (u, v) such that v ∈ D u and a node adjacent to v has been removed from the domain of a node adjacent to u since the last call to LAD-filtering.

For each couple of nodes (u, v) that belongs to the set S, LAD-filtering checks if there exists a matching of G (u,v) that covers adj(u). If this is not the case, then v is removed from D u , and all couples (u , v ) such that u is adjacent to u, and v is adjacent to v and belongs to D u are added to S.

The key point is to efficiently implement the procedure that checks if there exists a covering matching of G (u,v) . Régin has shown in [START_REF] Regin | A filtering algorithm for constraints of difference in CSPs[END_REF] that one can use the algorithm of Hopcroft and Karp [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF] to find such a matching. The time complexity of this algorithm is O(a √ b) where a and b respectively are the number of edges and nodes in the bipartite graph. As the bipartite graph G (u,v) has #adj(u) + #adj(v) nodes and, in the worst case (if no domain has been reduced), #adj(u) • #adj(v) edges, and as d t ≥ d p (otherwise the subgraph isomorphism problem instance is trivially inconsistent), the complexity of checking if there exists a covering matching of

G (u,v) is O(d p • d t • √ d t ).
This complexity may be improved by exploiting the fact that the algorithm of Hopcroft and Karp is incremental: starting from an empty matching, it iteratively computes new matchings that contain more edges than the previous matching, until the matching is maximal. Each iteration basically consists in a breadth first search and is in O(d p • d t ) whereas the number of iterations is bounded by 2 • d t + d p . However, if one starts the algorithm from a matching that already contains k edges, and if the maximal matching has l edges, then the number of iterations is also bounded by l -k (as the size of the matching increases of at least one at each iteration).

We use this property to improve the time complexity of LAD-filtering. More precisely, for each pattern node u ∈ N p and each target node v ∈ D u , we memorize the last computed matching of G (u,v) . The space complexity of memorizing the covering matchings of all bipartite graphs is O(n p • n t • d p ) (there are at most n p • n t bipartite graphs, and the covering matching of G (u,v) is composed of #adj(u) edges). As it would be very expensive, both in time and memory, to create a copy of all covering matchings at each choice point, we simply update these covering matchings whenever this is necessary. More precisely, each time we need to check if there exists a covering matching of a bipartite graph G (u,v) , we proceed as follows:

(1) we scan the last recorded matching of adj(u) and remove every couple (u , v ) such that v no longer belongs to D(u );

(2) if one or more couples have been removed, then we call Hopcroft Karp to complete it; (3) if Hopcroft Karp actually succeeds in completing it, then we record the computed complete matching.

Theorem 1 The time complexity of LAD-filtering is

O(n p • n t • d 2 p • d 2 t ).
Proof.

•

Comparison of LAD-filtering with other filterings

In this section, we compare the consistency ensured by LAD-filtering with other partial consistencies.

Theorem 2 LAD-filtering (algorithm 1 with S initialized to all couples (u, v) such that u ∈ N p and v ∈ D u ) ensures the Generalized Arc Consistency of neighborhood constraints, denoted GAC(Neighborhood).

Proof. If there exists a pattern node u ∈ N p such that for every target node v ∈ D u , it is not possible to assign every different pattern node u ∈ adj(u) to a different target node which is adjacent to v and belongs to D u , then LADfiltering removes every value v ∈ D u (because every bipartite graph G (u,v) does not have a adj(u)-covering matching), and returns failure. Otherwise, it returns success and filters domains so that for every pattern node u ∈ N p and every target node v ∈ D u , every different pattern node u ∈ adj(u) can be assigned to a different target node which is adjacent to v and belongs to D u (as every bipartite graph G (u,v) has an adj(u)-covering matching).

Theorem 3 GAC(Neighborhood) is stronger than LV2002

Proof. GAC(Neighborhood) is at least as strong as LV2002 because, for each pattern node u ∈ N p and each target node v ∈ D u , if there exists a adj(u)covering matching of G (u,v) , then all target nodes of this covering matching belong to the set F(u, v) and therefore #F(u, v) ≥ #adj(u). It is actually strictly stronger: for example, it is able to detect the inconsistency of the instance displayed in Figure 1 whereas LV2002 is only able to reduce the domains of the variables associated with nodes 2 and 4 to {A, B, D} whereas the domains of the other variables are not reduced.

Theorem 4 GAC(Neighborhood) is as strong as ILF(k) when labeling extensions are started from the initial labeling l dom and when they are iterated until reaching a fixpoint, i.e., k = ∞.

Proof. The initial labeling l dom associates a unique different label with every node, and the label of a pattern node u is compatible with the label of a target node v iff #adj(u) ≤ #adj(v) and v ∈ D u . With such an initial compatibility relationship, the multiset m u that contains all labels of nodes adjacent to u is compatible with the multiset m v that contains all labels of nodes adjacent to v iff there exists a covering matching of G (u,v) (as a label of m u is compatible with a label of m v iff there is an edge between the corresponding nodes in G (u,v) ). When a node v is removed from a domain D u , both ILF(∞) and LAD check, for every couple (u , v ) ∈ adj(u)×adj(v)∩D u , that every node adjacent to u may still be matched to a different node adjacent to v . In both cases, this is done in an iterative process, until a fixpoint is reached. The difference between ILF(∞) and LAD is that ILF(∞) recomputes all matchings, for all possible pattern/target couples, at each iteration, whereas LAD only updates matchings that have actually been impacted by domain reductions. Hence, LAD has a lower time complexity.

Actually, ILF(k) performs very poorly when it is started from the initial labeling l dom . It performs much better when it is started from an initial labeling defined with respect to node degrees: with such an initial labeling, the number of different labels is usually strongly reduced and, therefore, the number of compatibility relationships to compute is also strongly reduced.

Theorem 5 GAC(Neighborhood) is weaker than Singleton Arc Consistency of Edge and AllDifferent constraints (denoted SAC(Edges + AllDiff)).

Proof. Let us first recall that singleton arc consistency ensures that we can enforce arc consistency without failure after any assignment of a value to a variable [START_REF] Bessiere | Theoretical analysis of singleton arc consistency and its extensions[END_REF]. Hence, SAC(Edges + AllDiff ) ensures that, ∀u ∈ N p , ∀v ∈ D u , if D u is reduced to the singleton {v}, then AC(Edges) combined with GAC(AllDiff ) does not detect an inconsistency.

• SAC(Edges+AllDiff ) is at least as strong as GAC(Neighborhood): when reducing a domain D u to a singleton {v}, if AC(Edges) combined with GAC(AllDiff ) does not detect an inconsistency, then there exists a adj(u)covering matching of the bipartite graph G (u,v) . Indeed, AC(Edges) will reduce domains of nodes adjacent to u to nodes which are adjacent to v, while GAC(AllDiff ) will ensure that all nodes adjacent to u can be assigned to all different values. • SAC(Edges+AllDiff ) is actually stronger than GAC(Neighborhood) as it is able to detect the inconsitency of the subgraph isomorphism problem instance displayed in Fig. 3 whereas GAC(Neighborhood) does not reduce any domain.

( However, the optimal worst-case time complexity of enforcing singleton arc consistency of a binary CSP is O(nd 3 e) where e is the number of constraints, n is the number of variables and d is the domain size [START_REF] Bessiere | Theoretical analysis of singleton arc consistency and its extensions[END_REF].

Extension to directed graphs

LAD-filtering may be extended to directed graphs in a rather straightforward way. In directed graphs, edges are ordered couples of nodes and, for each node u, one distinguishes the set of successor nodes succ(u) that may be reached by an outgoing edge (i.e., succ(u) = {u ∈ N | (u, u ) ∈ E}), from the set of predecessor nodes pred(u) that may be reached from an ingoing edge (i.e., pred(u

) = {u ∈ N | (u , u) ∈ E}).
To extend LAD-filtering to directed graphs, one has to associate two bipartite graphs with every couple (u, v) such that u ∈ N p and v ∈ D u :

• the bipartite graph used to check that each successor of u may be matched to a different successor of v, i.e., G succ

(u,v) = (N succ (u,v) , E succ (u,v) ) with N succ (u,v) = succ(u)∪ succ(v) and E succ (u,v) = {(u , v ) ∈ succ(u) × succ(v) | v ∈ D u } • the bipartite graph used to check that each predecessor of u may be matched to a different predecessor of v, i.e., G pred (u,v) = (N pred (u,v) , E pred (u,v) ) with N pred (u,v) = pred(u) ∪ pred(v) and E pred (u,v) = {(u , v ) ∈ pred(u) × pred(v) | v ∈ D u } Algorithm 2.

LAD-filtering

Input: A set S of triples (u, v, x) such that x ∈ {pred, succ} Output: failure (if an inconsistency is detected) or success.

In case of success, domains are filtered so that ∀u ∈ N p , ∀v ∈ D u , there exist a matching of G pred (u,v) that covers pred(u) and a matching of G succ

(u,v)
that covers succ(u). begin while S = ∅ do Remove a triple (u, v, x) from S if there does not exist a matching of

G x (u,v) that covers x(u) then Remove v from D u if D u = ∅ then return failure S ← S ∪ {(u , v , succ) | u ∈ succ(u), v ∈ succ(v) ∩ D u } ∪ {(u , v , pred) | u ∈ pred(u), v ∈ pred(v) ∩ D u } end end return success end
Algorithm 2 extends Algorithm 1 to directed graphs. The main difference is that it maintains a set of triples (u, v, x) such that x ∈ {pred, succ} instead of a set of couples (u, v). At each iteration, a triple (u, v, x) is removed from the set, and if the graph G x (u,v) does not have a covering matching, then v is removed from D u and S is updated by adding all triples (u , v , x ) such that an edge has been removed from the bipartite graph G x (u ,v ) .

6 Experimental results

Test suite

We consider 1993 subgraph isomorphism instances that come from three different databases.

Scale-free database (classes sf-d-D-n and si-d-D-n) This database has been used in [START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF] to evaluate ILF(k). Graphs of these instances are scale-free networks that have been randomly generated using a power law distribution of degrees P (d = k) = k -λ with λ = 2.5 (see [START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF] for more details). There are 5 classes. Each of the first four classes, denoted sf-d-D-n, contains 20 feasible instances such that the target graph has n nodes which degrees are bounded between d and D, and the pattern graph is extracted from the target graph by randomly selecting 90% of nodes and edges from the target graph in such a way that the pattern graph is still connected. The fifth class, denoted si-d-D-n, contains 20 non feasible instances that have been generated like instances of the first four classes, excepted that 10% of new edges have been added in pattern graphs in order to obtain infeasible instances.

GraphBase database (class LV) This database has been used in [START_REF] Larrosa | Constraint satisfaction algorithms for graph pattern matching[END_REF] to evaluate LV2002. It contains 113 undirected graphs with different properties, i.e., simple, acyclic, connected, biconnected, triconnected, bipartite and planar. We have considered the 50 first graphs. This set contains graphs ranging from 10 to 128 nodes. Using these graphs, we have generated 793 instances of the subgraph isomorphism problem by considering all couples of graphs (G p , G t ) that are not trivially solved, i.e., such that e p > 0, n p ≤ n t and d p ≤ d t .

Vflib database (classes bvg-n, bvgm-n, m4D-n, m4Dr-n, and r-dn) This database has been used in [START_REF] Cordella | Performance evaluation of the vf graph matching algorithm[END_REF] to evaluate Vflib, a program dedicated to graph and subgraph isomorphism problems. It contains 63 classes of instances, and each class contains instances such that the target graph has from 20 to 1000 nodes. For each class, we have only considered 4 sizes and, for each size, we have only considered the first 10 instances. We have grouped classes as follows (see [START_REF] Foggia | A database of graphs for isomorphism and sub-graph isomorphism benchmarking[END_REF] for more details on the original classes):

• bvg-n (where n ∈ {100, 200, 400, 800} corresponds to the number of nodes of the target graphs); These classes contain fixed-valence graphs and are composed of the first 10 instances of the original classes si x -b y -n where x ∈ {2, 4, 6} corresponds to the size of the pattern graph with respect to the target graph (i.e., 20%, 40%, or 60%) and y ∈ {3, 6, 9} corresponds to the valence. Hence, each class bvg-n contains 90 instances.

• bvgm-n (where n ∈ {100, 200, 400, 800} corresponds to the number of nodes of the target graphs); These classes contain modified bounded-valence graphs and are composed of the first 10 instances of the original classes si x -b y m-n where x ∈ {2, 4, 6} corresponds to the size of the pattern graph with respect to the target graph (i.e., 20%, 40%, or 60%) and y ∈ {3, 6, 9} corresponds to the valence. Hence, each class bvgm-n contains 90 instances.

• m4D-n (where n ∈ {81, 256, 526, 1296} corresponds to the number of nodes of the target graphs); These classes contain graphs that correspond to 4D regular meshes and are composed of the first 10 instances of the original classes si x -m4D-n where x ∈ {2, 4, 6} corresponds to the size of the pattern graph with respect to the target graph (i.e., 20%, 40%, or 60%). Hence, each class m4D-n contains 30 instances.

• m4Dr-n (where n ∈ {81, 256, 526, 1296} corresponds to the number of nodes of the target graphs): These classes contain graphs that correspond to 4D irregular meshes and are composed of the first 10 instances of the original classes si x -m4Dr r -n where x ∈ {2, 4, 6} corresponds to the size of the pattern graph with respect to the target graph (i.e., 20%, 40%, or 60%) and r ∈ {2, 4, 6} corresponds to the degree of irregularity. Hence, each class m4Dr-n contains 90 instances.

• r-p-n (where n ∈ {100, 200, 400, 600} corresponds to the number of nodes and p ∈ {0.01, 0.05, 0.1} corresponds to the probability of adding an edge between two nodes). These classes contain graphs that have been randomly generated and are composed of the first 10 instances of the original classes si x -rand-r p -n where x ∈ {2, 4, 6} corresponds to the size of the pattern graph with respect to the target graph (i.e., 20%, 40%, or 60%). Hence, each class r-p-n contains 30 instances.

Considered solvers

LAD LAD-filtering has been implemented in C and has been integrated in a complete tree search. At each node of the search tree, the next pattern node to be assigned is chosen with respect to the minDom heuristic, i.e., we choose the non assigned pattern node that has the smallest number of target nodes in its domain. A choice point is created for each target node that belongs to the domain of the variable to be assigned, and these different choice points are explored by increasing order of values. At each node of the search tree, LAD-filtering is combined with GAC(AllDiff ). This search procedure is called LAD.

LAD is compared with ILF(k), with k ∈ {1, 2, 4}, Abscon(GAC), Abscon(FC), and Vflib.

ILF(k)

The original implementation of ILF(k) was in Gecode. We consider here a new implementation in C which uses the same data structures and the same ordering heuristics as LAD, and which is also combined with GAC(AllDiff ). This new implementation is much more efficient than the original one. For example, instances of class sf5-8-1000 are solved in 0.19 seconds with the new implementation of ILF(1) whereas they were solved in 11.2 seconds with the old implementation.

We compare results obtained with different numbers of labeling extension iterations, i.e., with k ∈ {1, 2, 4}. We do not report results with k > 4 as this never improves the solution process.

Abscon Abscon is a generic CSP solver written in Java by Lecoutre and Tabary (see [START_REF] Lecoutre | Abscon 112: towards more robustness[END_REF] for more details). The fact that Abscon is implemented in Java whereas all other approaches are implemented in C or C++ must be taken into account since Java programs have running times several time larger than their C/C++ counterparts. We consider two variants of this solver:

• Abscon(FC) performs a forward checking propagation of the constraints, i.e., FC(Edges) and FC(Diff ). • Abscon(AC) maintains Arc Consistency of edge constraints. For the difference constraints, it maintains a consistency that is stronger than AC(Diff ) but weaker than GAC(AllDiff ). It also uses symetry breaking techniques.

Both variants consider the minDom ordering heuristic for choosing the next variable to assign.

Vflib Vflib [CFSV99,CFSV01] is a solver dedicated to graph and subgraph isomorphism problems, and it is considered as the state-of-the-art for subgraph isomorphism. It basically performs a forward checking propagation of edge and difference constraints, but this propagation is limited to nodes that are adjacent to already matched nodes for difference constraints. It uses specific variable and value ordering heuristics: variable and values are chosen so that the subgraph induced by the matched nodes is connected (except when the pattern or the target graphs are composed of different connected components).

Experimental comparison on the problem of finding all solutions

Let us first consider the problem of finding all solutions to an instance, thus allowing a comparison that is less dependent on value ordering heuristics. For this first experiment, we have discarded instances that have too many solutions. Hence, we have only considered classes from the scalefree database, and the smallest classes of the vflib database (such that the target graph has 100 or 81 nodes).

Table 1 displays, for each class and each considered approach, the number of instances for which all solutions have been found in less than one hour on a 2.26 GHz Intel Xeon E5520, and the average corresponding CPU time. On these classes, LAD has solved 1 (resp. 3, 3, 23, 29, and 143) more instances than ILF(1) (resp. ILF(2), ILF(4), Abscon(AC), Abscon(FC), and Vflib. When comparing CPU times, we note that LAD is slower than the three variants of ILF on classes sf-5-8-* and bvg, but these instances are easy ones and LAD solves them in less than one second. However, on harder classes such as si20-300-300, r0.05-100, and r0.1-100, LAD is significantly quicker than ILF. On all classes, LAD and ILF are an order quicker than Abscon. Vflib is competitive on classes bvg-100, m4D-81, and m4Dr-81, but it is not competitive at all on all other classes.

Table 2 displays the average number of fail nodes (i.e., the number of times an inconsistency is detected), for each class and each approach except Vflib (because this information is not available in Vflib). On some classes, such as sf5-8-*, LAD and ILF have comparable numbers of failed nodes, and this corresponds to the classes that are more quickly solved by ILF than by LAD. However, on some other instances, such as r*-100, LAD explores many fewer nodes than ILF. The number of fail nodes of both ILF and LAD is an order smaller than Abscon. On some classes, Abscon(AC) has more fail nodes than Abscon(FC), but this corresponds to the fact that Abscon(AC) solves more instances than Abscon(FC) and, for these harder instances, the number of fail nodes is significantly higher than for the instances that are solved by both approaches.

Experimental comparison on the problem of finding the first solution

To illustrate scale-up properties of the different approaches and compare them on a larger set of instances, we now consider the problem of finding the first solution (or proving inconsistency). For this comparison, we consider instances of the LV class and the larger classes of the vflib database (such that the target graph has more than 100 nodes). 3 Finding the first solution of instances of the LV class: #solved is the number of solved instances (in less than one hour on a 2.26 GHz Intel Xeon E5520), Time and #fail respectively give the CPU time and the number of fail nodes (average on the completed runs). and sizes; some instances are feasible and have many solutions, some others are inconsistent). For this class, LAD has solved 29 (resp. 29, 30, 66, 81, and 260) more instances than ILF(4) (resp. ILF(2), ILF(1), Abscon(AC), Abscon(FC), and Vflib). This table also shows us that Abscon(AC) and ILF(1) have comparable number of fail nodes, and nearly four times as less as Abscon(FC). ILF(2) and ILF(4) have smaller number of fail nodes but the reduction of the search space is not enough to allow ILF(2) and ILF(4) to become competitive. The number of fail nodes of LAD is much smaller (more than 20 times as small as Abscon(AC) and ILF(1)).

Tables 4 and 5 allow us to compare scale-up properties of the different considered approaches. Table 4 displays results on rather easy classes of the Vflib database. LAD is able to solve the 900 instances of these classes in less than 1.5 seconds on average, and it is nearly 4 times as fast as ILF(k). It is also significantly faster than Abscon. Interestingly, Vflib is very efficient and exhibits very good scale-up properties on some classes such as bvg-*, bvgm-*, and m4Dr-*. Actually, Vflib uses variable and value ordering heuristics that are not used by the other approaches: at each iteration, it chooses the next couple (u, v) of nodes to match so that both u and v are adjacent to some nodes that have already been matched (whenever this is possible). These ordering heuristics may explain the very good behavior of Vflib on some instances when the goal is to find only one solution. It may also explain the fact that it is able to solve 29 instances of the m4D-256 class in less than 0.01 second, whereas it is not able to solve the last instance of this class in one hour. However, Table 5 shows us that the different approaches exhibit different scaleup properties on the random classes r-p-n. Indeed, when the probability p of adding an edge is 0.01, LAD is better than Abscon which is better than ILF, whereas when this probability increases, Abscon is better than ILF which is better than LAD. Actually, the denser and the larger the graphs, and the worse LAD. This may come from the fact that the complexity of LAD-filtering is

O(n p • n t • d 2 p • d 2 t )
: the degree is 10 times bigger (on average) for the graphs of classes r0.1-* than for those of classes r0.01-*. Therefore, when graphs are rather sparse, it is worth filtering with LAD whereas when graphs are denser, one has better consider a simpler filtering procedure such as AC(Edges).

Conclusion

We have introduced a new filtering algorithm for subgraph isomorphism that basically ensures that all nodes adjacent to a same pattern node may be matched to nodes that are all different and that are all adjacent to a same target node. This filtering is stronger than LV2002. Actually, it achieves the same consistency as the strongest variant of ILF(k), i.e., when the initial la- 5 Finding the first solution of hard instances of the Vflib base: for each class, the first line displays the number of solved instances (in less than one hour on a 2.26 GHz Intel Xeon E5520) and the second line the CPU time (average on completed runs).

beling fully integrates domain reductions and when labeling extensions are iterated until reaching a fixpoint. However, this consistency is achieved at a lower cost by updating matchings incrementally instead of recomputing them from scratch at each iteration, and by updating only the matchings that are impacted by a domain reduction instead of recomputing all matchings.

We have experimentally shown on a wide benchmark of 2000 or so instances that this new filtering is able to solve more instances quicker, and that it drastically reduces the search space so that many instances are solved without backtracking. However, this filtering is outperformed by arc consistency on the densest random graphs, such that edge density is greater or equal to 10%. This filtering procedure could be easily integrated within a constraint programming language. In particular, we plan to integrate it in our constraintbased graph matching system [START_REF] Le Clément | Constraint-based graph matching[END_REF] that is built on top of Comet [START_REF] Van Hentenryck | Constraint-Based Local Search[END_REF].

We also plan to improve LAD-filtering by studying different strategies for choosing, at each iteration, the next couple (u, v) that is removed from S. In the results reported in this paper, we have considered a basic last in first out strategy as S is implemented with a stack. However, we could use a priority queue that orders couples with respect to the number of edges that have been removed from the corresponding bipartite graph. Further work will also concern the extension of this filtering procedure to the maximum common subgraph problem, which involves finding the largest graph that is subisomorphic to two given graphs. Indeed, the algorithm of Hopcroft and Karp may be used to compute the maximal matching of bipartite graphs G (u,v) , thus giving a bound on the largest number of edges that may be matched when u is matched to v.

Fig. 1 .

 1 Fig. 1. Instance of subgraph isomorphism problem.

  McGregor [McG79] combines FC(Diff ) and FC(Edges); • Ullmann [Ull76] combines FC(Diff ) and AC(Edges); • Régin [R 95] combines GAC(AllDiff ) and AC(Edges); • Larrosa and Valiente [LV02] combine GAC(AllDiff ) and LV2002; • Zampelli et al combine GAC(AllDiff ), AC(Edges), and ILF(k).

Fig. 2 .

 2 Fig. 2. Bipartite graphs associated with (1, G) and (3, E).

Fig. 3 .

 3 Fig. 3. Instance of subgraph isomorphism problem. Let us suppose that the initial domains are D 1 = D 2 = D 3 = {A, B, C, D}. GAC(Neighborhood) does not reduce any domain as every bipartite graph G (u,v) has an adj(u)-covering matching (see, e.g., the bipartite graph G (1,a) displayed on the right part of the Figure). However, SAC(Edges + AllDiff ) detects an inconsistency: if D 1 is reduced to {A}, then AC(Edges) reduces D 2 and D 3 to nodes that are adjacent to A (i.e., to {C, B}) and the edge (3, 2) is no longer supported (as G t has no edge between C and B) so that AC(Edges) detects an inconsistency.

  1, 2, and 4. It is also able to remove G from the domain of 1 as the matching (1, G) has no support for the edge (1, 4). Indeed, none of the adjacent nodes of G (i.e., B, F , and E) belongs to the domain of 4. For the same reasons, AC(Edges) also removes G from the domains of 2 and 4.

	3.5 Propagation of a set of edge constraints (LV2002)
	Both FC(Edges) and AC(Edges) propagate each edge constraint separately. A
	stronger filtering is obtained by propagating edge constraints in a more global
	way, i.e., by propagating the fact that a whole set of nodes must be adjacent
	to a given node. Indeed, a pattern node u may be matched to a target node
	v only if the number of nodes adjacent to u is smaller or equal to the number
	of target nodes that are both adjacent to v and belong to domains of nodes
	adjacent to u (otherwise some nodes adjacent to u cannot be matched to nodes
	adjacent to v). Hence, Larrosa and Valiente have proposed in [LV02] a filtering
	algorithm (denoted LV2002) which propagates this constraint. More precisely,
	they define the set

  For our subgraph isomorphism CSP, if we only consider the binary edge constraints, we have n = n p , d = n t , and e = e p so that enforcing SAC(Edges) is in O(n p • n 3 t • e p ). Let us consider the case of fixed-degree graphs such that e p = (n p • d p )/2. In this case, the time complexity of enforcing SAC(Edges) is O(n 2 p • n 3 t • d p ), which should be compared to the time complexity of LAD-filtering, i.e., O(n p • n t • d 2 p • d 2 t ). In the worst case, i.e., if both G p and G t are complete graphs so that d p = n p -1 and d t = n t -1, enforcing SAC(Edges) and LAD-filtering have the same time complexity. However, for sparser graphs, LAD-filtering has a lower time complexity.

  Finding all solutions: for each class, the first line gives the number of solved instances (in less than one hour on a 2.26 GHz Intel Xeon E5520), and the second line gives the CPU time (average on the completed runs).

				Abscon			ILF		LAD
	Class (#solutions)	Vflib	FC	Abscon AC		k=1	ILF k=2	k=4	LAD
	Class sf5-8-200 (1.10)			FC 3,076	AC 108	k=1 5	k=2 0	k=4	0	0
	sf5-8-200 sf5-8-600 (1.00)		16	418	20	418	20	20 4	20 0	20 0	20 0
	sf5-8-1000 (1.05)	72.45	2.04 557	1.75 557	0.00 7	0.02 0	0.03 0	0.02 0
	sf5-8-600 sf20-300-300 (4.45)	0	397,844	20	29,338	20	20 38	20 13	20 7	20 0
	si20-300-300 (0.00)		-	138.10 913,730	135.01 61,191	0.07 15,342	0.15 62	0.15 22	0.29 27
	sf5-8-1000 bvg-100 (218)		0	10,037	20	2,862	20	20 461	20 391	20 391	20 0
	bvgm-100 (145,855)		8,977		95,618		641	379	222	1
			-1651.11 1631.88	0.19	0.55	0.59	0.83
	m4D-81 (1,253)			1,904		327		701	669	652	23
	sf20-300-300 m4Dr-81 (30,642)		0	22,920	16	23,592	16	20 1,356	20 1,304	20 1,300	20 12
	r0.01-100 (57,291,325)	-	386.87 38,853 6,749,220 474.11	0.35 10,621	5.95 6,717	8.24 6,175	2.56 60
	si20-300-300 r0.05-100 (6,062,230)	0	233,044	6	5 615,882 2,857,279 20	19 539,522	19 539,167	20 5,243
	r0.1-100 (30,501,838)	-	823.20 1046.91 819,714 1,985,225 2,227,792 2,224,579 2,224,408 320,067 132.33 30.42 48.75 27.77
	bvg-100	90		90		90	90	90	90	90
		0.02	1.99	2.78	0.04	0.07	0.13	0.75
	bvgm-100		89		89		90	90	90	90	90
		6.55	11.06	16.57	0.48	0.49	0.48	0.53
	m4D-81	30		30		30	30	30	30	30
		0.09	1.08	1.04	0.03	0.05	0.05	0.02
	m4Dr-81	90		90		90	90	90	90	90
		1.65	3.70	2.40	0.18	0.19	0.20	0.18
	r0.01-100		21		23		28	29	29	29	29
		83.60	121.98	322.67 158.35 170.63 170.53	180.24
	r0.05-100		2		22		23	23	22	22	23
	513.01	28.60	56.78	135.81 107.18 108.99	19.73
	r0.1-100		0		25		28	28	28	28	29
			-	64.91	218.38	217.17 242.00 243.12 148.38
	All instances	338		451	460	480	478	478	481
		13.83	118.72	144.86	34.41	31.09	32.07	22.34
	Table 1

Table 2

 2 Number of fail nodes (average on the completed runs); numbers in brackets after class names give the average number of solutions of the instances of the class.

Table 3

 3 displays the number of solved instances for the LV class, which contains 793 instances with many different features (graphs have different properties

		Vflib	Abscon			ILF		LAD
			FC	AC	k=1	k=2	k=4
	#solved	468	647	662	698	699	699	728
	Time	73.72	72.51	54.25	30.85	31.12	30.77	14.57
	#fail	-1,202,372 324,075 297,107 182,588 159,493 13,560
	Table

  Finding the first solution of easy instances of the vflib base: for each class, the first line displays the number of solved instances (in less than one hour on a 2.26 GHz Intel Xeon E5520) and the second line the CPU time (average on completed runs).

			Vflib Vflib	Abscon Abscon				ILF	ILF	LAD	LAD
	Class Class			FC FC	AC AC		k=1 k=1	k=2	k=4 k=2	k=4
	bvg-200 r0.01-200		90 3	90 28	90 30	90	28	90	90 28	90 28	30
		0.00 1735.93	0.68 192.14	0.78 0.99	0.00 0.00 0.00 27.48 44.09	0.14 46.49	0.04
	bvg-400 r0.01-400		90 0	90 20	90 29	90	14	90	90 14	90 14	30
			0.00 -	2.85 33.14	2.99 69.68	0.01 175.83	0.01 228.78 0.01	1.06 214.85	45.58
	r0.01-600		0	23	23		12			9	7	29
	bvg-800		90 -	90 226.38	90 236.14	90 428.14 1069.96 90 90	90 806.96 113.51
			0.02	54.13	54.86		0.03			0.04	0.05	8.41
	r0.05-200		0	25	28		28			28	28	30
	bvgm-200		90 -	90 266.77	90 142.80	90 125.57	90 198.68 90	90 198.66	38.28
	r0.05-400		0.00 0	0.95 22	0.73 24	0.00 0.00 0.00 25 25	0.01 25	17
	bvgm-400		90 -	89 632.84	89 647.48	90 519.04	90 500.54 494.12 1190.88 90 90
	r0.05-600		0.01 0	3.20 14	1.66 14	1.55 0.01 0.01 13 5	0.04 5	1
	bvgm-800		90 -1915.65 1936.98 1505.51 2319.68 2304.85 2100.61 90 90 90 90 90 90
	r0.1-200		0.03 0	12.02 27	12.07 29	0.06	26	0.04 0.03 26	0.19 26	21
	m4D-256		29 -	30 143.36	30 309.54	30 320.52	30 357.70 30	30 351.10	646.31
	r0.1-400		0.00 0	2.88 6	1.73	6	0.01 0.01 0.01 5 5	0.04 5	1
	m4D-526		23 -1764.63 1972.18 1950.67 1917.68 2070.81 30 30 29 30 29 30	961.35
	r0.1-600		4.11 159.76 164.90 0 0	0	9.61 32.93 30.72 1.71 0 0 0	0
	m4D-1296		20 -	23 -	23	-	29		-	29	-	29	30 -	-
	All inst.		0.05 252.73 242.47 52.93 61.21 73.33 5.67 3 165 183 151 140 138	159
	m4Dr-256 Table	90 1735.93	90 443.14	90 409.55	90 414.03	90 447.36 90	426.67 90	268.48
			0.00	7.91	1.44		0.23			1.05	2.24	0.06
	m4Dr-526		90	89	89		89			89		89	90
			0.01	23.47	23.35 14.02 18.31 19.08	0.33
	m4Dr-1296		90	89	89		90			90	90	90
			0.06 193.27 188.44		6.41			5.46	5.43	1.63
	All instances	882	890	890		897			898	897	900
			0.12	41.95	40.60		4.25			5.55	6.04 1.43
	Table 4

k must be greater or equal to

if the initial labeling from which the iterative labeling extension process is started is the empty labeling, that associates the same label to all nodes. If the initial labeling is defined by node degrees, then one iteration is enough to obtain a stronger consistency (see[START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF] for more details).

Acknowledgements Many thanks to Yves Deville for enriching discussions, to Jean-Christophe Luquet for having implemented a first version of ILF, to Christophe Lecoutre for guiding me in the use of Abscon, and to anonymous reviewers for their valuable remarks who helped me improving this paper. This work was done in the context of project Sattic ( Anr grant Blanc07-1_184534).


Mark Van De Velde

Dmitry Idiatov

Morphological classes and gender in Ɓəńá-Yungur

Keywords: morphological classes, noun classes, gender, stacking

This paper provides an analysis of the gender system of Ɓəńá-Yungur (glottocode: bena1260), distinguishing noun classes proper, defined as agreement classes, from morphological classes, defined in terms of number marking on nouns. The gender system is typologically unusual in its symmetry and simplicity. Ɓəńá-Yungur has three noun classes in the singular and the same three classes in the plural. All logically possible singular-plural pairings are attested, except one. Morphological classes are much more numerous than noun classes and they show a high degree of singular-plural polarity. We argue that many of the morphological class markers are historically stacked, and therefore that their high number does not reflect a complex proto-system. This is important, because the comparison of noun class systems is used as the main criterion for the genealogical classification of languages currently classified as Adamawa and Gur.

Introduction

This paper analyses nominal classification in the Ɓəńá-Yungur language of Nigeria. The existence of noun classes in the Ɓəńá-Mboi group is known since the pioneering work on these languages by Ulrich [START_REF] Kleinewillinghöfer | Evidence of noun classes in languages of the Yungur (Ɓəńá-Mboi) group[END_REF][START_REF] Kleinewillinghöfer | Nominalklassen im Mboi und Ɓəna-Lala der Yungur bzw. Ɓəna-Mboi-Gruppe[END_REF][START_REF] Kleinewillinghöfer | Die nordwestlichen Adamawa-Sprachen -Eine Übersicht[END_REF], who relies heavily on noun class morphology in his (so far unpublished) efforts to classify the languages of the Gur and Adamawa families. By keeping a strict distinction between noun classes and morphological classes in our synchronic analysis of nominal classification (following [START_REF] Corbett | Gender[END_REF], we show that the gender system is typologically unusual in its simplicity and symmetry. With symmetry we here mean that all singular noun classes also exist in the plural and vice versa. Moreover, the analysis of the rich morphological class system shows that its complexity can be reduced by subgrouping class markers into sets that consist of a basic marker and one or two markers presumably diachronically derived from it by means of stacking. This insight has consequences for the reconstruction of class markers in the Ɓəńá-Mboi group, and hence ultimately for language classification.

Traditionally, specialists of the Niger-Congo languages use four criteria to define noun classes, viz. agreement, class marking on nouns, number distinctions, and membership of singular-plural pairings. In this tradition, two nouns are analysed as belonging to different noun classes if they trigger different agreement patterns, or if they have a different class affix, or if one is a singular noun and the other a plural noun, or if they belong to different singular-plural pairings. These criteria are often implicit and they can be combined in different ways. Among Bantuists, for instance, it is common to distinguish two noun classes in a set of singular nouns that trigger the same agreement pattern, if they have different class affixes and if their plurals belong to different classes (defined along the same lines). The convenience of this approach is that it tracks historical changes in the noun class systems of individual languages, thereby helping to identify cognate class markers across languages of the same family. If two agreement patterns merged, for instance, the classes they defined can still be distinguished by means of other criteria. However, this approach does not always result in the most insightful synchronic analysis of nominal classification in individual Niger-Congo languages, and we think that it is better reserved for comparative studies. We will therefore equate noun classes with agreement classes: sets of nouns that trigger the same agreement pattern. Following a Niger-Congo terminological convention, we will use the term genders for singular-plural pairings of noun classes. Genders correspond to controller genders in [START_REF] Corbett | Gender[END_REF] terminology and noun classes to target genders. Gender is also the term for the grammatical feature. Morphological classes are sets of nouns that have the same class marker, a marker that signals whether the noun has singular or plural number and that gives a more or less reliable indication of the noun class assignment of the noun. Although the link between noun classes and morphological classes is perfectly obvious, there is rarely a one-to-one relation between both.

This paper is based on original data from field work we carried out in Nigeria. We gathered initial data with about ten speakers in the village of Dumne during a pilot study in Adamawa State. Due to the insecurity in the region, we subsequently invited native speaker consultants to come and work with us in Kwara State for longer periods in 2013, 2014 and 2015. Our main consultants are Sabeta Bukta and Bitrus Andrew, two male mother tongue speakers in their early thirties who use Ɓəńá-Yungur on a daily basis. We recorded many texts, including dialogues, which are partly transcribed and translated. However, the data used in this paper are almost entirely elicited. Even if the use of naturalistic data might alter the description at some points, we are confident of the overall validity of our analysis. The scope of the paper is restricted to a basic analysis of nominal classification. The distribution of class markers in the noun phrase and the possible link with construct forms of nouns need further study.

Section 2 provides an introduction to the Ɓəńá-Yungur language. It is followed by a section on the gender system (Section 3), an analysis of the morphological classes (Section 4), a discussion of gender assignment (Section 5) and a concluding discussion with a comparative perspective.

The Ɓəńá-Yungur language

The Ɓəńá-Yungur language is a language from the Ɓəńá-Mboi group traditionally classified as a subgroup of the Adamawa family of Niger-Congo, in which it probably occupies an isolated position according to Kleinewillinghöfer (to appear). The speakers refer to their languages as e ́ː ɓəńā 'mouth/language of Ɓəńá'. The name Yungur is originally an exonym, but today it is regularly used by the Ɓəńá themselves. Since speakers of the Lala varieties of the Ɓəńá-Mboi group identify themselves as Ɓəńá as well, [START_REF] Kleinewillinghöfer | Nominalklassen im Mboi und Ɓəna-Lala der Yungur bzw. Ɓəna-Mboi-Gruppe[END_REF] proposes to use Ɓəńá-Yungur as the name of the language, a convention we will follow.

Ɓəńá-Yungur is spoken in an area north of the Benue river in Adamawa State, Nigeria.

The largest settlement is the town of Dumne, where the use of the Pəŕá dialect is predominant. Our consultants are all Pəŕá speakers from Dumne. Ɓəńá-Yungur is used vigorously in its area, but we have often observed Ɓəńá-Yungur children speaking Hausa. Attitudes towards Ɓəńá-Yungur are positive. According to Bitrus Andrew, speakers recently started using Ɓəńá-Yungur in their encounters with Fulani herdsmen, where previously they used Fula. There is a language committee in place in Ɓəńá country, the Yungur Luke Partnership Project, which created and distributed several editions of a brochure that makes proposals for a spelling and contains some grammar notes. A native speaker, Saul Samuel, studied linguistics and wrote a term paper on modality and aspect in Ɓəńá-Yungur [START_REF] Samuel | Modality and aspect in Yungur grammar[END_REF], and also assisted Bitrus Andrew in successfully learning to use WeSay, a lexicographical tool created by SIL to assist non-linguists in making a dictionary of their language.

In our preliminary analysis Ɓəńá-Yungur has twenty six consonant phonemes: /b, p, d, t, ʧ, g, k, gb, kp, ʔ, ɓ, ɗ, f, z, s, ʃ, h, m, n, ɲ, ŋ, l, ⱱ, r, y, w/. So far, we found the labial-dental flap (/ⱱ/) in one ideophone only. We currently analyse geminates and prenasalised stops as successions of two phonemes. Ɓəńá-Yungur distinguishes six phonological vowel qualities /i, e, a, ə, o, u/. All can be phonologically nasal, with the possible exception of ə. Vowel length is contrastive throughout the vowel system. This brings the vowel inventory to twenty two phonemes. Utterance-initially, vowels are often pre-glottalised and voiced stops partially or fully devoiced, with the exception of /gb/, but including implosives. Optional initial devoicing is especially common with fricatives. Pre-pausal glottalisation is regular with stops and also occurs with continuants, nasals, /l/ and vowels. Consonant lengthening is another important phonetic property associated with the pre-pausal position.

There are three level tones, viz. Low, Mid and High, which can combine into every logically possible contour on any syllable type: LM, LH, ML, MH, HM, and HL. More complex contours, such as HLH, exist as well, but any restrictions on their occurrence are yet to be studied. The lexical distribution of tones is intriguing. In stem initial position, there is a very strong correlation between tone and onset consonant such that the voiced plosives (i.e. /b, d, g, gb/) are almost exclusively followed by a L tone and the majority of other consonants by either M or H. The behaviour of prenasalised stops depends on their place of articulation. Bilabial /mb/ and alveolar /nd/ do not behave as voiced stops. Only three out of 39 are followed by a L tone. Velar /ŋg/, in contrast, is followed by a L in ten out of thirteen cases. The phonemes /s/ and /m/ have an ambiguous behaviour too, but for /s/ comparative data show that it is the result of a merger of *s and *z and that the reflexes of *z are followed by a L and those of *s by H or M. Tonology is fairly straightforward. There are two important tone rules: tone spread and contour simplification. L and M do not behave as distinct tones in the application of these rules. The morphotonology of the language is more complicated. For instance, nouns that are entirely H or entirely L each split into two tone classes when in certain syntactic positions, especially that of dependent in a genitive construction.

Both open and closed syllables are possible. In their citation form, most words end in an open syllable. Final closed syllables are more common in minor word classes, such as adverbs. Utterance-internally, word final vowels are often reduced and in some constructions deleted. When the final vowel is deleted, the result is a word-final closed syllable. The resulting final consonant may be optionally glottalised comparably to the pre-pausal context. Vowel-initial syllables are rare. They are found mostly in function words and borrowings. Consonant clusters are possible across word boundaries and within words, either across syllable boundaries or in syllable onsets, but there are no pre-pausal or phrase-internal word-final consonant clusters in Bəńá-Yungur. Consonant clusters in syllable onsets are of two types. The first one involves a sequence of a homorganic nasal and a voiced stop. The second one involves a sequence of a stop and /w/, /l/ or /r/. In careful speech, some of the clusters of the second type are broken up by a schwa transforming a monosyllabic sequence into a bisyllabic one, as in t(ə)wá 'guinea fowl' with an optional schwa vs. twáːtwá 'wide' where no such option exists. The two cluster types can combine provided the first consonant is a homorganic nasal, as in mb(ə)ra ̃᷄ 'water'.

Bound segmental morphology is mostly suffixing. Modifiers follow the element they modify. Basic clause structure is SVO, although in some TAM constructions first and second person pronominal objects are preposed to the verb. Negative polarity is marked by a clause-final negative marker ré in combination with some negative morphology earlier in the clause. Basic TAM categories, including Perfective, Habitual, Progressive and Future, are marked syncretically on the verb and the subject pronominal. Pronominal agreement targets agree in animacy with their controller, where animacy basically reflects the self-locomotion ability of the referent. Inanimate pronominal targets are mostly realized as absence of an overt pronominal. Non-selective interrogative pronominals make a distinction between human yānā 'who?' and non-human mbīː 'what?'. A clusivity distinction is made in 1PL between inclusive and exclusive 1PL pronominals, both as subjects and non-subjects. Dedicated singular and plural logophoric forms exist for animate subject and possessive pronominals.

Gender in Ɓəńá-Yungur

Ɓəńá-Yungur has gender agreement on nominal modifiers, including demonstratives, indefinite determiners, possessive pronouns, adjectives and participles. Pronominal agreement targets agree in animacy with their controller, not in gender. There are three distinct agreement patterns, which we represent by means of the form of the demonstrative without their M tone diacritic, viz. wa, ya and ɓa. These three agreement patterns are always given in the same order in the following examples of demonstrative (1), possessive (2), adjectival (3) and indefinite determiner (4) targets.

(1) a. fətáː wa᷇ 'this horn' b. ét ya᷇ 'this person' c. án ɓa᷇ 'this place'

(2) a. dòbrə̀ wānō 'my bush' b. rèːké yánē 'my sugar cane' c. ám ɓánā 'my children'

(3) a. páː ʧéɓ-ô 'black sesame' b. ét ʧéɓ-ê 'black person' c. ɓét ʧéɓ-â 'black people'

(4) a. gòː kǒ 'a certain chicken' b. é(t) ké 'somebody (lit. some person)' c. ɓót ká 'a certain tree'

Comparing the demonstrative agreement targets with singular controllers in (1) with those with plural controllers in ( 5), shows that exactly the same agreement patterns are used with singular and plural controllers, a situation that is not attested in any other language that we are aware of.

(5) a. wùmsə̂ wā 'these owls' b. bàŋgē yā 'these palm trees' c. ám ɓa᷇ 'these children'

When we look at singular-plural pairings, we see that every logically possible gender is attested in our data, except ɓa-ɓa. The absence of the latter is no doubt due to the fact that, both in the singular and in the plural, agreement pattern ɓā is rare. In the singular, it is triggered by the nouns ándá 'place' and mbú 'thing', but not by phrasal compounds headed by these nouns, such as mbú kəfā 'food' (lit. 'thing to eat'). In the plural, it is triggered by some terms for human beings. This gender system, summarised in Figure 1, is typologically exceptional in its symmetry and simplicity.

Figure 1: The Ɓəńá-Yungur gender system SG PL wa wa ya ya ɓa ɓa

We will come back to the gender system in Section 5, which discusses gender assignment.

Morphological classes in Ɓəńá-Yungur

Morphological classes are sets of nouns that have the same number marking. Ɓəńá-Yungur has about thirty of them. Most class markers are postposed, but some plural class markers are preposed or circumposed. It is not yet entirely clear whether these markers should be analysed as affixes, clitics or separate words. They are probably not a homogeneous group in terms of their degree of morphological bonding. For the time being, we represent them all as affixes. We provide class markers without tone marking, because their underlying tone is not always clear yet and often partly or fully lexically determined. The tone of the markers -ra, -ta and -o, for instance, is usually H if the last syllable of the noun stem is H and M if the last stem syllable is M. When the last stem tone is L, nothing can be predicted about the tone of these class markers.

Table 1 provides an overview of the morphological classes, arranged in columns according to their type of coding, viz. singular and plural coded, only plural coded and no coding. Some classes, presented between brackets, contain less than three nouns in our current lexical database. The table is not fully exhaustive, but all major classes are represented. -o / -a -ra / -ta suppletion When determining the morphological class of a word, we take a strictly synchronic approach, recognising a class marker only when it commutes with another one. The final -a and -o of the singular nouns in (6) are analysed as class markers, because they commute with -e and -sa in the plurals in (7). The final a and o of the singular nouns in (8) may undergo some morphonological alternations, but they do not commute (9) and are analysed as part of the stem.

(6) a. sàb-ā 'tamarind tree' b. dìk-ō 'game' (7) a. sàb-ē 'tamarind trees' b. dìk-sâ 'games' (8) a. pīrā 'walking stick' b. sóktó 'sieve' (9) a. pīrā-ːmē 'walking sticks' b. sóktə-sâ 'sieves' Consequently, we also do not analyse the final ma in the mass nouns in (10) as a class marker, although there is no doubt that it is the reflex of one. In other Ɓəńá-Mboi languages, for instance, nouns ending in ma trigger a specific agreement pattern (demonstrative ma). The formal and functional resemblance with the Bantu class 6 prefix mais also obvious.

(10) dùːmà 'salt' hwa ̄ːmā 'paste' mēːmā 'milk' mūtmā 'blood' sómmâ 'urine' bàːmà 'chaff'

Now that it is clear how the zeroes in Table 1 should be interpreted, we will first discuss the morphological classes of the second and third column, and then turn to those presented in the first column. Most of the plural markers used with nouns that have an unmarked singular (column 2), can also be found in the plural of nouns with a marked singular (column 1). The two exceptions are -mse and yòː-. The latter of these two is not attested in the other Ɓəńá-Mboi languages and often marks the plural of borrowings ( 11).

(11) yòː-bwàtəŕè 'white people, Europeans' ( < Hausa) yòː-dàŋkálē 'sweet potatoes' ( < Hausa) yòː-máŋgòrò 'mangoes' yòː-gwéːvà 'guavas'

Turning to the third column of Table 1, more than thirty percent of nouns have no number marking. In a few of these cases, our consultants state that the form of the singular noun is identical to that of the plural (12). Some of these nouns are used to refer to staple foods and could be thought to be mass/uncount on semantic grounds. However, they can be the object of pluractional verbs (13b), showing that they can be plural, and therefore count, and that number is simply not coded on them. In this respect, compare ( 14) where dwàlò 'ritual whip' is clearly count and equally has no number marking.

(12) a. se ̀ːkē 'flute/s (sp.)' b. ȭː 'field/s (sp.)' (13) a. tóː dásè 'Take a bean / a quantity of beans.' b. hāː dàsè 'Take.PLURAC (several individual) beans.' ( 14) a. tóː dwálò 'Take a ritual whip.' b. hāː dwàlò 'Take.PLURAC ritual whips.'

Interestingly, for the majority of nouns that lack a class marker in the singular, our fluent native speaker consultants say that they do not know or have never heard the plural. This is all the more surprising, since the yòːplural, used with many borrowings, could be expected to act as a default plural marker. At the same time, our consultants normally accept using such uncoded nouns with pluractional verbs.

Figure 2 shows the data from the first column of Table 1 in the type of chart traditionally used for representing Niger-Congo noun class systems. Full lines represent common SG-PL pairings and dotted lines exceptional pairings. The width of the full lines is proportional to the number of nouns that belong to the class pairing. Note that the number of morphological class markers in the plural is twice as high as in the singular, which is typologically rather unusual (but perfectly explainable, see below). A comparison of Figure 2 to Figure 1 suggests that the system of morphological classes is structurally very different from the gender system, and much more complex. This may lead comparativists to the hypothesis that the morphological class system is the reflex of a rich noun class system in a proto stage of the language, the breakdown of which is more advanced in the agreement patterns than in the nominal class markers However, the morphological class system of Ɓəńá-Yungur shows parallels with its simple and symmetrical gender system, and some further analysis can reduce its complexity. An obvious parallelism with the gender system is that two morphological class markers, -a and -e, are used with singular nouns as well as with plural nouns. Note also that all plural markers end in a or e. Ignoring the markers -ra and -ta, and the words for 'place' and 'thing', 1 all nouns that take the singular marker -a have a plural marker that ends in e and all nouns that have -e or -o in the singular end in a in the plural. 2 Thus, -se and -me are like -e in marking the plural of nouns with a singular in -a. Likewise, -sa and -ma form a sub-paradigm with -a. An alternative hypothesis to assuming that the morphological class markers are reflexes of numerous proto-forms, is therefore that many of them are historically stacked forms. The plural marker -mse which occurs with nouns that lack marking in the singular, appears to be doubly stacked: -m-s-e. The hypothesis of historical stacking in the class markers -ma, -me, -sa, -se and -mse is strengthened by a number of clear cases of synchronic stacking in plural marking (15), and in denominal derivation (16-17).

(15) hṍː-rá 'tick' / hṍː-tə-sâ 'ticks' (16) ta ̄ː-rā / ta ̄ː-tā 'blind person/s'  ta ̄ː-tə-sô 'blindness' (17) a. bàt-ā / bàʧ-ē 'baobab tree/s'  bàt-ə-rá / bàt-ə-tá 'baobab fruit/s' b. kūml-á / kūml-é 'tree/s (sp)'  kūml-āː-rá / kūml-āː-tá 'kumla fruit/s' Likewise, the many nouns that end in a non-commuting o or a in the singular, are likely to have historically stacked suffixes (SG + PL) in their plural form too, see the examples in (8-9). Finally, multiple marking of plural number is not restricted to stacked suffixes. Many nouns with a plural suffix -a also have a plural prefix ám M -. Although this preposed plural marker is most probably grammaticalised from ámbá 'children', it often occurs on nouns that are not used to refer to animate beings.

(18) a. bàmlè / ám bàmlà 'donkey/s' b. bwàdē / ám bwàdā 'calabash/es (sp)' c. pwéː / ám pwã᷄ ː 'knife/knives'

The assignment of nouns to morphological classes shows some semantic regularities, but for the majority of nouns, we did not find a clear semantic motivation for their class assignment.

The clearest case of semantic assignment are the names of trees, which have SG -a and PL -e, with very few exceptions. Conversely, the -a /-e class pairing is almost entirely dedicated to names for trees. The two exceptions in our lexical database are nouns with human reference: yámá 'Libo person' and dəẁà 'singer (sp)', but for the latter our consultants have doubts on which of the two forms, dəẁà or dəẁè, is singular and which is plural. Names of fruits are usually derived from the tree name by suffixing -ra (PL -ta). About thirty percent of the nouns that are used to refer to human beings have the suffix -e in the singular and, consequently, a suffix that ends in a in the plural, sometimes with a ɓprefix in the plural and/or some degree of suppletion in the stem. The nouns for animals for which our consultants gave a plural form are mostly -o/-sa, -ra/-ta or /-sa.

Gender assignment

When we elicit information on the gender assignment of nouns, we are faced with variation and hesitations that remind of the difficulties that otherwise fluent speakers have to give the plural form of many nouns. This variation suggests that the gender assignment of nouns is unstable in the language, in that different systems coexist in the speech community. This does not necessarily mean that the gender system is on its way of being lost. Agreement targets HAVE TO agree, and only some speakers generalise one agreement pattern to the detriment of the others.

A first distinction must be made between the ɓa-pattern and the two others, viz. wa and ya. Few nouns trigger the ɓa-pattern, but the nouns that do are rather frequent. In the singular these are the nouns ándá 'place', gǎː 'sun' and ɓótá 'tree'. Agreement within phrasal compounds headed by mbú 'thing', such as mbú kəfā 'food' and mbú tómā 'thing to do', also follows the ɓapattern, but these compounds do not themselves trigger the ɓaagreement. In the plural, the ɓa-class contains nouns that are used to refer to human beings, as well as the noun ri ́a ́ 'foxes.'

Although not all nouns with human reference trigger the ɓa-class in the plural, assignment to the ɓa-class in the plural is clearly semantically motivated, as can be observed in polysemous words such as ka ́ːmá (19). 3 All nouns that trigger ɓa-agreement, whether in the singular or the plural, can alternatively trigger wa-agreement.

(19) a. ka ́ːmə́ wa᷇ 'these seeds' b. ka ́ːmə́ ɓa᷇ 'these paternal consanguinal relatives'

Assignment to the waand ya-classes is not semantically motivated. Here, different speakers have different rules of assignment. Two of our main consultants have a formal assignment rule based on the last segment of the noun, irrespective of whether this belongs to the stem or to a morphological class marker. Words that end in a or o tend to trigger the wa-pattern, all other words the ya-pattern. Another consultant tends to generalise the wa-pattern to all nouns in elicitation, the most noticeable exception being frequent singular nouns that end in e. For less common singular nouns that end in e, the ya-pattern is always accepted, but not necessarily provided spontaneously. This speaker also has the ɓa-gender with wa as an alternative gender assignment. The gender system shown in Figure 1 is therefore valid for all speakers, but speakers differ in the way they assign nouns to genders.

We saw that Ɓəńá-Yungur has only three noun classeseach of which can contain singular and plural nounsbut eight genders and up to thirty morphological classes. The scenario that is most appealing to specialists of the Niger-Congo languages in such a situation is one in which a historically complex noun class system has been simplified, in this case starting with the agreement patterns. Simplified noun class systems, i.e. simpler systems that can be shown to have evolved from more complex systems, are very widely attested in many branches of Niger Congo [START_REF] Good | How to become a "Kwa" noun[END_REF]). In the case of Ɓəńá-Yungur, however, the complexity of the morphological class system is more likely to be an innovation, brought about by the creation of new class markers and the stacking of existing ones.

The closest relatives of Ɓəńá-Yungur have similar systems of nominal classification, but with slightly more noun classes. [START_REF] Kleinewillinghöfer | Evidence of noun classes in languages of the Yungur (Ɓəńá-Mboi) group[END_REF] signals five paradigms of agreement markers in Mboi of Livo (wa, ya, ta, ma, za), six in Mboi of Gulungo (wa, ya, ra, ta, ma, za), and seven in Ɓəńá-Laala of Yang (wa, ya, ɓa, ra, ta, ma, za). The gender systems of these Ɓəńá-Mboi languages are summarised in figures 4-6. These languages all have a core of classes that occur both in the singular and in the plural, corresponding to the classes found in Ɓəńá-Yungur. Interestingly, the singular-plural pairings in these core noun classes show some of the polarity that can be found in the Ɓəńá-Yungur morphological classes. This is especially clear in Mboi of Gulungo, where the genders wa/ya and ya/wa are attested, but not wa/wa and ya/ya. The classes that do not exist in Ɓəńá-Yungur, viz. ra, ta, za and ma, are restricted to either singular or plural controllers in the other languages. Some gaps in the figures may be due to incomplete documentation, since [START_REF] Kleinewillinghöfer | Evidence of noun classes in languages of the Yungur (Ɓəńá-Mboi) group[END_REF] is based on survey work. We hope to have shown that the typologically unusual aspects of nominal classification in Ɓəńá-Yungur can only be appreciated if we follow the practice of distinguishing between noun classes (or target genders) and genders (or controller genders) on the one hand and between noun classes and morphological classes on the other. The rich set of morphological class markers is an innovation in the Ɓəńá-Mboi languages, created mostly through stacking, which should be kept in mind in the search for cognates among class markers in the Adamawa and Gur languages. Notes 1 The words for 'place' ándá and 'thing' mbú are also the two nouns that make up agreement pattern ɓa in the singular. They are both marked -sa in the plural: án-sâ 'places' and mbú-sâ 'things '. 2 This is reminiscent of the phenomenon often called gender polarity in Afro-Asiatic languages such as Somali, which, at least in Somali, could better be called morphological class polarity.

Figure 2 :

 2 Figure 2: Morphological class markers (of nouns marked in the SG and the PL) SG PL

Figure

  Figure 3: Morphological class markers (simplified) SG PL

Figure

  Figure 4: The Laala Yang gender system SG PL wa --

Table 1 :

 1 The morphological classes of Ɓəńá

	SG / PL -a / -e (-a / -me) (-a / -sa) (-a / -se) -e / -a -e / am-… -a -e / -ma (y-)…-e / ɓ--a -e / -sa (-e / -ta) -o / -sa (-o / am M -…-a) (-o / -ta)	∅ / PL (∅ / -a) (∅ / am-) (∅ / -ma) ∅ / -me ∅ / -mse ∅ / yòː-(∅ / -se) ∅ / -sa ∅ / -ta	∅ SG = PL no PL

3 This reminds of the relation between nouns with human reference and gender 1/2 in most Bantu languages: all nouns that belong to this gender have human reference, but not all nouns for humans are found in that gender.