Rémy Belmonte
email: remy.belmonte@gmail.com

Ignasi Sau
email: ignasi.sau@lirmm.fr

On the complexity of finding large odd induced subgraphs and odd colorings

Keywords: odd subgraph, odd coloring, rank-width, parameterized complexity, single-exponential algorithm, Exponential Time Hypothesis

We study the complexity of the problems of finding, given a graph G, a largest induced subgraph of G with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition V (G). We call these parameters mos(G) and χ odd (G), respectively. We prove that deciding whether χ odd (G) ≤ q is polynomial-time solvable if q ≤ 2, and NP-complete otherwise. We provide algorithms in time 2 O(rw) •n O(1) and 2 O(q•rw) •n O(1) to compute mos(G) and to decide whether χ odd (G) ≤ q on n-vertex graphs of rank-width at most rw, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.

Introduction

Gallai proved, around 60 years ago, that the vertex set of every graph can be partitioned (in polynomial time) into two sets, each of them inducing a subgraph in which all vertices have even degree (cf. [START_REF] Lovász | Combinatorial Problems and Exercises[END_REF]Exercise 5.19]). Let us call such a subgraph an even subgraph, and an odd subgraph is defined similarly. Hence, every graph G contains an even induced subgraph with at least |V (G)|/2 vertices. The analogous properties for odd subgraphs seem to be more elusive. For a graph G, let mos(G) and χ odd (G) be the order of a largest odd induced subgraph of G and the minimum number of odd induced subgraphs of G that partition V (G), respectively. Note that for χ odd (G) to be well-defined, each connected component of G must have even order.

Concerning the former parameter, the following long-standing -and still openconjecture is cited as "part of the graph theory folklore" by Caro [START_REF] Caro | On induced subgraphs with odd degrees[END_REF]: there exists a positive constant c such that every graph G without isolated vertices satisfies mos(G) ≥ c • |V (G)|. In the following discussion we only consider graphs without isolated vertices. Caro [START_REF] Caro | On induced subgraphs with odd degrees[END_REF] proved that mos(G) ≥ (1 -o( 1)) n/6 where n = |V (G)|, and Scott [START_REF] Scott | Large induced subgraphs with all degrees odd[END_REF] improved this bound to cn log n for some c > 0. The conjecture has been proved for particular graph classes, such as trees [START_REF] Radcliffe | Every tree contains a large induced subgraph with all degrees odd[END_REF], graphs of bounded chromatic number [START_REF] Scott | Large induced subgraphs with all degrees odd[END_REF], graphs of maximum degree three [START_REF] Berman | Odd induced subgraphs in graphs of maximum degree three[END_REF], and graphs of tree-width at most two [START_REF] Hou | Odd induced subgraphs in graphs with treewidth at most two[END_REF], also obtaining best possible constants.

As for the complexity of computing mos(G), Cai and Yang [START_REF] Cai | Parameterized complexity of even/odd subgraph problems[END_REF] studied, among other problems, two parameterized versions of this problem, and their reductions imply that it is NP-hard. They also prove the NP-hardness of computing the largest size of an even induced subgraph of a graph G, denoted mes(G). As a follow-up of [START_REF] Cai | Parameterized complexity of even/odd subgraph problems[END_REF], related problems were studied by Cygan et al. [START_REF] Cygan | Parameterized Complexity of Eulerian Deletion Problems[END_REF] and Goyal et al. [START_REF] Goyal | Finding even subgraphs even faster[END_REF].

The parameter χ odd , which we call the odd chromatic number, has attracted much less interest in the literature. To the best of our knowledge, it has only been considered by Scott [START_REF] Scott | On induced subgraphs with all degrees odd[END_REF], who defined it (using a different notation) and proved that the necessary condition discussed above for χ odd (G) to be well-defined is also sufficient. He also provided lower and upper bounds on the maximum value of χ odd (G) over all n-vertex graphs. In particular, there are graphs G for which χ odd (G) = Ω( √ n).

Our contribution. In this article we mostly focus on computational aspects of the parameters mos and χ odd . Note that, given a graph G, deciding whether χ odd (G) ≤ 1 is trivial. We prove that deciding whether χ odd (G) ≤ q is NPcomplete for every q ≥ 3 using a reduction from q-Coloring. We obtain a dichotomy on the complexity of computing χ odd by showing that deciding whether χ odd (G) ≤ 2 can be solved in polynomial time, through a reduction to the existence of a feasible solution to a system of linear equations over GF [START_REF] Bergougnoux | More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints[END_REF].

Given the NP-hardness of computing both parameters, we are interested in its parameterized complexity [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF], namely in identifying relevant parameters k that allow for FPT algorithms, that is, algorithms running in time f (k) • n O (1) for some computable function f . Since the natural parameter, that is, the solution size, for mos has been studied by Cai and Yang [START_REF] Cai | Parameterized complexity of even/odd subgraph problems[END_REF] (and its dual as well), and for χ odd the problem is para-NP-hard by our hardness results, we rather focus on structural parameters. Two of the most successful ones are definitely treewidth and clique-width, or its parametrically equivalent parameter rank-width introduced by Oum and Seymour [START_REF] Oum | Approximating clique-width and branch-width[END_REF]. This latter parameter is stronger than treewidth, in the sense that graph classes of bounded tree-width also have bounded rank-width; see Fig 1 . We present algorithms running in time 2 O(rw) • n O (1) for computing mes(G) and mos(G) for an n-vertex graph G given along with a decomposition tree of width at most rw, and an algorithm in time 2 O(q•rw) • n O (1) for deciding whether χ odd (G) ≤ q. These algorithms are inspired by the ones of Bui-Xuan et al. [START_REF] Bui-Xuan | H-join decomposable graphs and algorithms with runtime single exponential in rankwidth[END_REF][START_REF] Bui-Xuan | Boolean-width of graphs[END_REF] to solve Maximum Independent Set parameterized by rank-width and boolean-width, respectively. To the best of our knowledge, our algorithms are the first ones parameterized by rank-width for an NP-hard problem running in time 2 o(rw 2 ) • n O (1) [START_REF] Bergougnoux | Rank based approach on graphs with structured neighborhood[END_REF][START_REF] Bui-Xuan | H-join decomposable graphs and algorithms with runtime single exponential in rankwidth[END_REF][START_REF] Ganian | Better algorithms for satisfiability problems for formulas of bounded rank-width[END_REF][START_REF] Ganian | A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width[END_REF][START_REF] Oum | Rank-width: Algorithmic and structural results[END_REF]. We also show that the dependency on rank-width of the above algorithms is asymptotically optimal under the Exponential Time Hypothesis (ETH) of Impagliazzo et al. [START_REF] Impagliazzo | On the Complexity of k-SAT[END_REF][START_REF] Impagliazzo | Which Problems Have Strongly Exponential Complexity[END_REF]. For this, it suffices to obtain a linear NP-hardness reduction from a problem for which a subexponential algorithm does not exist under the ETH. While our reduction to decide whether χ odd (G) ≤ q already satisfies this property, the NP-hardness proof of Cai and Yang [START_REF] Cai | Parameterized complexity of even/odd subgraph problems[END_REF] for computing mes(G) and mos(G), which is from the Exact Odd Set problem [START_REF] Downey | The parametrized complexity of some fundamental problems in coding theory[END_REF], has a quadratic blow-up, so only a lower bound of 2 o( √ n) can be deduced from it. Motivated by this, we present linear NP-hardness reductions from 2in3-Sat to the problems of computing mes(G) and mos(G). The reduction itself is not very complicated, but the correctness proof requires some non-trivial arguments 3 .

Finally, motivated by the complexity of computing these parameters, we obtain two tight bounds on their values. We first prove that for every graph G with all components of even order, χ odd (G) ≤ tw(G) + 1, where tw(G) denotes the tree-width of G. This result improves the best known lower bound on a parameter defined by Hou et al. [START_REF] Hou | Odd induced subgraphs in graphs with treewidth at most two[END_REF] (cf. Section 5 for the details). On the other hand, we prove that, for every n-vertex graph G such that V (G) can be partitioned into two non-empty sets that are complete to each other (i.e., a join), mos(G)

≥ 2 • n-2 4 .
In particular, this proves the conjecture about the linear size of an odd induced subgraph for cographs, which are the graphs of clique-width two. This adds another graph class to the previous ones for which the conjecture is known to be true [START_REF] Berman | Odd induced subgraphs in graphs of maximum degree three[END_REF][START_REF] Hou | Odd induced subgraphs in graphs with treewidth at most two[END_REF][START_REF] Radcliffe | Every tree contains a large induced subgraph with all degrees odd[END_REF][START_REF] Scott | Large induced subgraphs with all degrees odd[END_REF]. It is interesting to mention that our proof implies that, for a cograph G, χ odd (G) ≤ 3, and this bound is also tight. While for cographs, or equivalently P 4 -free graphs, we have proved that the odd chromatic number is bounded, we also show that it is unbounded for P 5 -free graphs.

Organization. We start with some preliminaries in Section 2. In Section 3 we provide the linear NP-hardness reductions and the polynomial-time algorithm for deciding whether χ odd (G) ≤ 2. The FPT algorithms by rank-width are presented in Section 4, and the tight bounds in Section 5. We conclude the article in Section 6 with a number of open problems and research directions. Additional results for related problems discussed in the conclusions can be found in Appendix A.

Preliminaries

Graphs. We use standard graph-theoretic notation, and we refer the reader to [START_REF] Diestel | Graph Theory[END_REF] for any undefined notation. Let G = (V, E) be a graph, S ⊆ V , and H be a subgraph of G. We denote an edge between u and v by uv. The order of G is

|V |. The degree (resp. open neighborhood, closed neighborhood) of a vertex v ∈ V is denoted by deg(v) (resp. N (v), N [v]
), and we let deg

H (v) = |N (v) ∩ V (H)|. We use the notation G -S = G[V (G) \ S].
The maximum and minimum degree of G are denoted by ∆(G) and δ(G), respectively. We denote by P i the path on i vertices. For two graphs

G 1 and G 2 , with V (G 2 ) ⊆ V (G 1 ), the union of G 1 and G 2 is the graph (V (G 1 ), E(G 1 ) ∪ E(G 2 )
). The operation of contracting an edge uv consists in deleting both u and v and adding a new vertex w with neighborhood N (u) ∪ N (v) \ {u, v}. A graph M is a minor of G if it can be obtained from a subgraph of G by a sequence of edge contractions. For a positive integer k ≥ 3, the k-wheel is the graph obtained from a cycle C on k vertices by adding a new vertex v adjacent to all the vertices of C. A join in a graph G is a partition of V (G) into two non-empty sets V 1 and V 2 such that every vertex in V 1 is adjacent to every vertex in V 2 . For a positive integer i, we denote by [i] the set containing every integer j such that 1 ≤ j ≤ i.

Parameterized complexity. We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions. A parameterized problem is a decision problem whose instances are pairs (x, k) ∈ Σ * × N, where k is called the parameter. A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f , and a constant c such that given an instance I = (x, k), A (called an FPT algorithm) correctly decides whether I ∈ L in time bounded by f (k) • |I| c . A parameterized problem is slice-wise polynomial (XP) if there exists an algorithm A and two computable functions f, g such that given an instance I = (x, k), A (called an XP algorithm) correctly decides whether I ∈ L in time bounded by f (k) • |I| g (k) .

Within parameterized problems, the class W[1] may be seen as the parameterized equivalent to the class NP of classical optimization problems. Without entering into details (see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for the formal definitions), a parameterized problem being W[1]-hard can be seen as a strong evidence that this problem is not FPT. The canonical example of W[1]-hard problem is Independent Set parameterized by the size of the solution. To transfer W [START_REF] Bergougnoux | Rank based approach on graphs with structured neighborhood[END_REF]-hardness from one problem to another, one uses a parameterized reduction, which given an input I = (x, k) of the source problem, computes in time f (k) • |I| c , for some computable function f and a constant c, an equivalent instance I = (x , k ) of the target problem, such that k is bounded by a function depending only on k. An equivalent definition of W [START_REF] Bergougnoux | Rank based approach on graphs with structured neighborhood[END_REF]-hard problem is any problem that admits a parameterized reduction from Independent Set parameterized by the size of the solution.

The Exponential Time Hypothesis (ETH) of Impagliazzo et al. [START_REF] Impagliazzo | On the Complexity of k-SAT[END_REF][START_REF] Impagliazzo | Which Problems Have Strongly Exponential Complexity[END_REF] implies that the 3-Sat problem on n variables cannot be solved in time 2 o(n) . We say that a polynomial reduction from a problem Π 1 to a problem Π 2 , generating an input of size n 2 from an input of size n 1 , is linear if n 2 = O(n 1 ). Clearly, if Π 1 cannot be solved, under the ETH, in time 2 o(n) on inputs of size n, and there exists a linear reduction from Π 1 to Π 2 , then Π 2 cannot either.

Width parameters. In this article we mention several width parameters of graphs, such as tree-width, rank-width, clique-width, or boolean-width. However, since we only deal with rank-width in our algorithms (cf. Section 4), we give only the definition of this parameter here.

A decomposition tree of a graph G is a pair (T, δ) where T is a full binary tree (i.e., T is rooted and every non-leaf node has two children) and δ is a bijection between the leaf set of T and the vertex set of G. For a node w of T , we denote by V w the subset of V (G) in bijection -via δ-with the leaves of the subtree of T rooted at w. We say that the decomposition defines the cut V w , V w . The rank-width of a decomposition tree (T, δ) of a graph G, denoted by rw(T, δ), is the maximum over all w ∈ V (T ) of the rank of the adjacency matrix of the bipartite graph G[V w , V w ]. The rank-width of G, denoted by rw(G), is the minimum rw(T, δ) over all decomposition trees (T, δ) of G.

Definition of the problems. A graph is called odd (resp. even) if every vertex has odd (resp. even) degree. The Maximum Odd Subgraph (resp. Maximum Even Subgraph) problem consists in, given a graph G, determining the maximum order of an odd (resp. even) induced subgraph of G, that is, mos(G) (resp. mes(G)). An odd q-coloring of a graph G = (V, E) is a set of q odd induced subgraphs H 1 , . . . , H q of G such that V (H 1 ), • • • , V (H q ) is a partition of V . The Odd q-Coloring problem consists in determining whether an input graph G admits an odd q-coloring. In the Odd Chromatic Number problem, the objective is to determine the smallest integer q such that an input graph G admits an odd q-coloring.

Linear reductions and a polynomial-time algorithm

We first present the linear reductions for Maximum Even Subgraph and Maximum Odd Subgraph, and then for Odd q-Coloring for q ≥ 3. Proof: The first statement has been already proved by Cai and Yang [START_REF] Cai | Parameterized complexity of even/odd subgraph problems[END_REF], so we focus on the second one. We first deal with Maximum Even Subgraph, and we will then show how to deduce the hardness of Maximum Odd Subgraph with a simple modification.

In the 1in3-Sat (resp. 2in3-Sat) problem, we are given a 3-Sat formula, and the objective is to decide whether there exists an assignment of the variables such that every clause contains exactly one (resp. two) true literal(s). Porschen et al. [START_REF] Porschen | XSAT and NAE-SAT of linear CNF classes[END_REF]Lemma 5] showed that 1in3-Sat is NP-hard even if each clause contains exactly three variables and each variable occurs in exactly three clauses. Since their reduction from 3-Sat is linear, it follows that this restricted version of 1in3-Sat cannot be solved in time 2 o(n) under the ETH, where n is the number of variables. By taking such an instance of 1in3-Sat and building an equivalent instance of 2in3-Sat by negating all the literals in every clause, it follows that 2in3-Sat cannot be solved in time 2 o(n) under the ETH, even if each clause contains exactly three variables and each variable occurs in exactly three clauses. We denote this version of 2in3-Sat by 2in3-Sat 3 .

We proceed to present a linear reduction from 2in3-Sat 3 to Maximum Even Subgraph. Given an instance ϕ of 2in3-Sat 3 with n variables and m clauses, we build an instance G of Maximum Even Subgraph as follows (see Fig. 2 for an illustration). Let the variables and clauses of ϕ be x 1 , . . . , x n and c 1 , . . . , c m , respectively. Note that by the definition of the 2in3-Sat 3 problem, we have that n = m. Let p ≥ 88 be a fixed even integer. For every variable x i of ϕ, we add to G a variable gadget, with vertex set X i , consisting of a path P i on p vertices with endpoints s i and t i , two vertices x i and xi (corresponding to variable x i and its negation, respectively), and the five edges s i x i , s i xi , t i x i , t i xi , and

x i xi . c 1 j c 2 j v 1,1 j,x i x i xi xk x x x k s i t i P i s k t k P k s t P c j = (x i ∨ x k ∨ x ) v 1,2 j,x i v 2,2 j,x i v 2,1 j,x i v 1,1 j,x k v 1,2 j,x k v 2,1 j,x k v 2,2 j,x k v 2,1 j,x v 2,2 j,x v 1,1 j,x v 1,2 j,x X i C j Fig. 2. Graph G built in the proof of Theorem 1, for a clause cj = (xi ∨ x k ∨ x ).
For every clause c j = ( 1 ∨ 2 ∨ 3 ) of ϕ, where 1 , 2 , 3 are the literals of c j , we add to G two vertices c 1 j and c 2 j . For i ∈ [3] and k ∈ [START_REF] Bergougnoux | More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints[END_REF], we add a path on four vertices joining vertices c k j and i , where the two internal vertices are new ones. For every such a path, we denote its internal vertices by v k,1 j, i and v k,2 j, i , where v k,1 j, i is the one adjacent to c k j ; see Fig. 2. We denote by C j the set of 14 vertices of G consisting of c 1 j , c 2 j , and the 12 internal vertices of the six paths joining them to the literals. This concludes the construction of G. Note that |V (G)| = (p + 16)n, hence it is indeed a linear reduction. We claim that ϕ is a positive instance of 2in3-Sat 3 if and only if mes(G) ≥ (p + 13)n.

Assume first that that ϕ is a positive instance of 2in3-Sat 3 , and let ψ be the corresponding assignment of the variables. We proceed to define an even induced subgraph H of G, with |V (H)| = (p + 13)n, as follows. For every variable gadget X i of G, we include in H the whole path P i and either x i or xi depending on whether ψ sets variable x i to true or false, respectively. For every clause c j = ( 1 ∨ 2 ∨ 3 ) of ϕ, suppose without loss of generality that ψ sets 1 and 2 to true, and 3 to false. We include in H vertices c 1 j , c 2 j and, out of the 12 internal vertices of the paths, we add to H all of them except for the two vertices adjacent to c 1 j and c 2 j in the paths joining them to 3 , that is, the following set of 10 vertices: 3 for an illustration with 3 = x k . It can be verified that H is indeed an even subgraph and that |V (H)| = (p + 1)n + 12n = (p + 13)n. Conversely, suppose now that G contains an even subgraph H with |V (H)| = mes(G) ≥ (p + 13)n. We state some properties of H through a sequence of claims.

{v k,r j, i : i, k, r ∈ [2]} ∪ {v 1,2 j, 3 , v 2,2 j, 3 }. See Fig.
c 1 j c 2 j v 1,1 j,x i x i xi xk x x x k s i t i P i s k t k P k s t P c j = (x i ∨ x k ∨ x ) v 1,2 j,x i v 2,2 j,x i v 2,1 j,x i v 1,1 j,x k v 1,2 j,x k v 2,1 j,x k v 2,2 j,x k v 2,1 j,x v 2,2 j,x v 1,1 j,x v 1,2 j,x X i C j

Claim 1 For every

i ∈ [n], if x i ∈ V (H) and xi ∈ V (H), then |V (H) ∩ X i | ≤ p/2 + 2, and if x i / ∈ V (H) and xi / ∈ V (H), then |V (H) ∩ X i | ≤ p/2,
Proof: Suppose first that x i ∈ V (H) and xi ∈ V (H). H cannot contain any pair of adjacent vertices of P i , as this would result in a vertex of degree one or three in H, which implies that

|V (H) ∩ V (P i )| ≤ p/2, and thus |V (H) ∩ X i | ≤ p/2 + 2. Suppose now that x i / ∈ V (H) and xi / ∈ V (H). If V (P i ) ⊆ V (H), then deg H (s i ) = 1, so similarly as before we get that |V (H) ∩ X i | ≤ p/2. Claim 2 For every i ∈ [n], either x i ∈ V (H) or xi ∈ V (H).
Proof: Assuming that the claim is not true, we will build from H another even induced subgraph

H of G with |V (H )| > |V (H)|, contradicting the fact that |V (H)| = mes(G). For i ∈ [n], let J G i ⊆ [n] (resp. J H i ⊆ [n]
) be the set of indices j such that there exists at least one edge in G (resp. in H) between X i and C j . We define H according to the following iterative procedure, starting with H = H:

1. For every i ∈ [n] such that exactly one of x i and xi belongs to H, say i , we "double" the paths from X i to C j for every j ∈ J H i (note that some of these paths may already be "doubled" in H ). Formally, for every j

∈ J H i , we replace H with H ∪ G[{ i , v 1,1 j, i , v 1,2 j, i , v 2,1 j, i , v 2,2 j, i , c 1 j , c 2 j }]. 2. For every i ∈ [n] such that |V (H) ∩ {x i , xi }| ∈ {0, 2}, we first delete from H , if any, all the vertices in C j for every index j ∈ J G i , that is, we replace H with H -j∈J G i C j . Finally, we replace H with (H -{x i }) ∪ G[{x i } ∪ V (P i )],
that is, we delete xi and we add x i (if it did not already belong to H ) and the whole path P i . 3. Note that after Step 2 above, the degree in H of all vertices in X i is even for every i ∈ [n]. Note also that, since in H all the degrees were even and in

Step 1 only paths that already existed in H were doubled, no vertex in a set C j can have degree one in H . However, it is possible that a vertex in a set C j , namely both c 1 j and c 2 j , has degree three in H (recall that every clause contains exactly three literals). Let j ∈ [n] be such an index, and let i j ∈ [n] be an arbitrarily chosen index such that H contains edges from literal ij to C j . We guarantee that all the degrees in H are even by removing from H the internal vertices of the paths from ij to c 1 j and c 2 j , that is, we replace H with H -{v 1,1

j, i j , v 1,2 j, i j , v 2,1 j, i j , v 2,2 j, i j }.
Let H be the subgraph of G obtained at the end of the above procedure. By the discussion above, H is indeed an even induced subgraph. It remains to prove that |V (H )| > |V (H)|. We analyze each of the three steps separately.

Step 1 only adds new vertices to H , so we can focus on Steps 2 and 3. Let i ∈ [n] be an index considered in Step 2, and let H 1 and H 2 be the current graphs before and after applying the procedure for index i, respectively. Since

|V (H) ∩ {x i , xi }| ∈ {0, 2}, Claim 1 implies that |V (H 1 ) ∩ X i | = |V (H) ∩ X i | ≤ p/2 + 2. On the other hand, from the definition of Step 2 it follows that |V (H 2 ) ∩ X i | = p + 1.
Since every variable appears in exactly three clauses of ϕ,

|J G i | = 3, so we have that j∈J G i |C j | = 42
, so in the first part of Step 2 at most 42 vertices are removed from H 1 in order to obtain H 2 . Therefore,

|V (H 2 )| -|V (H 1 )| = (|V (H 2 ) ∩ X i | -|V (H 1 ) ∩ X i |) - j∈J G i |V (H 1 ) ∩ C j | ≥ (p + 1) -(p/2 + 2) -42 = p/2 -43 > 0,
where we have used that p ≥ 88.

Let i ∈ [n] be an index considered in Step 3, and let again H 1 and H 2 be the current graphs before and after applying the procedure for index i, respectively. Let j ∈ [n] be such that deg H1 (c 1 j ) = deg H1 (c 2 j ) = 3 and let c j = ( 1 ∨ 2 ∨ 3 ); see Fig. 4 for an illustration of the analysis. Since necessarily Note that, since we assume that the claim is not true, that is, that there exists some index i ∈ [n] such that |V (H) ∩ {x i , xi }| ∈ {0, 2}, Step 2 in the construction of H has been applied at least once, therefore |V (H )| > |V (H)| and the claim follows.

deg H (c 1 j ) = deg H (c 2 j ) = 2, but each of 1 , 2 , 3 has a neighbor in C j in the graph H (as otherwise deg H1 (c 1 j ) < 3), it follows that { 1 , 2 , 3 , c 1 j , c 2 j } ⊆ V (H)
c 1 j c 2 j 1 2 3 H 1 c 1 j c 2 j 1 2 3 H 2 c 1 j c 2

Claim 3 For every

i ∈ [n], V (P i ) ⊆ V (H). Proof: Consider an arbitrary i ∈ [n]. By Claim 2, either x i ∈ V (H) or xi ∈ V (H). Assume without loss of generality that x i ∈ V (H). If V (P i ) V (H), then the graph H defined as H ∪ G[{x i } ∪ V (P i )] is an even induced subgraph of G with |V (H )| > |V (H)|, a contradiction to the hypothesis that |V (H)| = mes(G). Claim 4 For every j ∈ [n], |V (H) ∩ C j | = 12.
Proof: If H contained at least 13 vertices in C j , then at least one of c 1 j and c 2 j would have degree three in H (see Fig. 2), a contradiction. On the other hand, Claims 2 and 3 imply that By Claim 2, the following assignment ψ of the variables is well-defined: for i ∈ [n], ψ sets variable x i to true if and only if vertex x i belongs to H. The following claim concludes the proof of the theorem for the even case.

|V (H) ∩ i∈[n] X i | = (p +
(c 1 j ) = deg H (c 2 j ) = 2. Moreover, since deg H (c 1 j ) = deg H (c 2 j ) = 2 and deg H (v) ∈ {0, 2} for every v ∈ C j ∩ V (H), necessarily C j \ V (H) = {v 1,1 j, i , v 2,1 j, i } for some i ∈ [3]
. Assume without loss of generality that i = 3. Then it follows that 1 , 2 ∈ V (H) and that

3 / ∈ V (H). Indeed, if 1 / ∈ V (H) (the proof for 2 is symmetric), the fact that v 1,1 j, 1 ∈ V (H) implies that deg H (v 1,2 j, 1 ) = 1, a contradiction. Similarly, if 3 ∈ V (H), the fact that v 1,1 j, 3 / ∈ V (H) implies that deg H (v 1,2 j, 3 ) = 1
, a contradiction as well. Therefore, by the definition of ψ, it follows that exactly two of the literals of c j (namely, 1 and 2 ) are set to true by ψ.

Note that the graph G constructed above to prove the hardness of Maximum Even Subgraph has bounded maximum degree, namely ∆(G) ≤ 9.

To prove the statement for Maximum Odd Subgraph, we present a simple linear reduction from Maximum Even Subgraph that uses a trick of Cai and Yang [START_REF] Cai | Parameterized complexity of even/odd subgraph problems[END_REF]Theorem 4.5]. Namely, let G be an instance of Maximum Even Subgraph as constructed by the above reduction, and recall that mes(G) ≤ (p + 13)n =: k. By adding an isolated vertex if needed, we may assume that k is even. We build from G an instance G of Maximum Odd Subgraph by adding a (k + 1)-wheel W and making an arbitrary vertex of W adjacent to all the vertices of G. Note that this is indeed a linear reduction. It can be easily checked that mos(G ) ≥ 2k + 1 if and only if mes(G) ≥ k, and the theorem follows.

Theorem 2. For every integer q ≥ 3, given a graph G on n vertices, determining whether χ odd (G) ≤ q is NP-complete and, moreover, cannot be solved in time 2 o(n) unless the ETH fails.

Proof: Membership in NP is clear. For every integer q ≥ 3, we present a linear reduction from the q-Coloring problem, which is well-known to be NP-hard and not solvable in time 2 o(n) on n-vertex graphs unless the ETH fails [START_REF] Impagliazzo | On the Complexity of k-SAT[END_REF][START_REF] Impagliazzo | Which Problems Have Strongly Exponential Complexity[END_REF]. We will use the fact that any connected graph G = (V, E) such that |V | + |E| is even admits an orientation of E such that, in the resulting digraph, all the vertex indegrees are odd; we call such an orientation an odd orientation. Moreover, an odd orientation can be found in polynomial time (for a proof, see for instance [START_REF] Frank | An orientation theorem with parity conditions[END_REF]).

Given an instance G = (V, E) of q-Coloring, such that G is connected, we build from G an instance G q of Odd q-Coloring as follows. First, if |V | + |E| is odd, we arbitrarily select a vertex v ∈ V and add a triangle on three new vertices v 1 , v 2 , v 3 and the edge vv 1 . Note that the resulting graph G = (V , E ) is q-colorable for q ≥ 3 if and only if G is, and that |V | + |E | is even. Hence, E admits an odd orientation φ; see Fig. 5(a)-(b). We let G q be the graph obtained from G by subdividing every edge once; see Fig. 5(c). Note that the size of G q depends linearly on the size of G, as required. We claim that χ(G) ≤ q if and only if Assume first that we are given a proper q-coloring c : V → [q], which can trivially be extended to a proper q-coloring of G . We define an odd q-coloring c odd of G q as follows.

χ odd (G q ) ≤ q. G (a) (b) (c) (d) G • G G •
If v ∈ V (G q
) is an original vertex of V , we set c odd (v) = c(v). Otherwise, if v is a subdivision vertex between two vertices u and w of V , we set c odd (v) = c(u) if edge uw is oriented toward u in φ, and c odd (v) = c(w) otherwise; see Fig. 5(d). It can be easily verified that c odd is indeed an odd q-coloring of G q . Conversely, let c odd : V (G q ) → [q] be an odd q-coloring of G q , let uw be an edge of G , and let v be the subdivision vertex in G q between u and w. If follows that c odd (u) = c odd (w), as otherwise vertex v would have degree zero or two in its color class. Therefore, letting c(v) = c odd (v) for every vertex v ∈ V (G) defines a proper q-coloring of G, and the theorem follows.

Theorem 2 establishes the NP-hardness of Odd q-Coloring for every q ≥ 3. On the other hand, the Odd 1-Coloring is trivial, as for any graph G, χ odd (G) ≤ 1 if and only if G is an odd graph itself. Therefore, the only remaining case is Odd 2-Coloring. In the next theorem we prove that this problem can be solved in polynomial time. Proof: We will express the Odd 2-Coloring problem as the existence of a feasible solution to a system of linear equations over the binary field, which can be determined in polynomial time using, for instance, Gaussian elimination. Given an instance G = (V, E) of Odd 2-Coloring, let its vertices be labeled v 1 , . . . , v n . For every vertex v i ∈ V we create a binary variable x i , and for every edge v i v j ∈ E, we create a binary variable x i,j . The interpretation of these two types of variables is quite different. Namely, for a vertex variable x i , its value corresponds to the color (either 0 or 1) assigned to vertex v i . On the other hand, the value of an edge variable corresponds to whether this edge belongs to a monochromatic subgraph, that is, to whether both its endvertices get the same color. In this case, its value is 1, and 0 otherwise. We guarantee this latter property by adding the following set of linear equations:

x i + x j + x i,j ≡ 1 for every edge v i v j ∈ E. ( 1
)
To guarantee that the degree of every vertex in each of the two monochromatic subgraphs is odd, we add the following set of linear equations (for an edge variable x i,j , to simplify the notation we interpret x j,i = x i,j ):

j:vj ∈N (vi) x i,j ≡ 1 for every vertex v i ∈ V . ( 2
)
Note that by Equation ( 1), only monochromatic edges contribute to the sum of Equation (2). Therefore, the above discussion implies that χ odd (G) ≤ 2 if and only if the system of linear equations given by Equations ( 1) and ( 2) admits a feasible solution, and the theorem follows.

Note that the Even 2-Coloring problem could be formulated in a similar way, just by replacing Equation (2) with j:vj ∈N (vi) x i,j ≡ 0. However, this is not that interesting, since all the instances of Even 2-Coloring are positive [START_REF] Lovász | Combinatorial Problems and Exercises[END_REF].

Dynamic programming algorithms

In this section, we present FPT algorithms for Maximum Odd/Even Subgraph and Odd q-Coloring, parameterized by the rank-width of the input graph. The algorithms are similar to those of Bui-Xuan et al. [START_REF] Bui-Xuan | H-join decomposable graphs and algorithms with runtime single exponential in rankwidth[END_REF][START_REF] Bui-Xuan | Boolean-width of graphs[END_REF] for Maximum Independent Set parameterized by rank-width and boolean-width, respectively, and even closer to the one by Bui-Xuan et al. [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF] for so-called locally checkable vertex partitioning problems, in particular for Dominating Set. There are however two key differences with our algorithms. First, while partial solutions for Maximum Independent Set are, themselves, independent sets, this is not true in general for odd subgraphs, where partial solutions may consist in a subgraph some vertices of which have even degree. Those vertices will impose some extra constraints on the remainder of the solution. The second difference is that, while the equivalence classes of [START_REF] Bui-Xuan | H-join decomposable graphs and algorithms with runtime single exponential in rankwidth[END_REF] and [START_REF] Bui-Xuan | Boolean-width of graphs[END_REF] are based on neighborhoods of vertex sets, those for Maximum Odd Subgraph only require "neighborhoods modulo 2". This will allow us to consider only 2 O(rw) equivalence classes, compared to 2 O(rw 2 ) classes used in [START_REF] Bui-Xuan | H-join decomposable graphs and algorithms with runtime single exponential in rankwidth[END_REF] for Maximum Independent Set.

Throughout this section, we will rely on the notion of "neighborhood modulo 2" of a set of vertices, defined as follows. Given a graph G and X ⊆ V (G), the neighborhood of X modulo 2, denoted by N 2 (X), is the set u∈X (N (u)), where the operator denotes the symmetric difference. Note that N 2 (X) is exactly the set of vertices in V (G) \ X that have an odd number of neighbors in X. The results in this section are stated using the O * notation, which hides polynomial factors in the input size. Proof: We give a dynamic programming over the given decomposition tree (T, L). Recall that there is a bijection between the leaves of T and V (G), and that each edge of T corresponds to a cut (A, A) of G. We begin by defining the equivalence relation over subsets of A, given a cut (A, A): two sets X, Y ⊆ V (G) are odd neighborhood equivalent with regard to A, denoted by

X ≡ A 2 Y , if N 2 (X) \ A = N 2 (Y ) \ A.
Then, given a row basis B of the adjacency matrix of (A, A) over GF [START_REF] Bergougnoux | More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints[END_REF], where we interpret a vertex set as the vector corresponding to its vertices, we define the representative of a set X ⊆ A as the the unique set of vertices R A (X) ⊆ A such that R A (X) ⊆ B and X ≡ A 2 R A (X). Observe that since (A, A) is a cut of (T, L), its adjacency matrix has rank at most rw(G), and therefore |R A (X)| ≤ rw(G). This implies, in particular, that there are at most 2 rw(G) distinct representatives for subsets of a given set A.

We are now ready to define the tables of our algorithm. Given an edge e of (T, L) and its associated cut (A, A) of G, we store in table T A , for every pair R, R of representatives of subsets of A and A, respectively, a largest set S ⊆ A such that S is odd neighborhood equivalent to R, and all the vertices that have even degree in G[S] is exactly the set N 2 (R ) ∩ S. More formally:

( ) T A [R, R ] = maxset S⊆A {S ≡ A 2 R ∧ {v ∈ S : |N (v) ∩ S| is even} = N 2 (R ) ∩ S},
where the notation 'maxset' indicates a largest set that satisfies the conditions. In cases where edge e is incident with a leaf, the cut associated with e is of the form ({u}, V (G) \ {u}). We assume u is not an isolated vertex, as such vertices never belong to an odd subgraph. We set Given an edge e of (T, L) such that the tables of both edges incident with one endvertex of e, say f, f , have been computed, we compute the table of e as follows. Let us denote by (A, A), (X, X), and (Y, Y ) the cuts associated with e, f , and f , respectively. For each pair of representatives R A , R A of the cut (A, A), the value of

T {u} [∅, ∅] = T {u} [∅, {v}] = ∅,
T A [R A , R A ] is the largest T X [R X , R X ] ∪ T Y [R Y , R Y ], such that R X , R X , R Y ,
and R Y satisfy the following conditions with regard to R A and R A :

(i) R A ≡ A 2 R X R Y , (ii) R X ≡ X 2 R A R Y , and (ii') R Y ≡ Y 2 R A R X .
We proceed with this computation, starting from the leaves, in a bottom-up manner, having previously rooted T by choosing an arbitrary edge, subdividing it, and making the newly created vertex the root of T . Observe that in the final stage of the algorithm, when the tables of both edges f, f incident with the root have been computed, we compute the table for the root node as described above, with A = ∅, since X ∪ Y = V (G) in this case. Of the three conditions described above, condition (i) becomes trivial, since R A = ∅, and conditions (ii) and (ii') simplify to R X ≡ X 2 R Y , and R Y ≡ Y 2 R X , respectively. This immediately implies that, provided the tables are updated correctly, the table for the root node will indeed contain an optimal solution.

We first observe that since, as noted above, there are at most 2 rw representatives on each side of each cut, the choices of R X , R Y and R A uniquely determines R X , R Y and R A through equations (i), (ii), and (ii'), and computing new tables can be carried out in time O * (2 3rw ). Since there are O(|V (G)|) nodes in the decomposition, the running-time is O * (2 3rw ) as well, as desired.

It now remains to prove that the algorithm correctly computes an optimal solution. The correctness of the tables for the leaves of T follows from their description. We now prove by induction that the tables are correct for internal edges of T as well. Let us assume T X and T Y have been fully and correctly computed for all possible representatives R X , R X , R Y , and R Y as per the description above.

Finally, we argue that if T X and T Y are computed correctly, then so is T A . Observe first that, for every (R X , R X ) and (R Y , R Y ) satisfying conditions (i),(ii) and (ii'),

S = T X [R X , R X ] ∪ T Y [R Y , R Y ] satisfies S ≡ A 2 R
A due to condition (I), and {v ∈ S : |N (v)∩S| is even} = N 2 (R A )∩S} due to conditions (ii) and (ii'). In other words, S satisfies ( ), bar possibly the maximality condition. To complete the proof that the tables are computed correctly, we argue that given any two representatives R A and R A of A and A, respectively, there exist representatives R X , R X , R Y , and R Y of X, X, Y , and Y , respectively, that satisfy conditions (i), (ii), and (ii'), and such that T

X [R X , R X ]∪T Y [R Y , R Y ] is a largest set that satisfies ( ) with respect to (R A , R A ). Let R X , R X , R Y , and R Y be representatives such that T A [R A , R A ] = T X [R X , R X ] ∪ T Y [R Y , R Y ] = S,
and let S X and S Y denote S ∩ X and S ∩ Y , respectively. Note that, since X and Y form a partition of A, S X and S Y form a partition of S, which implies S = S X ∪ S Y = S X S Y . We first show that S indeed satisfies ( ) with respect to (A, A), i.e., S ≡ A 2 R A and {v ∈ S :

|N (v) ∩ S| is even} = N 2 (R A ) ∩ S.
For the first of those two conditions, combining it with the fact that S = S X ∪ S Y = S X S Y , we only need to prove that S X S Y ≡ A 2 R X R Y . Observe first that, since X and Y form a partition of A, we have that for every vertex

v ∈ A, |N (v) ∩ A| = |N (v) ∩ X| + |N (v) ∩ Y |. Therefore, for every sets X , X ⊆ X and Y , Y ⊆ Y , it holds that if X ≡ X 2 X and Y ≡ Y 2 Y , then X Y ≡ A 2 X Y . From the definition of representative we obtain that S ≡ A 2 S X S Y ≡ A 2 R X R Y , as desired.
Let us now consider the second condition, i.e., {v ∈ S :

|N (v) ∩ S| is even} = N 2 (R A ) ∩ S. Let v be a vertex in S X . If |N (v) ∩ S|
is even, then at least one of the following cases holds:

• |N (v) ∩ S X | is even and v ∈ N 2 (S Y ). Since |N (v) ∩ S X | is even, we obtain from ( ) in T X that v ∈ N 2 (R X ), which when combined with (ii) implies v ∈ N 2 (R A ) N 2 (S Y ). Since v ∈ N 2 (S Y ), it follows that v ∈ N 2 (R A ), as desired. • |N (v) ∩ S X | is odd and v ∈ N 2 (S Y ). Symmetrically to the case above, we have that v ∈ N 2 (R X ), hence v ∈ N 2 (R A ) N 2 (S Y ) from (ii), and since v ∈ N 2 (S Y ), it follows that v ∈ N 2 (R A ), as desired.
The case where v ∈ S Y is proved similarly, replacing condition (ii) with (ii'). Therefore, {v ∈ S :

|N (v) ∩ S| is even} ⊆ S ∩ N 2 (R A ). Now, let v be a vertex in S X ∩ N 2 (R A ). From (ii), we obtain that v ∈ N 2 (S ∩ X) if and only if v ∈ N 2 (S Y ). Since T X satisfies ( ), it holds that v ∈ N 2 (S ∩ X) if and only if |N (v) ∩ S X | is even, and therefore ∈ N 2 (S Y ) if and only if |N (v) ∩ S X | is even. Therefore, |N (v) ∩ S| = |N (v) ∩ S X | + |N (v) ∩ S Y | is even, as desired.
As above, the case where v ∈ S Y is proved similarly, replacing condition (ii) with (ii'). Therefore, {v ∈ S :

|N (v) ∩ S| is even} = S ∩ N 2 (R A ).
Finally, we prove the maximality of S among all those sets that satisfy ( ) with respect to (R A , R A ). Let us assume for a contradiction that there exists S * that satisfies ( ) with respect to (R A , R A ) and such that |S * | > |S|. Let S * X and S * Y denote S * ∩ X and S * ∩ Y , respectively. Observe that S * X and S * Y satisfy ( ) with respect to some pairs of representatives (R X , R X ) and (R Y , R Y ), respectively. In addition, observe that since S satisfies ( ) with respect to (R A , R A ), it follows that S, S X , and S Y satisfy conditions (i), (ii), and (ii') with respect to (R A , R A ), contradicting the assumption that T X and T Y were computed correctly.

Small variations of the algorithm of Theorem 4 allow us to prove the following two theorems. Theorem 5. Given a graph G along with a decomposition tree of rank-width rw, the Maximum Even Subgraph problem can be solved in time O * (2 3rw ).

Proof:

The algorithm and its proof are nearly identical to the ones for Maximum Odd Subgraph, replacing condition ( ) with

T A [R, R ] = max S⊆A {|S| : S ≡ A 2 R ∧ {v ∈ S : |N (v) ∩ S| is odd} = S ∩ N 2 (R )},
and the leaves are instead defined as

T {u} [∅, ∅] = T {u} [∅, {v}] = ∅ and T {u} [{u}, ∅] = {u}. T {u} [{u}, {v}]
is left empty, due to there being no odd subgraph of G[{u}] with the same neighborhood as {u} in G -{u}.

Theorem 6. Given a graph G along with a decomposition tree of rank-width w, the Odd q-Coloring problem can be solved in time O * (2 O(q•rw) ).

Proof:

The algorithm is nearly identical to the one for Maximum Odd Subgraph, with the exception that the tables are indexed by q pairs of representatives R 1 , R 1 , . . . , R q , R q , associating set S i with each pair (R i , R i ), with the additional constraint that q i=1 S i = A. Since each table has at most 2 2•q•rw entries, and computing a new table from two given ones takes time polynomial in the number of entries, we obtain the desired running time.

Tight bounds

In this section we provide two tight bounds concerning odd induced subgraphs and odd colorings. Namely, we first provide in Theorem 7 a tight upper bound on the odd chromatic number in terms of tree-width, and then we provide in Theorem 8 a tight lower bound on the size of a maximum odd induced subgraph for graphs that admit a join.

Theorem 7.

For every graph G with all components of even order we have that χ odd (G) ≤ tw(G) + 1, and this bound is tight.

Proof: Scott proved [42, Corollary 3] that every graph G with all components of even order admits a vertex partition such that every vertex class induces a tree with all degrees odd. Consider such a vertex partition, and let G be the graph obtained from G by contracting each of the trees to a single vertex. Since G is a minor of G, we have that tw(G ) ≤ tw(G). Now note that every proper vertex coloring of G using q colors can be lifted to a partition of V (G) into q odd induced subgraphs (in fact, odd induced forests). Indeed, with every color i of a proper q-coloring of V (G ) we associate an induced forest of G defined by the union of the trees whose corresponding vertex in G is colored i; see Fig 6 for an example. Therefore,

χ odd (G) ≤ χ(G ) ≤ tw(G ) + 1 ≤ tw(G) + 1,
where we have used the well-known fact that the chromatic number of a graph is at most its tree-width plus one [START_REF] Kloks | Computations and Approximations[END_REF]. To see that this bound it tight, consider a subdivided clique K q n , that is, the graph obtained from a clique on n vertices, with n ≡ 0, 3 (mod 4), by subdividing every edge once; see Fig. 7 for an example. Since no pair of original vertices of the clique can get the same color, we have that χ odd (K Let us mention some consequences of Theorem 7. Hou et al. [START_REF] Hou | Odd induced subgraphs in graphs with treewidth at most two[END_REF] define the following parameter. Let G k be the set of all graphs of treewidth at most k without isolated vertices, and let

q n ) = n = tw(K q n ) + 1.
c k = min G∈G k mos(G)
|V (G)| . In [START_REF] Hou | Odd induced subgraphs in graphs with treewidth at most two[END_REF] the authors prove that c 2 = 2/5 and say that the best general lower bound is c k ≥ 1 2k+2 , which follows from a result of Scott [START_REF] Scott | Large induced subgraphs with all degrees odd[END_REF]. As an immediate corollary of Theorem 7 it follows that c k ≥ 1 k+1 , which improves the lower bound by a factor two. As it is known [START_REF] Hou | Odd induced subgraphs in graphs with treewidth at most two[END_REF] that, for k ∈ [START_REF] Bui-Xuan | H-join decomposable graphs and algorithms with runtime single exponential in rankwidth[END_REF], c k ≤ 2 k+3 , our lower bound implies that 1/4 ≤ c 3 ≤ 1/3 and 1/5 ≤ c 4 ≤ 2/7.

We now provide a lower bound on mos(G) for every graph that admits a join. Theorem 8. For every n-vertex graph G that admits a join we have

mos(G) ≥ 2 • n -2 4 ,
and this bound is tight even for cographs.

Proof: Let V 1 , V 2 ⊆ V (G) define a join of G.
We proceed to define a coloring c : V (G) → [START_REF] Berman | Odd induced subgraphs in graphs of maximum degree three[END_REF] such that, for some i ∈ [START_REF] Berman | Odd induced subgraphs in graphs of maximum degree three[END_REF], G[c -1 (i)] is an odd subgraph with the claimed order. We distinguish three cases according to the parities of n, |V 1 |, and

|V 2 |.
Case 1: n is even and both |V 1 |, |V 2 | are odd. Gallai proved (see [START_REF] Caro | On induced subgraphs with odd degrees[END_REF]) that the vertex set of every graph G can be partitioned into two sets A, B such that

G[A] is odd and G[B] is even. We apply this result to both G[V 1 ] and G[V 2 ], yielding four sets V e 1 , V o 1 , V e 2 , V o 2 such that, for i ∈ [2], V i = V e i V o i , G[V e i ] is even, and G[V o i ] is odd. For i ∈ [2], the fact that G[V o i ] is odd implies that |V o i | is even, which in turn implies that |V e i | is odd since, by assumption, |V e i | + |V o i | = |V i | is odd. We define c -1 (1) = V e 1 ∪ V e 2 , c -1 (2) = V o 1 ∪ V o 2 , and c -1 (3) = ∅. Since V 1 , V 2 = ∅
as they define a join of G, and both |V 1 | and |V 2 | are odd, it follows that, for i ∈ [START_REF] Bergougnoux | More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints[END_REF], V e i = ∅. This implies that both G[c -1 (1)] and G[c -1 (2)] are odd, and therefore one of them has order at least n/2. Case 2: n is even and both |V 1 |, |V 2 | are even. Let v 1 ∈ V 1 and v 2 ∈ V 2 be two arbitrary vertices. We define c(v 1 ) = c(v 2 ) = 3 and we apply Case 1 above to the graph G -{v 1 , v 2 } with join given by V 1 \ {v 1 } and V 2 \ {v 2 }, obtaining two odd induced subgraphs of G colored 1 and 2, one of which has order at least (n -2)/2. Note that G[c -1 (3)] is also an odd subgraph (an edge).

Case 3: n is odd. Assume without loss of generality that |V 1 | is even and |V 2 | is odd, and let v 1 ∈ V 1 be an arbitrary vertex. We apply again Case 1 to the graph G -{v 1 } with join given by V 1 \ {v 1 } and V 2 , obtaining two odd induced subgraphs of G, one of which has order at least (n -1)/2. Note that since n is odd, in this case χ odd (G) is not defined.

Summarizing, we have proved that if n is even, then mos(G) ≥ n-2 2 , and that if n is odd, then mos(G) ≥ n-1 2 . Taking into account that an odd subgraph must have even order, both cases imply that, for every n, mos(G) ≥ 2 • n-2 4 .

Let us now see that this bound is tight for both even and odd values of n. For even n, consider the tripartite graph K 2,2,2 . It can be checked that this graph contains none of K 4 , K 1,3 , and 2K 2 (which are the only odd subgraphs on four vertices) as an induced subgraph, and therefore mos(K 2,2,2

) = 2 = 2 • 6-2 4 .
Finally, for odd n, consider C + 5 , that is, the graph obtained from C 5 by adding (any) two vertex-disjoint chords. Again, it can be checked that this graph contains none of K 4 , K 1,3 , and 2K 2 as an induced subgraph, and therefore mos(

C + 5 ) = 2 = 2 • 5-2 4
. Note that both K 2,2,2 and C + 5 are cographs; see Fig. Determining a tight lower bound for cographs that are not necessarily connected remains open. The proof of Cases 1 and 2 of Theorem 7 together with the fact that χ odd (K 2,2,2 ) = 3 (since mos(K 2,2,2 ) = 2) yield the following corollary.

Corollary 1.

Let G be a cograph with every connected component of even order. Then χ odd (G) ≤ 3. Moreover, this bound is tight.

Note that cographs can be equivalently defined as P 4 -free graphs. It is interesting to note that, in contrast to Corollary 1, P 5 -free graphs have unbounded odd chromatic number. Indeed, let H n be the graph obtained from the subdivided clique K q n , with n ≡ 0, 3 (mod 4), by adding an edge between each pair of original vertices of the clique. It can be checked that χ odd (H n ) ≥ n and, in fact, the proof of Theorem 2 implies that χ odd (H n ) = n. Note that H n is a split graph, hence split graphs have unbounded odd chromatic number.

Further research

We considered computational aspects of the Maximum Odd Subgraph and Odd q-Coloring problems. A number of interesting questions remain open.

We gave in Theorem 6 an algorithm that solves Odd q-Coloring in time O * (2 O(q•rw) ). Is the Odd Chromatic Number problem FPT or W [START_REF] Bergougnoux | Rank based approach on graphs with structured neighborhood[END_REF]-hard parameterized by rank-width? A strongly related question is how the odd chromatic number depends on rank-width. We proved in Theorem 7 that χ odd (G) ≤ tw(G) + 1, but we do not know whether χ odd (G) ≤ f (rw(G)) for some function f . Note that this would not only yield an FPT algorithm for Odd Chromatic Number by rank-width, but would also prove the conjecture about the linear size of a largest odd induced subgraph [START_REF] Caro | On induced subgraphs with odd degrees[END_REF] for all graphs of bounded rank-width. As a first step in this direction, we proved in Corollary 1 that cographs, which have rank-width at most one, have odd chromatic number at most three. It would be interesting to prove an upper bound for distance-hereditary graphs, which can be equivalently defined as graphs of rank-width one.

In fact, we do not even know whether Odd Chromatic Number by rankwidth is in XP. In view of the algorithm of Theorem 6, a sufficient condition for this would be that there exists a function f such that χ odd (G) ≤ f (rw(G)) • log |V (G)| for every graph G with all components of even order, but we were unable to prove it. Another plausible approach to obtain an XP algorithm (which we believe to exist) would be to extend the general XP algorithm of Rao [START_REF] Rao | MSOL partitioning problems on graphs of bounded treewidth and cliquewidth[END_REF] parameterized by clique-width for vertex partitioning problems expressible in monadic second-order logic so to take into account the parities of the degrees, that is, to counting monadic second order logic.

Toward an eventual W[1]-hardness proof for Odd Chromatic Number by rank-width, a natural strategy is to try to adapt the reduction given by Fomin et al. [START_REF] Fomin | Intractability of Clique-Width Parameterizations[END_REF] to prove that Chromatic Number is W[1]-hard by clique-width (hence, rank-width). This reduction is from Equitable Coloring parameterized by the number of colors plus tree-width, proved to be W[1]-hard by Fellows et al. [START_REF] Fellows | On the complexity of some colorful problems parameterized by treewidth[END_REF]. By appropriately modifying the chain of reductions given in [START_REF] Fellows | On the complexity of some colorful problems parameterized by treewidth[END_REF], we have only managed to prove that the naturally defined Odd Equitable Coloring problem is W[1]-hard by tree-width, but not if we add the number of colors as a parameter.

Concerning Odd q-Coloring parameterized by tree-width, a straightforward dynamic programming algorithm that guesses, for every vertex, its color class and the parity of its degree within that class, runs in time O * ((2q) tw ). Note that this algorithm together with Theorem 7 yield an algorithm for Odd Chromatic Number in time O * ((2tw + 2) tw ). By the lower bound under the ETH of Lokshtanov et al. [START_REF] Lokshtanov | Slightly superexponential parameterized problems[END_REF] for Chromatic Number by tree-width and the fact that our reduction of Theorem 2 preserves tree-width, it follows that the dependency on tree-width of this algorithm is asymptotically optimal under the ETH. It would be interesting to prove lower bounds under the Strong Exponential Time Hypothesis (SETH). Note that our reduction of Theorem 2 together with the lower bound under the SETH of Lokshtanov et al. [START_REF] Lokshtanov | Known algorithms on graphs of bounded treewidth are probably optimal[END_REF] for q-Coloring by tree-width yield a lower bound for Odd q-Coloring of O * ((q -ε) tw ) under the SETH.

A natural direction is to study the complexity of Odd q-Coloring, Odd Chromatic Number, Maximum Even Subgraph, and Maximum Odd Subgraph on restricted graph classes, such as split, interval, or chordal graphs. Concerning the Even Subgraph problem, given that in an n-vertex graph there always exists an even induced subgraph of size at least n/2 [START_REF] Lovász | Combinatorial Problems and Exercises[END_REF], it makes sense to consider the parameterization of the problem above this lower bound, that is, ask for the existence of an even induced subgraph of size at least n/2 + k, k being the parameter.

From a broader point of view, concerning problems that are FPT by rank-width such as Independent Set, Dominating Set, q-Coloring, and Feedback Vertex Set, the currently fastest algorithms run in time O * (2 O(rw 2 ) ) [START_REF] Bergougnoux | More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints[END_REF][START_REF] Bui-Xuan | H-join decomposable graphs and algorithms with runtime single exponential in rankwidth[END_REF], but the lower bounds under the ETH are just O * (2 o(rw) ), from the classical linear NP-hardness reductions from 3-Sat. To improve the lower bounds, one should probably construct graph families of rank-width O( √ n) and boolean-width Θ(n), as these problems can be solved in single-exponential time parameterized by boolean-width [START_REF] Bergougnoux | More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints[END_REF][START_REF] Bui-Xuan | Boolean-width of graphs[END_REF]. In particular, this would answer a question of Bui-Xuan et al. [START_REF] Bui-Xuan | Boolean-width of graphs[END_REF] about the relation between rank-width and boolean-width. A related question is to determine which graphs, other than sparse ones, have rank-width O( √ n). Concerning problems that are W[1]-hard by rank-width (or clique-width), such as Chromatic Number, Edge Dominating Set, Maximum Cut, and Hamiltonian Path, the lower bounds that follow directly from the ones for clique-width [START_REF] Fomin | Intractability of Clique-Width Parameterizations[END_REF][START_REF] Fomin | Almost optimal lower bounds for problems parameterized by clique-width[END_REF][START_REF] Fomin | Cliquewidth III: Hamiltonian Cycle and the Odd Case of Graph Coloring[END_REF] leave a huge gap for rank-width. Closing this gap looks like a challenging problem.

Note that the problems that we considered can be seen as the "parity version" of Independent Set and q-Coloring. It is natural to consider the parity version of other classical problems. In Appendix A we present some results on the parity version of domination problems, where the main contribution is to adapt the dynamic programming algorithms of Section 4 to these problems. It seems plausible that these results could also be lifted to the parity version of the vertex partitioning problems considered in [START_REF] Bui-Xuan | Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems[END_REF].

A Parity version of domination problems

In this section we consider the "parity version" of domination problems. For simplicity, we just deal with the "odd" versions. Namely, an odd dominating set (resp. odd total dominating set) of a graph G is a set S ⊆ V (G) such that every vertex in V (G) \ S (resp. V (G)) has an odd number of neighbors in S. Accordingly, in the Minimum Odd Dominating Set (resp. Minimum Odd Total Dominating Set) problem, we are given a graph G and the objective is to find an odd dominating set (resp. odd total dominating set) in G of minimum size.

It is worth mentioning that what is usually called an "odd dominating set" in the literature (cf. for instance [START_REF] Caro | The odd domination number of a graph[END_REF] and the references given in [START_REF] Caro | Connected odd dominating sets in graphs[END_REF][START_REF] Gravier | On weak odd domination and graph-based quantum secret sharing[END_REF]) differs from the definition given above. Indeed, in previous work a set S ⊆ V is said to be an odd dominating set if |N [v] ∩ S| is odd for every vertex v ∈ V (G). That is, vertices outside of S must have an odd number of neighbors in S, while vertices in S must have an even number of neighbors in S. Note that this definition differs from both definitions given in the above paragraph.

Concerning Odd Total Dominating Set, it was studied -among other parity problems-by Halldórsson et al. [START_REF] Halldórsson | Mod-2 Independence and Domination in Graphs[END_REF], who proved its NP-hardness by a reduction from the Codeword of Minimal Weight problem. However, the (quite involved) NP-hardness proof of this latter problem by Vardy [START_REF] Vardy | The intractability of computing the minimum distance of a code[END_REF] involves several nonlinear blow-ups, so a lower bound of 2 o(n) under the ETH cannot be deduced from it. Fortunately, we can indeed obtain a linear NPhardness reduction for both Minimum Odd Dominating Set and Minimum Odd Total Dominating Set by doing simple local modifications to the proof of Sutner [START_REF] Sutner | Additive automata on graphs[END_REF]Theorem 3.2] for a variant of odd total domination, which is from the 3-Sat problem. We omit the details here.

Once we know that none of these problems can be solved in time 2 o(n) on n-vertex graphs under the ETH, our main contribution in this section is to adapt the dynamic programming algorithms presented in Section 4 to solve both Minimum Odd Dominating Set and Minimum Odd Total Dominating Set in single-exponential time parameterized by the rank-width of the input graph. Namely, we prove the following two results. Theorem 9. Given a graph G along with a decomposition tree of rank-width w, the Minimum Odd Dominating Set problem can be solved in time O * (2 3rw ).

Proof:

The algorithm and its proof are nearly identical to the ones for Maximum Odd Subgraph (cf. Theorem 4), replacing condition ( ) with As future work, it would be interesting to adapt the above algorithms to deal with the connected version of both problems, where the (total) odd dominating set S is further required to induce a connected graph; see [START_REF] Caro | Connected odd dominating sets in graphs[END_REF] for related work about this variant of domination.

T A [R, R ] = max

Fig. 1 .

 1 Fig. 1.Diagram of some famous graph parameters (not defined here), where a parameter π is above a parameter π if there exists a function f : N → N such that, for everyinteger k ≥ 0, {G | π (G) ≤ k} ⊆ {G | π(G) ≤ f (k)}.

Theorem 1 .

 1 The Maximum Even Subgraph and Maximum Odd Subgraph problems are NP-hard. Moreover, none of them can be solved in time 2 o(n) on n-vertex graphs unless the ETH fails.

Fig. 3 .

 3 Fig. 3. Example of an even subgraph H in the graph of Fig. 2, assuming that ψ(xi) = 1 and ψ(x k ) = ψ(x ) = 0. Fat edges belong to H, while circled vertices do not.

  and that, out of the six possible paths from { 1 , 2 , 3 } to {c 1 j , c 2 j }, exactly four of them are entirely in H, while two of them are entirely outside of H. That is, |V (H) ∩ C j | = 10. On the other hand, the definition of Step 3 implies that |V (H 2 ) ∩ C j | = |V (H 1 ) ∩ C j | -4 = 10. Hence, since Step 3 only deletes vertices in C j , and we have proved that |V (H) ∩ C j | = |V (H 2 ) ∩ C j | = 10, we conclude that the joint application of Steps 1 and 3 does not decrease |V (H)|.

j 1 2 3 HFig. 4 .

 34 Fig. 4. Subgraphs considered in the analysis of Step 3 in the construction of H in the proof of Claim 2. The circled vertices do not belong to the corresponding graph.

Claim 5

 5 For every clause c j = ( 1 ∨ 2 ∨ 3 ) of ϕ, exactly two of its literals are set to true by ψ. Proof: By Claim 4, |V (H) ∩ C j | = 12, and then clearly deg H

Fig. 5 .

 5 Fig. 5. Example of the reduction of Theorem 2 with q = 3: (a) Instance G of 3-Coloring, along with a proper 3-coloring. (b) Graph G obtained from G along with an orientation of E(G ) with all in-degrees odd. (c) Instance G • of Odd 3-Coloring. (d) An odd 3-coloring of G • .

Theorem 3 .

 3 The Odd 2-Coloring problem can be solved in polynomial time.

Theorem 4 .

 4 Given a graph G along with a decomposition tree of rank-width rw, the Maximum Odd Subgraph problem can be solved in time O * (2 3rw ).

  and T {u} [{u}, {v}] = {u}, where v is the unique vertex of a basis of the adjacency matrix of the cut (V (G) \ {u}, {u}), which is the only non-empty choice for R . The entry T {u} [{u}, ∅] is left empty, since {u} is the only set equivalent to {u} and u has even degree in the subgraph G[{u}].

Fig. 6 .

 6 Fig. 6. A graph G and a partition of V (G) into odd induced trees. Thick vertices and edges correspond to the contracted graph G . A proper 3-coloring of V (G ) is depicted with colors.

Fig. 7 .

 7 Fig. 7. A subdivided K4 and an odd 4-coloring of it.

8 . 5 Fig. 8 . 2 4

 8582 Fig. 8. Cographs showing that the bound 2 • n-2 4 is tight.

S⊆A {|S| : S ≡ A 2 Theorem 10 .

 210 R∧{v ∈ A\S : |N (v)∩S| is even} = A∩N 2 (R )\S}, and the leaves are instead defined as T {u} [∅, {v}] = ∅ and T {u} [{u}, ∅] = T {u} [{u}, {v}] = {u}. T {u} [∅, ∅] is left empty. Given a graph G along with a decomposition tree of rank-width w, the Minimum Odd Total Dominating Set problem can be solved in time O * (2 3rw ).Proof: Again, the algorithm and its proof are nearly identical to the ones for Maximum Odd Subgraph (cf. Theorem 4), replacing condition ( ) withT A [R, R ] = max S⊆A {|S| : S ≡ A 2 R ∧ {v ∈ A : |N (v) ∩ S| is even} = A ∩ N 2 (R )},and the leaves are instead defined as T {u} [∅, {v}] = ∅ and T {u} [{u}, {v}] = {u}. T {u} [∅, ∅] and T {u} [{u}, ∅] are left empty.

We would like to mention that another NP-hardness proof for computing mes(G) has very recently appeared online[40]. The proof uses a chain of reductions from Maximum Cut and, although it also involves a quadratic blow-up, it can be avoided by starting from Maximum Cut restricted to graphs of bounded degree.

Acknowledgement. We would like to thank the anonymous referees for helpful and thorough comments that improved the presentation of the manuscript.

CE40-0028), ESIGMA (ANR-17-CE23-0010), and ELIT (ANR-20-CE48-0008-01), the program "Exploration Japon 2017" of the French embassy in Japan, and the JSPS KAKENHI grant number JP18K11157.


G L Ramillien

J Darrozes

L Seoane

AN INNOVATIVE MAPPING OF HYDROCLIMATIC TIME SERIES OF THE NIGER WATERSHED BY INVERTING GRACE KBR RANGES ON A BASIS OF SURFACE SLEPIAN FUNCTIONS

Keywords: GRACE, Slepian functions, continental hydrology, Niger

We propose to use a regional orthogonal Slepian Functions (SF) decomposition to represent and analyse the surface water mass variations sensed by GRACE satellite over the Niger basin. As band-limited Spherical Harmonics (SH) remain not adapted for describing hydrological signals in small geographical areas, Slepian functions can solve the signal energy loss by searching the concentration of information in both spatial and spectral domains of various size and shape. Another advantage of using such regionallydefined basis of orthogonal functions is the drastic reduction of the problem dimensions, so that much faster computation of only a few coefficients, instead of thousands of SH. We propose to use SF to adjust the corresponding 10-day SF coefficients for the semi-arid Niger basin from real geopotential data of the GRACE gravimetry mission. Multiyear time series of the Niger coefficients retrieve the seasonal cycle including a short-wet season every end of summer.

INTRODUCTION

Launched in March 2002 by NASA and DLR, the Gravity Recovery and Climate Experiment (GRACE) mission belongs to a new generation of Low-Earth Orbiter (LEO) satellites that improves the resolution of the gravity field to 300-400 km [START_REF] Tapley | The gravity recovery and climate experiment: mission overview and early results[END_REF][START_REF] Tapley | Contributions of GRACE to understanding climate change[END_REF]. In particular, the GRACE mission has been mapping the tiny changes of the gravity field that correspond to water mass transfers inside fluid envelops of our planet, i.e. atmosphere, oceans, continental water/ice storage.

Different ways for representing and analysing the GRACE signal have been proposed. Spherical Harmonics (SH) have been historically used to recover low degrees (or long wavelengths) of the gravity field from precise satellite trajectories, e.g. by laser telemetry. Unfortunately, SH suffer from spectrum truncation that causes spatial leakage. As they constitute a basis of orthogonal functions on the entire sphere and they are no longer optimal while studying small areas, the orthogonality and energy property are lost. Without orthogonality, any regional decomposition is not unique and ensured.

A representation in Slepian Functions (SF) that maximizes the information density in spatial and spectral domains is adopted in the present study. Extracting information over the full bandwidth of the solution without filtering, the SF basis provides spatial sensitivity that is superior to the sensitivity of many other modelling methods. It consists of building a finite set of orthogonal functions in a given region, as earlier proposed by [START_REF] Simons | Spherical Slepian functions and the polar gap in geodesy[END_REF] to solve geodetic localization problems. Former studies on applications of Slepian functions concerned the characterization of deep deformation of important earthquakes by their signature in the gravity field measured by GRACE. It is possible to isolate the coseismic gravity variation due to the 2004 Sumatra-Adaman earthquake [START_REF] Han | Spatiospectral localization of global geopotential fields from the Gravity Recovery And Climate Experiment (GRACE) reveals the coseismic gravity change owing to the 2004 Sumatra-Andaman earthquake[END_REF], while [START_REF] Cambiotti | A source model for the great 2011 Tohoku earthquake (Mw=9.1) from inversion of GRACE gravity data[END_REF] studied the Tohoku earthquake of 2011. In hydrology, the total mass loss of Greenland by melting has been made by [START_REF] Harig | Mapping Greenland's mass loss in space and time[END_REF] using GRACE data between 2002 -2011. Mass balance of the Tibetan Plateau and its surrounding glaciers that have been losing ice mass due to the global warming, was also quantified by [START_REF] Beveridge | The changing mass of glaciers on the Tibetan Plateau, 2002-2016, using timevariable gravity from GRACE satellite mission[END_REF]. The effects of coal mining that causes groundwater depletion consumption in the Loess Plateau were explored using SF representation [START_REF] Xie | Monitoring groundwater storage changes in the Loess Plateau using GRACE satellite gravity data, hydrological models and Coal mining data[END_REF]. Re-evaluation of the mass balance of the Iceland ice cap using SF have been also made by [START_REF] Hippel | Long-term and inter-annual mass changes in the Iceland ice cap determined from GRACE gravity using Slepian functions[END_REF], where considering a whole continent limited spatial leakage. So far, the first SF modes have been derived from spherical harmonics basis by imposing a certain bandwidth of L=60 for GRACE data. They are commonly derived considering the method of [START_REF] Harig | Mapping Greenland's mass loss in space and time[END_REF] and coded in [START_REF] Harig | A suite of software analyzes data on the sphere[END_REF] to transform the GRACE Stokes coefficients, i.e. dimensionless SH coefficients of the geopotential, into a regional SF basis. We propose here to use this set of SF to recover the hydrological variations of the semi-arid basin of the Niger river to restore the SF coefficients directly from the along-track GRACE geopotential data for 10-day periods.

THE NIGER BASIN CLIMATE

With a surface of 2.27 millions of km 2 shared by ten countries and a population of almost 100 millions of people, the Niger river basin is one of the most important river system of Africa (Figure 1). Its length of 4,200 km makes it the third longest river of the continent after Congo and Nile. Its average annual discharge is ~5500m 3 /s. It supports largescale irrigation, fisheries and livestock herding and agriculture (mainly cotton and rice), provides drinking water, generates hydropower and allows navigation. Its discharge at Koulikoro in Nigeria is about 32.5 km 3

GRACE KBRR DATA

The on-board K-Band Range Rate (KBRR) system measures the dual one-way change of range of the baseline between the two co-planar GRACE satellites with a precision of ~0.1 µm/s on the velocity difference or equivalently 10 µm in terms of Line-Of-Sight (LOS) distance after integration versus time [START_REF] Lemoine | Temporal gravity field models inferred from GRACE data[END_REF][START_REF] Bruinsma | CNES/GRGS 10-day gravity field models (release 2) and their evaluation[END_REF], while the average distance between the two GRACE vehicles is ~220 km. The Level-1B data are the most precise measurements of the gravity variations sensed by the satellite tandem with an accuracy of 10 -7 m/s, which gives access to surface water mass transfers. Coupled with the accurate 3-axis accelerometers measuring the effects of forces acting on the satellites, i.e. atmospheric drag and solar pressure, a priori models for atmosphere and oceanic masses, including polar and sloid tides, are used to compute along-track 5-second KBRR residuals by least-squares dynamical orbit determination. The daily positions of both GRACE satellite are provided by the Géodésie par Intégrations Numériques Simultanées (GINS) software developed by the Groupe de Recherche en Géodésie Spatiale (GRGS) in Toulouse, France, given realistic ephemeris and a EIGEN static gravity field model for imposing gravitational forces mainly due to the solid Earth acting on the twin satellites. KBRR residuals are easily converted into variations of potential differences between the two satellites following the energy conservation method proposed earlier by [START_REF] Jekeli | The determination of gravitational potential differences from satellite-to-satellite tracking[END_REF][START_REF] Han | Precise estimation of in situ geopotential differences from GRACE low-low satellite-tosatellite tracking and accelerometer data[END_REF], so that along-track residual differences of potential mainly caused by continental hydrology variations can reach 0.1 m 2 /s 2 with a precision of 10 -3 m 2 /s 2 [START_REF] Biancale | GRACE-derived surface mass anomalies by energy integral approach. Application to continental hydrology[END_REF].

METHODOLOGY

The Slepian function approach consists of two steps: (1) computation of the basis of regional orthogonal Slepian functions for the Niger watershed, and (2) the adjustment of the Slepian coefficients from the along-track GRACE KBRR data (see Section 3). More details on the SF methodology can be found in [START_REF] Ramillien | An innovative Slepian approach to invert GRACE KBRR for localized hydrological information at the sub-basin scale[END_REF].

Construction of a regional SF basis

The main task to construct the Slepian Functions F for regions of arbitrary shape is to solve the eigenvalue equation by SVD analysis, as they are the eigenfunctions of an areabandwidth limiting operator D [START_REF] Simons | Spherical Slepian functions and the polar gap in geodesy[END_REF][START_REF] Ramillien | An innovative Slepian approach to invert GRACE KBRR for localized hydrological information at the sub-basin scale[END_REF][START_REF] Bates | Efficient computation of Slepian functions for arbitrary regions on the sphere[END_REF]:

D F =  F ( 1
)
where D is the matrix formed by the distances between the points inside the geographical mask, e.g. the Niger basin.

For each eigenvalue k and its associated solution Fk of (1), or Slepian functions, that maximizes the concentration of energy inside the region, so that eigenvalue is a measure of information density of the considered k-th SF.

Reconstruction of the hydrological signal S consists of summing the SF with weights (or coefficients) to be determined, e.g. from the satellite gravity data, up to a certain mode K.

The approximate number of the pertinent SF to be kept is usually a quantity named Shannon number KS. This threshold number characterizes roughly the stair-step nature of the  spectrum, it represents the number of useful functions that are necessary to expand a L-band limited signal within the region. Considering only the first eigenvalues of the highest energy, e.g.  > 0.5, drastically improves the signal-to-noise ratio with very small impact outside the region of interest [START_REF] Simons | Spherical Slepian functions and the polar gap in geodesy[END_REF][START_REF] Kennedy | Hilbert Space Methods in Signal Processing[END_REF]. In practice, Shannon number can be simply determined as the sum of all the eigenvalues normalized by their maximum value, e.g. KS=21 for the Niger basin.

Space reduction of the inverse gravity problem

The damped Moore-Penrose solution of the problem to estimate the Slepian coefficient vector C is:

C = ( B *T B * ) -1 B *T Y ( 2
)
where Y is the N-element vector containing the GRACE potential differences due to a surface distribution of sources (see Section 3), and B * is the numerically-stabilized version of the pseudo-inverse operator given by:

B =  F (3)
where the elements of the Newtonian potential matrix  are given by [START_REF] Ramillien | Sequential estimation of surface water mass changes from daily satellite gravimetry data[END_REF] and F is the block-diagonal matrix of the SF (see Section 4.1). B * is constructed by keeping 99.9 % of the energy of the total SVD spectrum of B for attenuation of illconditioning of the system. Note that using B of dimension (N, KS) diminishes drastically the dimensions of the problem, as KS is generally of only several tens [START_REF] Ramillien | An innovative Slepian approach to invert GRACE KBRR for localized hydrological information at the sub-basin scale[END_REF]. A closer look at the location of the SF of this 2-maxima mode (Figure 2 (up)) reveals that one peak is located in the western part where oceanic influence is important and the second peak is located at the limit of desert / semi-arid zones. Consequently, these very weak fluctuations shown in Figure 2 (down) can be explained by the oceanic influences which bring rains on the western part of the Niger watershed while the eastern part remains under the influence of the desert climate. Mode 5 therefore results from the integration of these two climatic influences and it shows that the western rainfalls are balanced by the water deficit of the desert area. These observations explain the weak variations observed in the time series and also the associated shift due to asynchronous oceanic arrivals.

RESULTS

CONCLUSIONS

We have here demonstrated the possibility for inverting GRACE KBRR to retrieve water mass density (expressed in EWH) without re-projection of SH coefficients on a SF basis, but applying an innovative approach based on regional SF.

  per year (average of 1970-1998). The Niger river crosses areas with different climatic characteristics. It has a clear latitudinal zonation marked in the north by a desert climate (Sahara desert) which changes to a semi-arid band with savannas and ends in the south in the estuarine zone by a tropical band according to the Köppen climate classification. Due to the topography and hydrology, the basin is generally divided into four subregions: the Upper Niger, the Central Delta, the Middle Niger and the Lower Niger.

Figure 1 .

 1 Figure 1. Geographical localization of the Niger river basin. Latitudes and longitudes are in decimal degrees. The region is characterized by wet (~4 mm of average rainfall) and dry (~0.4 mm of average rainfall) seasons, the latter being significantly longer in the Sahel zone. The seasonal pattern and amount of rainfall in all areas depend on the latitude and position of the Inter-Tropical Convergence Zone (ITCZ) which migrates between North and South during the year.

Figure 2 (

 2 Figure 2 (up) shows the location of the main SF used to reconstruct the EWH time series over 6 years of GRACE data with a time step of 10 days. These main functions are located in the center of the Niger watershed, which indicates that, despite the complexity of the shape of the basin, the energy accumulated in these different modes is sufficient to reconstruct the climatic variability of the Niger watershed, as presented in Figure 2 (down). The first modes (K = 1, 2, 3, 4, 6) exhibit the same seasonal fluctuations. They show a rainy season starting suddenly in May with maxima in June-July of ~0.75 (in 2003) to ~0.4 m (in 2002) of EWH. Then a gradual decrease from September to March / April can be observed, with minima which show water deficits ranging from -0.20 m (in 2002) to -0.30 m (in 2003) of EWH. Mode number 5 is more surprising because if it also shows seasonality, it is much weaker but also much smoother. It presents maxima in August / September ranging from 0.2 m

Figure 2 .

 2 Figure 2. Spatial SF determined by SVD analysis for the Niger watershed up to the Shannon number 21 (up) and time series of these first SF modes adjusted every 10 days from the GRACE data (down).

We highlight that using a basis of only K=21 SF coefficients is sufficient to restore the main hydroclimatic changes of the Niger watershed at the GRACE satellite resolution.