L Ászl

Ó Egri

Andrei Krokhin
email: andrei.krokhin@durham.ac.uk

Benoit Larose
email: larose@mathstat.concordia.ca

Pascal Tesson
email: pascal.tesson@ift.ulaval.ca

L Egri

THE COMPLEXITY OF THE LIST HOMOMORPHISM PROBLEM FOR GRAPHS

Keywords: graph homomorphism, constraint satisfaction problem, complexity, universal algebra, Datalog

We completely classify the computational complexity of the list H-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph H the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems.

Introduction

Homomorphisms of graphs, i.e. edge-preserving mappings, generalise graph colourings, and can model a wide variety of combinatorial problems dealing with mappings and assignments [START_REF] Hell | Graphs and Homomorphisms[END_REF]. Because of the richness of the homomorphism framework, many computational aspects of graph homomorphisms have recently become the focus of much attention. In the list H-colouring problem (for a fixed graph H), one is given a graph G and a list L v of vertices of H for each vertex v in G, and the goal is to determine whether there is a homomorphism h from G to H such that h(v) ∈ L v for all v. The complexity of such problems has been studied by combinatorial methods, e.g., in [START_REF] Feder | List homomorphisms and circular arc graphs[END_REF][START_REF] Feder | Bi-arc graphs and the complexity of list homomorphisms[END_REF]. In this paper, we study the complexity of the list homomorphism problem for graphs in the wider context of classifying the complexity of constraint satisfaction problems (CSP), see [START_REF] Barto | The CSP dichotomy holds for digraphs with no sources and no sinks (A positive answer to a conjecture of Bang-Jensen and Hell)[END_REF][START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory[END_REF][START_REF] Hell | Colouring, constraint satisfaction, and complexity[END_REF]. It is well known that the CSP can be viewed as the problem of deciding whether there exists a homomorphism from a relational structure to another, thus naturally extending the graph homomorphism problem.

One line of CSP research studies the non-uniform CSP, in which the target (or template) structure T is fixed and the question is whether there exists a homomorphism from an input structure to T. Over the last years, much work has been done on classifying the complexity of this problem, denoted Hom(T) or CSP(T), with respect to the fixed target structure, see surveys [START_REF] Bulatov | Dualities for constraint satisfaction problems[END_REF][START_REF] Bulatov | Recent results on the algebraic approach to the CSP[END_REF][START_REF] Cohen | The complexity of constraint languages[END_REF][START_REF] Hell | Colouring, constraint satisfaction, and complexity[END_REF]. Classification here is understood with respect to both computational complexity (i.e. membership in a given complexity class such as P, NL, or L, modulo standard assumptions) and descriptive complexity (i.e. definability of the class of all positive, or all negative, instances in a given logic).

The best-known classification results in this direction concern the distinction between polynomial-time solvable and NP-complete CSPs. For example, a classical result of Hell and Nešetřil (see [START_REF] Hell | Graphs and Homomorphisms[END_REF][START_REF] Hell | Colouring, constraint satisfaction, and complexity[END_REF]) shows that, for a graph H, Hom(H) (aka H-colouring) is tractable if H is bipartite or admits a loop, and is NP-complete otherwise, while Schaefer's dichotomy [START_REF] Schaefer | The complexity of satisfiability problems[END_REF] proves that any Boolean CSP is either in P or NP-complete. Recent work [START_REF] Allender | The complexity of satisfiability problems: Refining Schaefer's theorem[END_REF] established a more precise classification in the Boolean case: if T is a structure on {0, 1} then CSP(T) is either NP-complete, P-complete, NL-complete, ⊕L-complete, L-complete or in AC 0 .

Much of the work concerning the descriptive complexity of CSPs is centred around the database-inspired logic programming language Datalog and its fragments (see [START_REF] Bulatov | Dualities for constraint satisfaction problems[END_REF][START_REF] Dalmau | Linear Datalog and bounded path duality for relational structures[END_REF][START_REF] Egri | Symmetric Datalog and constraint satisfaction problems in Logspace[END_REF][START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory[END_REF][START_REF] Ph | A logical approach to constraint satisfaction[END_REF]). Feder and Vardi initially showed [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory[END_REF] that a number of important tractable cases of CSP(T) correspond to structures for which ¬ CSP(T) (the complement of CSP(T)) is definable in Datalog. Similar ties were uncovered more recently between the two fragments of Datalog known as linear and symmetric Datalog and structures T for which CSP(T) belongs to NL and L, respectively [START_REF] Dalmau | Linear Datalog and bounded path duality for relational structures[END_REF][START_REF] Egri | Symmetric Datalog and constraint satisfaction problems in Logspace[END_REF].

Algebra, logic and combinatorics provide three angles of attack which have fueled progress in this classification effort [START_REF] Bulatov | Dualities for constraint satisfaction problems[END_REF][START_REF] Bulatov | Recent results on the algebraic approach to the CSP[END_REF][START_REF] Cohen | The complexity of constraint languages[END_REF][START_REF] Hell | Graphs and Homomorphisms[END_REF][START_REF] Hell | Colouring, constraint satisfaction, and complexity[END_REF][START_REF] Ph | A logical approach to constraint satisfaction[END_REF]. The algebraic approach (see [START_REF] Bulatov | Recent results on the algebraic approach to the CSP[END_REF][START_REF] Cohen | The complexity of constraint languages[END_REF]) links the complexity of CSP(T) to the set of functions that preserve the relations in T.

In this framework, one associates to each T an algebra A T and exploits the fact that the properties of A T completely determine the complexity of CSP(T). This angle of attack was crucial in establishing key results in the field (see, for example, [START_REF] Barto | Constraint satisfaction probllems of bounded width[END_REF][START_REF] Bulatov | Tractable conservative constraint satisfaction problems[END_REF][START_REF] Bulatov | Recent results on the algebraic approach to the CSP[END_REF]).

Tame Congruence Theory, a deep universal-algebraic framework first developed by Hobby and McKenzie in the mid 80's [START_REF] Hobby | The Structure of Finite Algebras[END_REF], classifies the local behaviour of finite algebras into five types (unary, affine, Boolean, lattice and semilattice.) It was recently shown (see [START_REF] Bulatov | Dualities for constraint satisfaction problems[END_REF][START_REF] Bulatov | Recent results on the algebraic approach to the CSP[END_REF][START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF]) that there is a strong connection between the computational and descriptive complexity of CSP(T) and the set of types that appear in A T and its subalgebras. There are strong conditions involving types which are sufficient for NL-hardness, P-hardness and NPhardness of CSP(T) as well as for inexpressibility of ¬ CSP(T) in Datalog, linear Datalog and symmetric Datalog. These sufficient conditions are also suspected (and in some cases proved) to be necessary, under natural complexity-theoretic assumptions. For example, (a) the presence of unary type is known to imply NP-completeness, while its absence is conjectured to imply tractability (see [START_REF] Bulatov | Recent results on the algebraic approach to the CSP[END_REF]); (b) the absence of unary and affine types was recently proved to be equivalent to definability in Datalog [START_REF] Barto | Constraint satisfaction probllems of bounded width[END_REF]; (c) the absence of unary, affine, and semilattice types is proved necessary, and suspected to be sufficient, for membership in NL and definability in linear Datalog [START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF]; (d) the absence of all types but Boolean is proved necessary, and suspected to be sufficient, for membership in L and definability in symmetric Datalog [START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF]. The strength of evidence varies from case to case and, in particular, the conjectured algebraic conditions concerning CSPs in NL and L (and, as mentioned above, linear and symmetric Datalog) still rest on relatively limited evidence [START_REF] Bulatov | Dualities for constraint satisfaction problems[END_REF][START_REF] Dalmau | Linear Datalog and bounded path duality for relational structures[END_REF][START_REF] Dalmau | Maltsev + Datalog ⇒ Symmetric Datalog[END_REF][START_REF] Dalmau | Majority constraints have bounded pathwidth duality[END_REF][START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF].

The aim of the present paper is to show that these algebraic conditions are indeed sufficient and necessary in the special case of list H-colouring for undirected graphs (with possible loops), and to characterise, in this special case, the dividing lines in graph-theoretic terms (both via forbidden subgraphs and through an inductive definition). One can view the list H-colouring problem as a CSP where the template is the structure H L consisting of the binary (edge) relation of H and all unary relations on H (i.e. every subset of H). Tractable list homomorphism problems for general structures were characterised in [START_REF] Bulatov | Tractable conservative constraint satisfaction problems[END_REF] in algebraic terms. The tractable cases for graphs were described in [START_REF] Feder | Bi-arc graphs and the complexity of list homomorphisms[END_REF] in both combinatorial and (more specific) algebraic terms; the latter implies, when combined with a recent result [START_REF] Dalmau | Majority constraints have bounded pathwidth duality[END_REF], that in these cases ¬ CSP(H L ) definable in linear Datalog and therefore CSP(H L ) is in fact in NL. We complete the picture by refining this classification and showing that CSP(H L ) is either NP-complete, or NL-complete, or L-complete or in AC 0 (and in fact first-order definable). We also remark that the problem of recognising into which case the problem CSP(H L ) falls can be solved in polynomial time.

As we mentioned above, the distinction between NP-complete cases and those in NL follows from earlier work [START_REF] Feder | Bi-arc graphs and the complexity of list homomorphisms[END_REF], and the situation is similar with distinction between L-hard cases and those leading to membership in AC 0 [START_REF] Larose | A characterisation of first-order constraint satisfaction problems[END_REF][START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF]. Therefore, the main body of technical work in the paper concerns the distinction between NL-hardness and membership in L. We give two equivalent characterisations of the class of graphs H such that CSP(H L ) is in L. One characterisation is via forbidden subgraphs (for example, the reflexive graphs in this class are exactly the (P 4 , C 4 )-free graphs, while the irreflexive ones are exactly the bipartite (P 6 , C 6 )-free graphs), while the other is via an inductive definition. The first characterisation is used to show that graphs outside of this class give rise to NL-hard problems; we do this by providing constructions witnessing the presence of a non-Boolean type in the algebras associated with the graphs. The second characterisation is used to prove positive results. We first provide operations in the associated algebra which satisfy certain identities; this allows us to show that the necessary condition on types is also sufficient in our case. We also use the inductive definition to demonstrate that the class of negative instances of the corresponding CSP is definable in symmetric Datalog, which implies membership of the CSP in L.

Preliminaries

Graphs and relational structures

In the following we denote the underlying universe of a structure S, T, ... by its roman equivalent S, T , etc. A signature is a (finite) set of relation symbols with associated arities. Let T be a structure of signature τ ; for each relation symbol R ∈ τ we denote the corresponding relation of T by R(T). Let S be a structure of the same signature. A homomorphism from S to T is a map f from S to T such that f (R(S)) ⊆ R(T) for each R ∈ τ . In this case we write f : S → T. A structure T is called a core if every homomorphism from T to itself is a permutation on T . We denote by CSP(T) the class of all τ -structures S that admit a homomorphism to T, and by ¬ CSP(T) the complement of this class.

The direct n-th power of a τ -structure T, denoted T n , is defined to have universe T n and, for any (say m-ary) R ∈ τ , (a 1 , . . . , a m ) ∈ R(T n ) if and only if (a

1 [i], . . . , a m [i]) ∈ R(T)
for each 1 ≤ i ≤ n. For a subset I ⊆ T , the substructure induced by I on T is the structure I with universe I and such that R(I) = R(T) ∩ I m for every m-ary R ∈ τ .

For the purposes of this paper, a graph is a relational structure H = H; θ where θ is a symmetric binary relation on H. The graph H is reflexive (irreflexive) if (x, x) ∈ θ ((x, x) ∈ θ) for all x ∈ H. Given a graph H, let S 1 , . . . , S k denote all subsets of H; let H L be the relational structure obtained from H by adding all the S i as unary relations; more precisely, let τ be the signature that consists of one binary relational symbol θ and unary symbols R i , i = 1, . . . , k. The τ -structure H L has universe H, θ(H L ) is the edge relation of H, and R i (H L ) = S i for all i = 1, . . . , k. It is easy to see that H L is a core. We call CSP(H L ) the list homomorphism problem for H. Note that if G is an instance of this problem then θ(G) can be considered as a digraph, but the directions of the arcs are unimportant because H is undirected. Also, if an element v ∈ G is in R i (G) then this is equivalent to v having S i as its list, so G can be thought of as a digraph with H-lists.

In [START_REF] Feder | Bi-arc graphs and the complexity of list homomorphisms[END_REF], a dichotomy result was proved, identifying bi-arc graphs as those whose list homomorphism problem is tractable, and others as giving rise to NP-complete problems. Let C be a circle with two specified points p and q. A bi-arc is a pair of arcs (N, S) such that N contains p but not q and S contains q but not p. A graph H is a bi-arc graph if there is a family of bi-arcs {(N x , S x ) : x ∈ H} such that, for every x, y ∈ H, the following hold: (i) if x and y are adjacent, then neither N x intersects S y nor N y intersects S x , and (ii) if x is not adjacent to y then both N x intersects S y and N y intersects S x .

Algebra

An n-ary operation on a set A is a map f :

A n → A, a projection is an operation of the form e i n (x 1 , . . . , x n ) = x i for some 1 ≤ i ≤ n.
Given an h-ary relation θ and an n-ary operation f on the same set A, we say that f preserves θ or that θ is invariant under f if the following holds: given any matrix M of size h × n whose columns are in θ, applying f to the rows of M will produce an h-tuple in θ.

A polymorphism of a structure T is an operation f that preserves each relation in T; in this case we also say that T admits f . In other words, an n-ary polymorphism of T is simply a homomorphism from T n to T. With any structure T, one associates an algebra A T whose universe is T and whose operations are all polymorphisms of T. Given a graph H, we let H denote the algebra associated with H L . An operation on a set is called conservative if it preserves all subsets of the set (as unary relations). So, the operations of H are the conservative polymorphisms of H. Polymorphisms can provide a convenient language when defining classes of graphs. For example, it was shown in [START_REF] Brewster | Near-unanimity functions and varieties of reflexive graphs[END_REF] that a graph is a bi-arc graph if and only if it admits a conservative majority operation where a majority operation is a ternary operation m satisfying the identities m(x, x, y) = m(x, y, x) = m(y, x, x) = x.

In order to state some of our results, we will need the notions of a variety and a term operation. Let I be a signature, i.e. a set of operation symbols f each of a fixed arity (we use the term "signature" for both structures and algebras, this will cause no confusion). An algebra of signature I is a pair A = A; F where A is a non-empty set (the universe of A) and F = {f A : f ∈ I} is the set of basic operations (for each f ∈ I, f A is an operation on A of the corresponding arity). The term operations of A are the operations built from the operations in F and projections by using composition. An algebra all of whose (basic or term) operations are conservative is called a conservative algebra. A class of similar algebras (i.e. algebras with the same signature) which is closed under formation of homomorphic images, subalgebras and direct products is called a variety. The variety generated by an algebra A is denoted by V(A), and is the smallest variety containing A, i.e. the class of all homomorphic images of subalgebras of powers of A.

Tame Congruence Theory, as developed in [START_REF] Hobby | The Structure of Finite Algebras[END_REF], is a powerful tool for the analysis of finite algebras. Every finite algebra has a typeset, which describes (in a certain specified sense) the local behaviour of the algebra. It contains one or more of the following 5 types:

(1) the unary type, (2) the affine type, (3) the Boolean type, (4) the lattice type and ( 5) the semilattice type. The numbering of the types is fixed, and they are often referred to by their numbers. Simple algebras, i.e. algebras without non-trivial proper homomorphic images, admit a unique type; the prototypical examples are: any 2-element algebra whose basic operations are all unary has type 1. A finite vector space has type 2. The 2-element Boolean algebra has type 3. The 2-element lattice is the 2-element algebra with two binary operations {0, 1}; ∨, ∧ : it has type 4. The 2-element semilattices are the 2-element algebras with a single binary operation {0, 1}; ∧ and {0, 1}; ∨ : they have type 5. The typeset of a variety V, denoted typ(V), is simply the union of typesets of the algebras in it. We will be mostly interested in type-omitting conditions for varieties of the form V(A T ), and Corollary 3.2 of [START_REF] Valeriote | A subalgebra intersection property for congruence-distributive varieties[END_REF] says that in this case it is enough to consider the typesets of A T and its subalgebras.

On the intuitive level, if T is a core structure then the typeset typ(V(A T )) contains crucial information about the kind of relations that T can or cannot simulate, thus implying lower/upper bounds on the complexity of CSP(T). For our purposes here, it will not be necessary to delve further into the technical aspects of types and typesets. We only note that there is a very tight connection between the kind of equations that are satisfied by the algebras in a variety and the types that are admitted or omitted by a variety, i.e. those types that do or do not appear in the typesets of algebras in the variety [START_REF] Hobby | The Structure of Finite Algebras[END_REF].

In this paper, we use ternary operations f 1 , . . . , f n satisfying the following identities:

x = f 1 (x, y, y) (2.1) f i (x, x, y) = f i+1 (x, y, y) for all i = 1, . . . n -1 (2.2) f n (x, x, y) = y.
(2.

3)

The following lemma contains some type-omitting results that we use in this paper. We remark in passing that operations satisfying identities (2.1)-(2.3) are also known to characterise a certain algebraic (congruence) condition called (n + 1)-permutability [START_REF] Hobby | The Structure of Finite Algebras[END_REF].

Datalog

Datalog is a query and rule language for deductive databases (see [START_REF] Ph | A logical approach to constraint satisfaction[END_REF]). A Datalog program D over a (relational) signature τ is a finite set of rules of the form h ← b 1 ∧ . . . ∧ b m where h and each b i are atomic formulas R j (v 1 , ..., v k ). We say that h is the head of the rule and that b 1 ∧ . . . ∧ b m is its body. Relational predicates R j which appear in the head of some rule of D are called intensional database predicates (IDBs) and are not part of the signature τ . All other relational predicates are called extensional database predicates (EDBs) and are in τ . So, a Datalog program is a recursive specification of IDBs (from EDBs).

A rule of D is linear if its body contains at most one IDB and is non-recursive if its body contains only EDBs. A linear but recursive rule is of the form I 1 (x) ← I 2 (ȳ) ∧ E 1 (z 1 ) ∧ . . . ∧ E k (z k ) where I 1 , I 2 are IDBs and the E i are EDBs (note that the variables occurring in x, ȳ, zi are not necessarily distinct). Each such rule has a symmetric I 2 (ȳ) ← I 1 (x) ∧ E 1 (z 1 ) ∧ . . . ∧ E k (z k ). A Datalog program is non-recursive if all its rules are nonrecursive, linear if all its rules are linear and symmetric if it is linear and if the symmetric of each recursive rule of D is also a rule of D.

A Datalog program D takes a τ -structure A as input and returns a structure D(A) over the signature τ ′ = τ ∪ {I : I is an IDB in D}. The relations corresponding to τ are the same as in A, while the new relations are recursively computed by D , with semantics naturally obtained via least fixed-point of monotone operators. We also want to view a Datalog program as being able to accept or reject an input τ -structure and this is achieved by choosing one of the IDBs of D as the goal predicate: the τ -structure A is accepted by D if the goal predicate is non-empty in D(A). Thus every Datalog program with a goal predicate defines a class of structures -those that are accepted by the program.

When using Datalog to study CSP(T), one usually speaks of the definability of ¬ CSP(T) in Datalog (i.e. by a Datalog program) or its fragments (because any class definable in Datalog must be closed under extension). Examples of CSPs definable in Datalog and its fragments can be found, e.g., in [START_REF] Bulatov | Dualities for constraint satisfaction problems[END_REF][START_REF] Egri | Symmetric Datalog and constraint satisfaction problems in Logspace[END_REF]. As we mentioned before, any problem CSP(T) is tractable if its complement is definable in Datalog, and all such structures were recently identified in [START_REF] Barto | Constraint satisfaction probllems of bounded width[END_REF]. Definability of ¬ CSP(T) in linear (symmetric) Datalog implies that CSP(T) belongs to NL and L, respectively [START_REF] Dalmau | Linear Datalog and bounded path duality for relational structures[END_REF][START_REF] Egri | Symmetric Datalog and constraint satisfaction problems in Logspace[END_REF]. As we discussed in Section 1, there is a connection between definability of CSPs in Datalog (and its fragments) and the presence/absence of types in the corresponding algebra (or variety).

Note that it follows from Lemma 2.1 and from the results in [START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF][START_REF] Zádori | Bounded width problems and algebras[END_REF] that if, for a core structure T, ¬ CSP(T) is definable in symmetric Datalog then T must admit, for some n, operations satisfying identities (2.1)-(2.3). Moreover, with the result of [START_REF] Barto | Constraint satisfaction probllems of bounded width[END_REF], a conjecture from [START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF] can be restated as follows: for a core structure T, if ¬ CSP(T) is definable in Datalog and, for some n, T admits operations satisfying (2.1)-(2.3), then ¬ CSP(T) is definable in symmetric Datalog. This conjecture is proved in [START_REF] Dalmau | Maltsev + Datalog ⇒ Symmetric Datalog[END_REF] for n = 1.

A class of graphs

In this section, we give combinatorial characterisations of a class of graphs whose list homomorphism problem will turn out to belong to L.

Let H 1 and H 2 be bipartite irreflexive graphs, with colour classes B 1 , T 1 and B 2 and T 2 respectively, with T 1 and B 2 non-empty. We define the special sum H 1 ⊙H 2 (which depends on the choice of the B i and T i ) as follows: it is the graph obtained from the disjoint union of H 1 and H 2 by adding all possible edges between the vertices in T 1 and B 2 . Notice that we can often decompose a bipartite graph in several ways, and even choose B 1 or T 2 to be empty. We say that an irreflexive graph H is a special sum or expressed as a special sum if there exist two bipartite graphs and a choice of colour classes on each such that H is isomorphic to the special sum of these two graphs. The following result gives a characterisation of basic irreflexive graphs in terms of forbidden subgraphs: Lemma 3.2. Let H be an irreflexive graph. Then the following conditions are equivalent:

(1) H is basic irreflexive;

(2) H is bipartite, contains no induced 6-cycle, nor any induced path of length 5.

We shall now describe our main family of graphs, first by forbidden induced subgraphs, and then in an inductive manner. Definition 3.3. Define the class L of graphs as follows: a graph H belongs to L if it contains none of the following as an induced subgraph:

(1) the reflexive path of length 3 and the reflexive 4-cycle;

(2) the irreflexive cycles of length 3, 5 and 6, and the irreflexive path of length 5;

(3) B1, B2, B3, B4, B5 and B6 (see Figure 1.)

We will now characterise the class L in an inductive manner. (2) D is closed under disjoint union;

(3) if H 1 is a single loop and H 2 ∈ D then H 1 ⊘ H 2 ∈ D.
Lemma 3.6 states that the reflexive graphs avoiding the path of length 3 and the 4cycle are precisely those constructed from the one-element loop using disjoint union and adjunction of a universal vertex. These graphs can also be described by the following property: every connected induced subgraph of size at most 4 has a universal vertex. These graphs have been studied previously as those with NLCT width 1, which were proved to be exactly the trivially perfect graphs [START_REF] Gurski | Characterizations of co-graphs defined by restricted NLC-width or clique-width operations[END_REF]. Our result provides an alternative proof of the equivalence of these conditions. Theorem 3.7. The class L is the smallest class C of graphs such that:

(1) C contains the basic graphs;

(2) C is closed under disjoint union;

(3) if H 1 is a basic graph and H 2 ∈ C then H 1 ⊘ H 2 ∈ C.
Proof. We start by showing that every basic graph is in L, i.e. that a basic graph does not contain any of the forbidden graphs. If H is a single loop or a basic irreflexive graph, then this is immediate. Otherwise H is obtained from a basic irreflexive graph H 1 with colour classes B and T by adding every edge of the form (t 1 , t 2 ) where t i ∈ T . In particular, the loops form a clique and no edge connects two non-loops; it is clear in that case that H contains none of B1, B2, B3, B4. On the other hand if H contains B5 or B6, then H 1 contains the path of length 5 or the 6-cycle, contradicting the fact that H 1 is basic.

Next we show that L is closed under disjoint union and adjunction of basic graphs. It is obvious that the disjoint union of graphs that avoid the forbidden graphs will also avoid these. So suppose that an adjunction H 1 ⊘ H 2 , where H 1 is a basic graph, contains an induced forbidden graph B whose vertices are neither all in H 1 nor H 2 ; without loss of generality H 1 contains at least one loop, its loops form a clique and none of its edges connects two non-loops. It is then easy to verify that B contains both loops and non-loops. Because the other cases are similar, we prove only that B is not B3: since vertex d is not adjacent to a it must be in H 2 , and similarly for c. Since b is not adjacent to d it must also be in H 2 ; since non-loops of H 1 are not adjacent to elements of H 2 it follows that a is in H 2 also, a contradiction. Now we must show that every graph in L can be obtained from the basic graphs by disjoint union and adjunction of basic graphs. Suppose this is not the case. If H is a counterexample of minimum size, then obviously it is connected, and it contains at least one loop for otherwise it is a basic irreflexive graph. By Lemma 3.6, H also contains at least one non-loop.

For a ∈ H let N (a) denote its set of neighbours. Let R(H) denote the subgraph of H induced by its set R(H) of loops, and let J(H) denote the subgraph induced by J(H), the set of non-loops of H. Since H is connected and neither B1 nor B2 is an induced subgraph of H, the graph R(H) is also connected, and furthermore every vertex in J(H) is adjacent to some vertex in R(H). By Lemma 3.6, we know that R(H) contains at least one universal vertex: let U denote the (non-empty) set of universal vertices of R(H). Let J denote the set of all a ∈ J(H) such that N (a) ∩ R(H) ⊆ U . Let us show that J = ∅. For every u ∈ U , there is w ∈ J(H) not adjacent to u because otherwise H is obtained by adjoining u to the rest of H, a contradiction with the choice of H. If this w has a neighbour r ∈ R(H) \ U then there is some s ∈ R(H) \ U not adjacent to r, and the graph induced by {w, u, s, r} contains B2 or B3, a contradiction. Hence, w ∈ J. Let S denote the subgraph of H induced by U ∪ J. The graph S is connected. We claim that the following properties also hold:

(1) if a and b are adjacent non-loops, then N (a) ∩ U = N (b) ∩ U ;

(2) if a is in a connected component of the subgraph of S induced by J with more than one vertex, then for any other b ∈ J, one of N (a) ∩ U, N (b) ∩ U contains the other. The first statement holds because B1 is forbidden, and the second follows from the first because B4 is also forbidden. Let J 1 , . . . , J k denote the different connected components of J in S. By (1) we may let N (J i ) denote the set of common neighbours of members of J i in U . By (2), we can re-order the J i 's so that for some 1 ≤ m ≤ k we have N (J i ) ⊆ N (J j ) for all i ≤ m and all j > m, and, in addition, we have m = 1 or

|J i | = 1 for all 1 ≤ i ≤ m. Let B denote the subgraph of S induced by B = m i=1 (J i ∪ N (J i ))
, and let C be the subgraph of H induced by H \ B. We claim that H = B ⊘ C. For this, it suffices to show that every element in m i=1 N (J i ) is adjacent to every non-loop c ∈ C. By construction this holds if c ∈ J ∩ C. Now suppose this does not hold: then some x ∈ J(H) \ J is not adjacent to some y ∈ N (J i ) for some i ≤ m. Since x ∈ J we may find some z ∈ R(H) \ U adjacent to x; it is of course also adjacent to y. Since z ∈ U there exists some z ′ ∈ R(H) \ U that is not adjacent to z, but it is of course adjacent to y. If x is adjacent to z ′ , then {x, z, z ′ } induces a subgraph isomorphic to B2, a contradiction. Otherwise, {x, z, y, z ′ } induces a subgraph isomorphic to B3, also a contradiction.

If every J i with i ≤ m contains a single element, notice that B is a basic graph: indeed, removing all edges between its loops yields a bipartite irreflexive graph which contains neither the path of length 5 nor the 6-cycle, since B contains neither B5 nor B6. Since this contradicts our hypothesis on H, we conclude that m = 1. But this means that N (J 1 ) is a set of universal vertices in H. Let u be such a vertex and let D its complement in H: clearly H is obtained as the adjunction of the single loop u to D, contradicting our hypothesis. This concludes the proof.

Classification results

Recall the standard numbering of types: (1) unary, (2) affine , (3) Boolean, (4) lattice and ( 5) semilattice. We will need the following auxiliary result (which is well known). Note that the assumptions of this lemma effectively say that CSP(T) can simulate the graph k-colouring problem (with k = |U |) or the directed st-connectivity problem. (2) If R = {(t, t), (t, t ′ ), (t ′ , t ′ )} for some distinct t, t ′ ∈ T then V(A T ) admits at least one of the types 1, 4, 5.

Proof [sketch]: The assumption of this lemma implies that A T has a subalgebra (induced by U and {t, t ′ }, respectively) such that all operations of the subalgebra preserve the relation R. It is well-known (see, e.g., [START_REF] Hell | Graphs and Homomorphisms[END_REF]) that all operations preserving the disequality relation on U are essentially unary, while it is easy to check that the order relation on a 2-element set cannot admit operations satisfying identities (2.1)-(2.3), so one can use Lemma 2.1.

The following lemma connects the characterisation of bi-arc graphs given in [START_REF] Brewster | Near-unanimity functions and varieties of reflexive graphs[END_REF] with a type-omitting condition. Lemma 4.2. Let H be a graph. Then the following conditions are equivalent:

(1) the variety V(H) omits type 1;

(2) the graph H admits a conservative majority operation;

(3) the graph H is a bi-arc graph.

The results summarised in the following theorem are known (or easily follow from known results, with a little help from Lemma 4.2). Theorem 4.3. Let H be a graph.

• If typ(V(H)) admits type 1, then ¬ CSP(H L ) is not expressible in Datalog and CSP(H L ) is NP-complete (under first-order reductions);

• if typ(V(H)) omits type 1 but admits type 4 then ¬ CSP(H L ) is not expressible in symmetric Datalog but is expressible in linear Datalog, and CSP(H L ) is NL-complete (under first-order reductions.)

Proof. The first statement is shown in [START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF]. If the variety omits type 1, then H L admits a majority operation by Lemma 4.2 and then ¬ CSP(H L ) is expressible in linear Datalog by [START_REF] Dalmau | Majority constraints have bounded pathwidth duality[END_REF]; in particular the problem is in NL. If, furthermore, the variety admits type 4, then ¬ CSP(H L ) is not expressible in symmetric Datalog and is NL-hard by results in [START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF].

By Lemma 2. and5. By Lemma 4.2, H admits a majority operation, so Lemma 2.1 implies that V(H) also omits type 2; hence (3) holds. Implication (3)⇒( 4) is the content of Lemma 4.5 below, and (5) implies (3) by a result of [START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF]. By using Theorem 3.7, one can show that (4) implies both (1) and [START_REF] Bulatov | Tractable conservative constraint satisfaction problems[END_REF]. Finally, definability in symmetric Datalog implies membership in L by [START_REF] Egri | Symmetric Datalog and constraint satisfaction problems in Logspace[END_REF]. Proof. By Theorem 9.15 of [START_REF] Hobby | The Structure of Finite Algebras[END_REF], typ(V(H)) = {3} if and only if H admits a sequence of conservative operations satisfying certain identities (in the spirit of (2.1)-(2.3)). By conservativity, such operations can be restricted to any subset of H while satisfying the same identities, so the property typ(V(H)) = {3} is inherited by induced subgraphs. It follows that it is enough to prove this lemma for the forbidden graphs from Definition 3.3.

For the irreflexive odd cycles, the lemma follows immediately from the main results of [START_REF] Barto | The CSP dichotomy holds for digraphs with no sources and no sinks (A positive answer to a conjecture of Bang-Jensen and Hell)[END_REF][START_REF] Maróti | Existence theorems for weakly symmetric operations[END_REF]. The proof of Theorem 3.1 of [START_REF] Feder | List homomorphisms and circular arc graphs[END_REF] shows that the conditions of Lemma 4.1(1) are satisfied by (some S, s 1 , s 2 and) T = F L where F is the irreflexive 6-cycle. One can check that the reflexive 4-cycle is not a bi-arc graph, so we can apply Lemma 4.2 in this case.

For the remaining forbidden graphs F from Definition 3.3, we use Lemma 4.1(2) with T = F L . In each case, the binary relation of the structure S will be a short undirected path, and s 1 , s 2 will be the endpoints of the path. We will represent such a structure S by a sequence of subsets of F (indicating lists assigned to vertices of the path). It can be easily checked that, in each case, the relation R defined as in Lemma 4.1 is of the required form.

If F is the reflexive path of length 3, say abcd, then S = acbcadac. If F is the irreflexive path of length 5, say abcdef then S = aebdcebfae. For graphs B1 -B6, we use notation from Fig. 1. For B1, S = bcbcababbc. For B2, S = bcacabbc. For B3, S = bcadbdbc. For B4, S = aebdcdae. Finally, for both B5 and B6, S = acb ′ c ′aba ′ c ′ac.

For completeness' sake, we describe graphs whose list homomorphism problem is definable in first-order logic (equivalently, is in AC 0 , see [START_REF] Bulatov | Dualities for constraint satisfaction problems[END_REF].) By results in [START_REF] Larose | Universal algebra and hardness results for constraint satisfaction problems[END_REF], any problem CSP(T) is either first-order definable or L-hard under FO reductions. Hence, it follows from Theorem 4.4 that, for a graph H ∈ L, the list homomorphism problem for H is either first-order definable or L-complete.

We need the following characterisation of structures whose CSP is first-order definable [START_REF] Larose | A characterisation of first-order constraint satisfaction problems[END_REF]. Let T be a relational structure and let a, b ∈ T . We say that b dominates a in T if for any relation R of T, and any tuple t ∈ R, replacement of any occurrence of a by b in t will yield a tuple of R. Recall the definition of a direct power of a structure from Subsection 2.1. If T is a relational structure, we say that the structure T 2 dismantles to the diagonal if there exists a sequence of elements {a 0 , . . . , a n } = T 2 \ {(a, a) : a ∈ T } such that, for all 0 ≤ i ≤ n, a i is dominated in T i , where T 0 = T 2 and T i is the substructure of T 2 induced by T 2 \ {a 0 , . . . , a i-1 } for i > 0.

Lemma 4.6 ([21]). Let T be a core relational structure. Then CSP(T) is first-order definable if and only if T 2 dismantles to the diagonal. Theorem 4.7. Let H be a graph. Then CSP(H L ) is first-order definable if and only if H has the following form: H is the disjoint union of two sets L and N such that (i) L is the set of loops of H and induces a complete graph, (ii) N is the set of non-loops of H and induces a graph with no edges, and (iii) N = {x 1 , . . . , x m } can be ordered so that the neighbourhood of x i is contained in the neighbourhood of x i+1 for all 1 ≤ i ≤ m -1.

Proof. We first prove that conditions (i) and (ii) are necessary. Notice that if CSP(H L ) is first-order definable then so is CSP(K L ) for any induced substructure K of H. Let x and y be distinct vertices of H and let K L be the substructure of H L induced by {x, y}. If x and y are non-adjacent loops, then θ(K) = {(x, x), (y, y)} the equality relation on {x, y}; if x and y are adjacent non-loops, then θ(K) = {(x, y), (y, x)}, the adjacency relation of the complete graph on 2 vertices. It is well known (and can be easily derived from Lemma 4.6) that neither of these classes CSP(K L ) is first-order definable. It follows that the loops of H induce a complete graph and the non-loops induce a graph with no edges. Now we prove (iii) is necessary. Suppose for a contradiction that there exist distinct elements x and y of N and elements n and m of L such that m is adjacent to x but not to y, and n is adjacent to y but not to x. Then CSP(G) is first-order definable, where G is the substructure of H L induced by {x, y, m, n}. By Lemma 4.6, G 2 dismantles to the diagonal. Then (x, y) must be dominated by one of (x, x), (y, x) or (y, y), since domination respects the unary relation {x, y} 2 (on G 2 ). But (m, n) is a neighbour of (x, y) and none of the other three, a contradiction.

For the converse: we show that we can dismantle (H L ) 2 to the diagonal. Let x ∈ H: then (x 1 , x) and (x, x 1 ) are dominated by (x, x). Suppose that we have dismantled every element containing a coordinate equal to x i with i ≤ j -1: if x is any element of H such that the elements (x j , x) and (x, x j ) remain, then either x is a loop or x = x k with k ≥ j; in any case the elements (x j , x k ) and (x k , x j ) are dominated by (x, x). In this way we can remove all pairs (x, y) with one of x or y a non-loop. For the remaining pairs, notice that if u and v are any loops then (u, v) is dominated (in what remains of (H L ) 2 ) by (u, u).

Finally, given a graph H, it can be decided in polynomial time which of the different cases delineated in Theorems 4.3, 4.4, 4.7 the list homomorphism problem for H satisfies. Indeed, it is known that bi-arc graphs can be recognised in polynomial time (see [START_REF] Feder | Bi-arc graphs and the complexity of list homomorphisms[END_REF]). Assume that H is a bi-arc graph: the forbidden substructure definition of the class L gives an AC 0 algorithm to recognise them; and those graphs whose list homomorphism problem is first-order definable can be recognised in polynomial time by results of [START_REF] Larose | A characterisation of first-order constraint satisfaction problems[END_REF].

Definition 3 . 1 .Figure 1 :

 311 Figure 1: The forbidden mixed graphs.

Lemma 4 . 1 .

 41 Let S, T be structures, let s 1 , s 2 ∈ S, and letR = {(f (s 1 ), f (s 2 )) | f : S → T}. (1) If R = {(x, y) ∈ U 2 | x = y} for some subset U ⊆ T with |U | ≥ 3 then V(A T )admits type 1.

Lemma 4 . 5 .

 45 If H ∈ L then typ(V(H)) = {3}.

  1, the presence of a majority operation in H implies that typ(V(H)) can contain only types 3 and 4. Type 4 is dealt with in Theorem 4.3, so it remains to investigate graphs H with typ(V(H)) = {3}. The next theorem is the main result of this paper. ¬ CSP(H L ) is definable in symmetric Datalog. If the above holds then CSP(H L ) is in the complexity class L. Proof [sketch]: (1) ⇒ (2) is trivial. If (2) holds then by Lemma 2.1 V(H) omits types 1, 4,

	Theorem 4.4. Let H be a graph. Then the following conditions are equivalent:
	(1) H admits conservative operations satisfying (2.1)-(2.3) for n = 3;
	(2) H admits conservative operations satisfying (2.1)-(2.3) for some n ≥ 1;
	(3) typ(V(H)) = {3};
	(4) H ∈ L;
	(5)

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.


Frédéric Archaux
email: frederic.archaux@cemagref.fr

Hilaire Martin

HYBRID POPLAR PLANTATIONS IN A FLOODPLAIN HAVE BALANCED IMPACTS ON FARMLAND AND WOODLAND BIRDS

Keywords: Bird, Hybrid poplar, Landscape, Plantation, Management

Hybrid poplar plantations are increasing worldwide and are often accused of impoverishing bird communities in surrounding farmland and woodland areas. We conducted 124 bird point counts in a landscape where plantations, semi-natural forests and farmland occupied similar surface areas. As expected, birds occurred at higher densities in forests than in plantations, mostly due to the scarcity of late-successional forest birds in plantations. Contrary to expectations, bird communities were the poorest in farmland dominated areas and the most specialised in areas dominated by young plantations. Indeed, many grassland species, including some of conservation concern in Europe, frequently or almost exclusively used young plantations. However, plantations have probably depleted grassland bird communities by fragmenting open areas, while playing a limited positive role on forest species. Total length of unpaved roads had a positive effect on community specialisation index, while total length of paved roads and mean forest/plantation patch size played no role. Bird density increased with the development of the understory vegetation in mature poplar plantations. We conclude that poplar plantations should be avoided in areas of high conservation value; in other areas, they may increase the overall diversity of bird communities. At the plantation scale, we advocate stopping understory removal as soon as possible and maintaining old trees and hedgerows alongside or within plantations to provide suitable breeding habitats for bird species that may be foraging in the plantations.

Introduction

Many fertile floodplains in Europe were occupied by large riparian forests dominated by hardwood tree species (oaks, ash) before the Middle Ages (Petts et al., 1989). Human population growth caused a progressive conversion of a large part of these forests into farmland, while most of the remnants were managed as coppices or coppices with standards for fuel wood production [START_REF] Steiger | Hydrogeomorphic processes affecting riparian habitat within alluvila channel-floodplain river systems: a review for the temperate zone[END_REF]. The farming on these lands varied greatly over time and space, and the landscape included pastures, hayfields, various ploughed fields, and more recently maize fields and set-asides. From the XVIIIth century onwards, poplars were often planted at the expense of arable lands and the few forest remnants (Petts et al., 1989).

Many factors jointly caused an acceleration of this phenomenon after the 1950s: the embankment of large rivers limited the occurrence and magnitude of floods that poplar plantations are sensitive to, the overproduction of dairy and meat production in Europe caused a strong decrease in cattle numbers, the need for wood fibre increased, poplar plantations (from two-year stems) readily took , and fast-growing, fungus-resistant cultivars became available through hybridization among European, Asian and American Populus species [START_REF] Schnitzler | Conservation of biodiversity in alluvial hardwood forests of the temperate zone: the example of the Rhine Valley[END_REF]. In France, hybrid poplar plantations now represent 1.6% of the forested area (ca 260,000 ha) and this area is still increasing (+0.8% between 1988and 2002, SCEES/Terruti data 2003).

Since 1980, hybrid poplar plantations have been accused of contributing to the decrease in bird populations in floodplains in Western Europe [START_REF] Zollinger | Etude comparée de l'avifaune de ripisylves et de populicultures aux Grangettes (Vaud)[END_REF][START_REF] Schmitz | Avifaunes nicheuse et hivernante des peupleraies de Hesbaye occidentale[END_REF][START_REF] Pont | Comparaison de l'avifaune nicheuse d'une ripisylve et de peupleraies de la moyenne vallée du Rhône (île de la Platière)[END_REF][START_REF] Mourgaud | Etude comparative des passereaux nicheurs en prairie alluviale et en peupleraie dans les Basses Vallées Angevines[END_REF][START_REF] Godreau | Biodiversity in the floodplain of Saône: a global approach[END_REF]. However, this seems to be an over-simplification. Indeed, several studies have shown that some uncommon/rare birds may use poplar plantations; for example, the Golden oriole Oriolus oriolus is restricted to mature poplar plantations in Great-Britain [START_REF] Dagley | Golden orioles in East Anglia and their conservation[END_REF]. Furthermore, the ecological impact of plantations depends on the habitats they are compared with: [START_REF] Hanowski | Influence of within-plantation heterogeneity and surrounding landscape composition on avian communities in hybrid poplar plantations[END_REF] in North America showed that the number of breeding birds was higher in poplar plantations than in the row crops the plantations were replacing but less than in surrounding forest/shrub habitat. Finally, extensively-managed plantations may be less unfavourable to breeding birds than intensively-managed ones [START_REF] Pont | Comparaison de l'avifaune nicheuse d'une ripisylve et de peupleraies de la moyenne vallée du Rhône (île de la Platière)[END_REF][START_REF] Godreau | Impact des changements d'occupation des sols et de la populiculture sur les peuplements aviens et floristiques en plaine alluviale[END_REF].

We believe further studies are needed to confirm some of these results and better understand the impact of hybrid poplar plantations on bird communities. In particular, the previous studies rarely used a landscape perspective (but see [START_REF] Hanowski | Influence of within-plantation heterogeneity and surrounding landscape composition on avian communities in hybrid poplar plantations[END_REF][START_REF] Godreau | Impact des changements d'occupation des sols et de la populiculture sur les peuplements aviens et floristiques en plaine alluviale[END_REF]) and yet, many birds need a mosaic of adjacent habitats to breed and forage (e.g. [START_REF] Virkkala | Effects of landscape composition on farmland and red-listed birds in boreal agricultural-forest mosaics[END_REF]. Furthermore, the poplar plantations studied so far have usually been isolated within a farmland matrix and have always represented a minor proportion of the landscape (e.g. at most 12% in area, [START_REF] Godreau | Impact des changements d'occupation des sols et de la populiculture sur les peuplements aviens et floristiques en plaine alluviale[END_REF]) and yet isolation of forest fragments is well-known for causing deleterious effects on bird communities, irrespective of tree species [START_REF] Blake | Breeding birds of isolated woodlots: area and habitat relationships[END_REF][START_REF] Hinsley | Habitat and landscape factor influencing the presence of individual breeding bird species in woodland fragments[END_REF]. More connected poplar plantations may host more woodland species, as suggested by [START_REF] Godreau | Impact des changements d'occupation des sols et de la populiculture sur les peuplements aviens et floristiques en plaine alluviale[END_REF].

In this study, we focused on a floodplain area in northern France where semi-natural forests, poplar plantations and farmland represented equivalent proportions in the landscape.

Within this landscape, we assessed how bird communities responded to habitat composition at three different spatial scales (100, 250 and 500m-radius circles). More specifically, our main working hypotheses were:

-bird densities decrease with an increasing proportion of poplar plantations in the surroundings, -the greater the area planted with hybrid poplar, the less specialised the bird communities, -the presence of forest birds depends mainly on semi-natural forest areas but also, to a smaller extent, on mature poplar plantations, -bird densities vary with the fragmentation of habitats, -bird densities in plantations increase with understory vegetation cover due to larger areas suitable for breeding/foraging and/or to a higher number of potential niches.

Methods

Study area

The 6950-ha study area is located between Romilly-sur-Seine and Méry-sur-Seine (France, Aube department, ca 100-120m asl), along 20 km of the Seine River on deep, chalky soils corresponding to modern alluvial deposits. The climate is Atlantic with continental influences (mean annual temperature ca 10°C with 630-700mm annual rainfall). Poplar plantations represent 27% of the area due to the unusual width (2-3km) of the floodplain (nearby confluence of the Seine with the Aube River). Other land uses found in the floodplain were farmland and open areas (36%), forests (22% including abandoned poplar plantations), urban areas (11%) and aquatic areas (4%). The poplar plantations did not differ from that of forests in terms of median size (Wilcoxon rank-sum test, W = 151758, P = 0.52) but other areas (farmland, other open, urban and aquatic areas) were significantly larger than poplar plantations (W = 226243, P = 0.001) and forests (W = 155897, P = 0.02) (Table 1). The study area extended slightly beyond the floodplain bottom onto the intensive row crop fields of the plateau, so as to allow us to calculate habitat areas surrounding bird sampling points up to 500m. Crop fields are also found within the plain (including maize fields), along with setasides and, to a far lesser extent, hay pastures. The nearest large forest (the "Traconne") state forest that may be a source of forest birds is about 10km from the study area. As hedgerows are also scarce on the plateau, bird exchanges between forested areas in the valley and the plateau are probably limited. At a larger scale (Aube and Seine floodplains sensu the French National Inventory: 34,025 ha), hardwood forests decreased by 53% between 1974 and 1994, representing only 5.5% of the total area in 1994 (ca 1,660ha) versus 3,740ha for poplar plantations (French Forest Inventory data, 1994).

The study area was first mapped from colour aerial photographs taken in [START_REF] Twedt | Artificial cavities enhance breeding bird densities in managed cottonwood forests[END_REF]2004 (NGI data). We separated unpaved and paved roads and identified nine major habitats:

(1) very young VYP, (2) young YP and (3) mature MP poplar plantations; (4) young YF and

(5) old OF hardwood forests; (6) farmland Farm (cropland and grassland combined); (7) urban areas; (8) aquatic areas (rivers, ponds, lakes) and ( 9) other open habitats. We attributed one of these habitat classes to the 1,592 polygons that were individualised from aerial photos; then, in the field, we checked the correctness of this attribution. In the field, poplar stands were attributed to the very young class when the mean diameter at breast height (dbh) was less than 20cm, to the young class when the dbh was between 20 and 30cm, and to the mature class when above 30cm (i.e. when the canopy closes). In the area, poplars are cut when about 20 years old. Mean distance between poplars in plantations is almost invariably 7m in the area (occasionally 6 or 8m). Plantations are ploughed, and sometimes fertilised, at plantation; the clones most often used are Populus x interamericana "Beaupré" and P. x canadensis "I214".

The understory vegetation is mechanically and/or chemically removed during the first years after planting. This control may be either continued more or less regularly (intensive management) or ceased (extensive). In the case of intensive management, the vegetation understory is limited to sedges and grasses (including Nettle Urtica dioca). In extensively managed plantations, a shrubby layer develops with Blackthorn Prunus spinosa, Common Elder Sambucus nigra, Willow Salix sp, and Blue Bramble Rubus caesius. All the young forest stands (YF) actually originated from former poplar plantations cleared in December 1999 after the Lothar windstorm (ca 30% of the plantations in the study area were cleared) and never replanted: these stands could be considered either as very extensive young poplar plantations (due to the presence of naturally resprouting poplars) or young semi-natural forests (due to the rapid recolonisation by ash and other shrubs). Old forest stands (OF) included a variety of forest types, from most to least common: (1) coppiced Hazel Corylus avellana with standards of Pedunculate Oak Quercus robur and Ash Fraxinus excelsior, (2) abandoned over-mature poplar plantations overgrown by Ash, (3) spontaneous riparian forests (including the previously mentioned species, as well as Alder Alnus glutinosa, Sycomore Maple Acer pseudoplatanus, Smooth-leaved Elm Ulmus minor and various willow species Salix sp. along river beds) and ( 4) old Ash/Hazel coppices.

Bird point counts

124 bird point counts were located throughout the study area, based on a quasisystematic grid design (ca 400m between points). We located the majority of the points along paths for efficiency and discretion (a few were carried out along roads with limited traffic at the time of the counts). Each point was visited twice (two 5-min counts), first between April 16 and 27 (between 6:30 and 9:43 am), and second between the May 30 and June 8, 2007 (between 5:42 and 9:32 am). All counts were carried out under good weather conditions (no wind, no rain).

During the count, the observer (FA) used aerial photographs centred on the points to localise all singing (the great majority) or moving/flying (a minority) birds. The fact that the landscape was very fragmented helped to locate the birds. As for the territory mapping method, the observer estimated whether the birds recorded during the second visit had already been detected during the first visit (according to the spatial proximity among the contacts). A total of 2,482 individual birds (62 species) were recorded and incorporated in the GIS. Total cover for the 1-4m and 4-8m vegetation layers was visually estimated (and classified in 5% increments above a minimum 5% total cover). The mean poplar dbh was measured in poplar plantations immediately surrounding the points (but not in more distant plantations).

Data analyses

To test our working hypotheses, for each point we estimated the bird density, the mean specialisation and preference for mature forests of the bird community. Only birds recorded within 100m of the observer were kept (N=1138, 47 species). To adjust raw count data for imperfect detection, we treated the two visits as two replicate counts and calculated the total number of individuals A (observed abundance) and the number of individuals recorded at only one visit (n 1 ). We calculated the Jackknife 1 estimator (Jack1 = A + n 1 /2) and its standard deviation (SD = ½√(3n 1 )) for each point as an estimate of the total number of birds (all species) present within 100m. This estimator assumes heterogeneity of detection among species [START_REF] Burnham | Robust estimation of population size when capture probabilities vary among animals[END_REF], a classical phenomenon in bird communities [START_REF] Boulinier | Estimating species richness: the importance of heterogeneity in species detectability[END_REF]. Density (number of pairs.ha -1 ) was then estimated as Jack1/π (the area 100m around the point, in ha). In models, we used the inverse of the variance of the density estimate to weight observations: observations for which density was known with lesser precision were logically given smaller weight.

We calculated the community specialisation index (CSI), a measure of the mean specialisation of the bird community [START_REF] Julliard | Common birds facing global changes: what makes a species at risk?[END_REF], using data from the specialisation index of 105 common birds by [START_REF] Devictor | Functional biotic homogenization of bird communities in disturbed landscapes[END_REF]. The CSI index is known to correlate well with the level of landscape fragmentation and disturbance [START_REF] Devictor | Functional biotic homogenization of bird communities in disturbed landscapes[END_REF]. The higher the CSI, the more specialised the bird community. We followed the same rationale to define the community preference for mature forests (CPMF). [START_REF] Muller | L'avifaune forestière nicheuse des Vosges du Nord. Sa place dans le contexte médio-européen[END_REF] provided the mean age of the forest stands for 40 common European bird species where these species were observed in French oak regular high forest stands; stand age varied from 10 years for the early-successional Willow Warbler Phylloscopus trochilus to 147 years for the latesuccessional Short-toed Treecreeper Certhia brachydactyla. CPMF was calculated as the mean stand age over all species recorded within 100m. The greater the CPMF, the more typical the bird community to mature forests. In analyses, we kept only points for which CSI and CPMF indices could be calculated from at least five species and we weighted the observations in models using the inverse of the variance of the index estimate (as for species richness).

Using the GIS, we extracted the area covered by the nine pre-defined habitats within 100, 250 and 500m of the point. We also recorded the cumulated length of ( 1) unpaved roads and (2) paved roads within the same radii. Finally, we calculated the mean patch size 100, 250 or 500m around the point (MPS) for plantations and forest patches. We modelled the impact of these explanatory variables on the different community indices defined above using spatially-explicit GAM models. A generalized additive model (GAM) is a generalized linear model (GLM) in which spatial autocorrelation is modelled using a non-parametric, smooth function of the geographical coordinates of the study points (using the gam function from R library mgcv). To limit spurious effects of non-focal habitats (aquatic, gardens, urban, open habitats other than farmland), we excluded from our analyses 20 points where these habitats represented more than 5% of the area within 100m around the point. The final data set contained 104 points for species richness, 85 for the CSI and 79 for the CPMF. To identify the spatial scale that could explain the largest part of the total variance in the community indices, we built models including all nine selected variables (farmed area, very young plantation area, young plantation area, mature plantation area, young forest area, old forest area, mean patch size of plantations and forests, cumulative length of paths, cumulative length 1 of roads) calculated either on 100, 250 or 500m around the point. Then, we compared the relative merits of the three models with AIC (the lower the AIC value, the better). To further investigate how the community indices varied among the six habitat area variables, we used the model with the lowest AIC value in the preceding step of the analysis and we progressively aggregated habitat area variables whose model coefficients were roughly similar until the AIC of the resulting simpler model did not decrease any further: this step of grouping habitat variables revealed which (groups of) habitats had similar and distinct impacts on the bird communities. The significance of the MPS and length of paths and roads variables was directly tested from an ANOVA (using the ANOVA function in R).

It was difficult to reliably assess the impact of the understory vegetation in plantations on birds. Indeed, many plantations were small, leading to potentially confounding edge effects. Furthermore, the observer rarely stood within the plantations during the counts, so that only part of the larger plantations may have been effectively "sampled" (a positive aspect of this sampling design is nonetheless that singing birds were less disturbed). We addressed this issue by restricting our analyses to birds recorded within 100m of the observer, in mature plantations (mean dbh over 30cm) covering at least 1ha within a 100m radius of the point (ca >30% of the circle area). We further excluded all narrow plantations to limit edge effects, finally retaining a list of 28 patches of mature plantations. We then estimated a density per patch by dividing the number of birds recorded in a given patch (all species confounded, corrected for imperfect detection using the Jackknife 1) by patch size. We built simple linear models on unadjusted bird density with the 1-4m and 4-8m cover indices as explanatory variables. Unadjusted bird density is given in Table 3 for the 20 most common bird species in the six main habitats considered in this study.

Results

1

Mean bird density (Jackknife1) over the 104 point counts was estimated at ca 3.8±1.5 pairs.ha -1 (assuming a singing male corresponds to a breeding pair). Little spatial autocorrelation was found as the effect of the spatial smoother was never significant. Bird density was correlated to neither CSI nor CPMF, but the latter two variables were highly negatively correlated (Pearson's r = -0.55, t = -5.7, df = 77, P<0.001). For the three indices, the model including explanatory variables defined locally (i.e. 100m around the point) had a significantly lower AIC value than models including variables defined at larger scales (250 or 500m) (Table 2). Models explained a reasonable part of the variance for CPMF but a more limited part for CSI and bird density, reflecting either measurement error or less determinism in these variables (Table 2).

Bird density primarily decreased with farmland area and was highest in forests (Table 2). Interestingly, several habitats contributed to the CSI and CPMF but at different levels: CSI increased primarily with the area of very young and young poplar plantations and secondarily with the area of farmland. Similarly, CPMF was mostly related to the area of old forests but the negative impact of the main other habitats gradually decreased with the structural similarity of the habitat to old forest (this similarity increasing from (1) very young plantations, (2) farmland and young plantations, (2) young forest to (3) mature plantations).

None of the three indices was significantly related either to the mean patch size of plantations and woodlands, or to the cumulative length of roads. Only the mean level of specialisation of the species increased with the length of footpaths.

Variation in bird density between plantations increased with the increase in the understory cover. Nonetheless, log-transformed bird density (to limit heteroscedasticity) increased more or less linearly with the understory cover up to 30% (Pearson's r = 0.62, t=3.88, df= 24, P<0.001) and then seemed to stabilise (Fig. 1). On the contrary, bird density was unrelated to the overstory cover (Pearson's r = -0.22, t=-1.1, df= 26, P=0.17, Fig. 2).

Discussion

Our results show that the impacts of poplar plantations on bird communities are more complex than it is usually claimed: birds in poplar plantations did occur in lower densities than in semi-natural forest stands (whatever stand age) but in higher densities than in farmed areas. Similarly, mature plantations effectively lacked many of the forest birds typically found in old forest stands; yet a truncated succession in bird communities occurred along the poplar rotation, the composition of bird communities in mature plantations being somewhat intermediate between young and old forest stands. Finally, contrary to what is generally thought, the most specialised bird communities were found in the very young and young poplar plantations, whereas mature plantations and forests hosted the least-specialised bird communities.

Plantations versus farmland

Bird communities were also found to be poorer in intensively-managed farmland than in short-rotation hybrid poplar plantations in North America [START_REF] Hanowski | Influence of within-plantation heterogeneity and surrounding landscape composition on avian communities in hybrid poplar plantations[END_REF]. Bird populations in our study valley are probably also suffering from the intensive management of the farmland. Obviously, the set-asides and the too few and too artificial grasslands play a reduced protective role for grassland birds in the area. In addition, plantations may have exacerbated the decline in grassland species by fragmenting the grassland areas. Indeed, [START_REF] Godreau | Biodiversity in the floodplain of Saône: a global approach[END_REF] showed that many grassland species were very sensitive to the 1 fragmentation of open habitats along the Saône River, a few hundred km south of our study site. The relatively large areas planted with poplars in our site probably explain why many of the specialist grassland species that could normally breed in our floodplain were either never recorded (Quail Coturnix coturnix, Black-tailed Godwit Limosa limosa, Curlew Numenius torquata, Meadow Pipit Anthus pratensis, Whinchat Saxicola rubetra and Yellow Wagtail Motacilla flava) or very rarely recorded (Lapwing Vanellus vanellus, Skylark Alauda arvensis, Corn bunting Miliaria calandra, Pied wagtail Motacilla alba and finches Carduelis sp). Yet, some of these species were regularly observed in the immediate neighbourhood of the study area (the Skylark, Corn Bunting and Yellow Wagtail on the purely agricultural plateau, finches in urban areas), supporting the hypothesis that the valley is repulsive to many grassland birds. Finally, plantations probably favoured the Carrion Crow Corvus corone which appreciates the mosaic of interconnected farmland and woodland patches; this species is known to heavily predate on the eggs of grassland ground nesters [START_REF] Andren | Corvid density and nest predation in relation to forest fragmentation: a landscape perspective[END_REF].

Although poplar plantations at the landscape scale may contribute to the near absence of many grassland species, several ground-and shrub-nesters usually found in farmland along hedgerows were commonly recorded in very young and young plantations. The same pattern was found along the nearby Saône River [START_REF] Godreau | Biodiversity in the floodplain of Saône: a global approach[END_REF]. Interestingly, Yellowhammer Emberiza citrinella was recorded as frequently in very young poplar plantations as in farmland. Other species found in very young and young plantations included Melodious Warbler Hippolais polyglotta, Whitethroat Sylvia communis, Grasshopper Warbler Locustella naevia and, more marginally, Red-backed Shrike Lanius collurio. These species are considered to be habitat specialists [START_REF] Devictor | Functional biotic homogenization of bird communities in disturbed landscapes[END_REF], a fact that probably explains why the most specialised bird communities were found in areas dominated by very young and young plantations.

Plantations versus woodland

The lower bird density in plantations compared to semi-natural forests has repeatedly been found in Western Europe and North America [START_REF] Schmitz | Avifaunes nicheuse et hivernante des peupleraies de Hesbaye occidentale[END_REF][START_REF] Hanowski | Influence of within-plantation heterogeneity and surrounding landscape composition on avian communities in hybrid poplar plantations[END_REF][START_REF] Godreau | Impact des changements d'occupation des sols et de la populiculture sur les peuplements aviens et floristiques en plaine alluviale[END_REF][START_REF] Twedt | Impact of forest type and management strategy on avian densities in the Mississippi Alluvial Valley, USA[END_REF]. This pattern is mostly due to the scarcity in plantations, even mature, of forest species that prefer old trees with a dense foliage to forage or breed such as the Woodpigeon Columba palumbus, Blue Tit Cyanistes caeruleus, Nuthatch Sitta europaea, Short-toed Treecreeper and Chaffinch Fringilla coelebs (Table 3). Although cavity-nesters were logically more frequent in forests than in plantations, mature poplar plantations in our study were regularly used by the Great-spotted Woodpecker Dendrocopos major, the Great Tit Parus major (breeding in abandoned cavities of the Great-spotted Woodpecker) and the Willow Tit Poecile montanus. Dead poplars may be suitable to this species that needs decaying softwood trees to dig its own cavities.

The young stages of poplar plantations hosted bird communities globally distinct from that of the young forests: species like Stock Dove Streptopelia turtur, Winter Wren Troglodytes troglodytes, Nightingale Luscinia megarhynchos, Melodious Warbler, Blackcap Sylvia atricapilla, Garden Warbler Sylvia borin and Starling Sturnus vulgaris preferred young forests to young plantations, probably in response to the higher structural and compositional diversity of the shrub layer (the starling was probably also favoured by the presence of old poplar snags in many young forest patches). Conversely, the Tree Pipit Anthus trivialis and Grasshopper Warbler were more frequently found in young plantations: they respectively forage on or close to the ground, in dense herbaceous vegetation; these two species rapidly colonise plantations after planting and desert them a few years later, as the canopy closes.

More surprisingly, the level of specialised bird communities was lowest in the areas dominated by forests (at a level similar to that of mature poplar plantations). Actually, as for 1 farmland, among the forest specialist species potentially present in floodplain forests [START_REF] Godreau | Biodiversity in the floodplain of Saône: a global approach[END_REF], some were never recorded (Middle-spotted Woodpecker Dendrocopos medius, Wood Warbler Phylloscopus sibilatrix) or very rarely (Lesser-spotter Woodpecker Dendrocopos minor, Spotted Flycatcher Muscicapa striata, Hawfinch Coccothraustes coccothraustes). In our study, the semi-natural forest fragments are probably too small and isolated to allow these area-sensitive birds to maintain viable populations.

Several authors argued that the development of understory in extensively-managed poplar plantations is favourable to small birds [START_REF] Schmitz | Avifaunes nicheuse et hivernante des peupleraies de Hesbaye occidentale[END_REF][START_REF] Godreau | Impact des changements d'occupation des sols et de la populiculture sur les peuplements aviens et floristiques en plaine alluviale[END_REF]. We did in fact observe that bird density increased with the vegetation cover between 1 and 4m (though possibly not linearly), but this was not the case above 4m. Our sample size was too small to statistically assess whether the higher bird density in extensively-managed plantations was primarily caused by a greater number of species or simply by a higher abundance of the same set of species. In the study by [START_REF] Godreau | Impact des changements d'occupation des sols et de la populiculture sur les peuplements aviens et floristiques en plaine alluviale[END_REF], the number of species more frequently recorded in intensively-managed plantations did not differ statistically from the number of species more frequently found in extensively-managed plantations (16 versus 19, binomial test, P=0.74). Thus, extensive management of the plantations probably improves the overall quality of the mature plantations more than it provides new niches benefiting new species; as a result, it probably mainly favours the species already able to cope with the initial intensive management of poplar plantations. This hypothesis may also hold in North America since [START_REF] Christian | Effects of mechanical strip thinning of aspen on small mammals and breeding birds in northern Minnesota[END_REF] also conclude that (aspen) stand thinning has a weakly positive and transitory effect on species abundances but none on the number of breeding species.

Impact of habitat fragmentation

1 [START_REF] Godreau | Impact des changements d'occupation des sols et de la populiculture sur les peuplements aviens et floristiques en plaine alluviale[END_REF] noted that the number and abundance of forest birds in poplar plantations increased with the size of the plantation. We found little convincing evidence of any effect of habitat fragmentation, except for a positive impact on the length of unpaved roads on the mean community specialisation. The vegetation along unpaved roads is likely to provide food resources that are otherwise limited in fields for several specialist birds, especially seed-eaters such as yellowhammer and stock dove. The fact that the mean size of forest and plantation patches (MPS) moderately varied among points (MPS within 100-m radius disks exceeded 2ha for only eight of the 104 points) probably explains why we failed to find an effect on bird communities. Similarly, paved roads were present within 100m of the points in only 14 points (by comparison, 87 points included paths within 100m).

Implications for bird conservation in floodplains

This study gives a balanced view of the impact of poplar plantations on common birds in floodplains. On one hand, plantations do not provide refuge habitats for the most specialised grassland and woodland birds. On the other hand, several woodland birds use mature plantations (although often at lower densities than in semi-natural forests). Thus, the conversion of intensive crop fields by plantations may be beneficial to some open-land and woodland birds (at different ages of the plantations). On one hand, in areas of high conservation value, they probably contribute to the loss of the most area-sensitive birds in floodplains by causing the loss and fragmentation of grassland and woodland. On the other hand, in already fragmented and intensively-managed farming areas such as our study area, many grassland birds, including some that are currently declining all over Europe, use young plantations to breed (although it remains to be demonstrated that young plantations are not also demographic sinks).

At the scale of the plantation, extensive management has a positive impact on bird density. This means that the removal of understory should stop as soon as the understory no longer threatens the growth of poplars. In addition, plantations seem to lack breeding places for many species, although plantations may represent valuable foraging habitats. For instance, the presence of the great tit in mature plantations probably indicates that other cavity-nesters would breed in plantations if sufficient cavities would be available: thus, the retention of large old/decaying poplars, ashes or oaks within or along the plantation would probably favour cavity-nesters. Those trees with a dense crown would also represent breeding sites safer than poplars for species nesting in tree crown. Alternatively, nest-boxes may be installed in plantations as suggested by [START_REF] Twedt | Artificial cavities enhance breeding bird densities in managed cottonwood forests[END_REF]. Similarly, hedgerows may be installed between plantations or within large plantations to the benefit of shrub bird species.

The supplementary cost related to the retention of old trees and hedgerows may be partly compensated by a better regulation of poplar defoliating insect populations since these measures would be mostly beneficial to insectivorous birds. Table 1 Impact of landscape variables on bird assemblages (BD bird density, CPMF community preference for mature forests, CSI community specialisation index) 1

1

 1

  . a) AIC values of the three alternative models based on the same set of variables but defined at three different spatial scale (100, 250 and 500m around the point)); in bold the model with the lower AIC before aggregating habitat area variables (Farm to OF variables); the % deviance of this model in provided in b); in superscript AIC of the best model after aggregating the habitat area variables. c) Fitted coefficients and standard errors of the explanatory variables corresponding to the model in bold in a) (removing the intercept) and in superscript (a-d) variables whose aggregation improves model AIC (the AIC of the corresponding model is the value in superscript in a)). For MPS, Paths, Roads and the smoother: *P<0.05, italics P<0.

Table 2 485

 2 1.Bird density (number of singers/10ha) of the 20 most common species calculated from the 486 124 point counts of the study depending on the habitat where the individual was recorded 487 (#Ind: total number of individuals recorded within 100m around the points, see also Table2 488

	Variables	BD	CPMF	CSI
	a) AIC (100/250/500) 617 612 /619/632 587 584 /599/610 -108 -113 /-85/-82
	b) %Dev	36.8	67.9	39.1
	c) Farm	1.2±0.6 a	10.5±2.5 a	-0.27±0.02 a
	VYP	3±0.7 b	6.5±1.2 b	-0.20±0.03 b
	YP	3.1±0.7 b	11.2±2.1 a	-0.24±0.03 b
	MP	3.6±0.5 b	15.2±1.3 c	-0.33±0.02 c
	YF	4.5±1 c	12.4±1.9 a	-0.34±0.03 c
	OF	5.1±0.7 c	22.1±1.8 d	-0.34±0.02 c
	MPS	-1.0±0.8	-4.5±2.3	0.03±0.02
	Paths	0.3±0.5	-1.5±1.2	0.03±0.01*
	Roads	0.6±0.4	1.7±0.9	0.0±0.01
	Smooth df	10.8	5.8	3.2

Farm farmland, VYP/YP/MP very young/young/mature poplar plantations, YF/OF young/old forests, MPS mean patch size of plantations and forests (all in ha), Paths/Roads cumulated length of paths or roads (km);. Smooth df: estimated degree of freedom of the spatial smoother.

Acknowledgments

We are grateful to R. Chevalier and E. Dauffy-Richard, B. Faivre and V. Godreau for discussion on bird sampling and data analysis, and to Vicky Moore for improving the clarity of manuscript. This study was funded by a grant from the GIP ECOFOR and the Ministries in charge of the Ecology and the Forest.

Chaffinch 77 0 0.2 1.1 1.9 1.5 4.9