Walid Ben-Ameur
email: walid.benameur@telecom-sudparis.eu

Antoine Glorieux
email: antoine.glorieux@telecom-sudparis.eu

José Neto
email: jose.neto@telecom-sudparis.eu

On the most imbalanced orientation of a graph

We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. The studied problem is denoted by MAXIM. We first characterize graphs for which the optimal objective value of MAXIM is zero. Next we show that MAXIM is generally NP-hard and cannot be approximated within a ratio of 1 2 + ε for any constant ε > 0 in polynomial time unless P = NP even if the minimum degree of the graph δ equals 2. Then we describe a polynomial-time approximation algorithm whose ratio is almost equal to 1

2 . An exact polynomial-time algorithm is also derived for cacti. Finally, two mixed integer linear programming formulations are presented. Several valid inequalities are exhibited with the related separation algorithms. The performance of the strengthened formulations is assessed through several numerical experiments.

Introduction and notation

Let G = (V, E) be an undirected simple graph (with node set V and edge set E), we denote by δ G the minimum degree of the vertices of G. An orientation Λ of G is an assignment of a direction to each undirected edge uv in E, i.e. any function on E of the form Λ (uv) ∈ { #» uv, #» vu}, ∀{uv} ∈ E where #» uv and # » vu denote the edge uv oriented from u to v. For each vertex v of G we denote by d G (v) or d(v) the unoriented degree of v in G and by d + Λ (v) or d + (v) (resp. d - Λ (v) or d -(v)) the outdegree (resp. indegree) of v in G w.r.t. Λ . Graph orientation is a well studied area in graph theory and combinatorial optimization, a large variety of constrained orientations as well as objective functions have been considered so far.

Among those arise the popular degree-constrained orientation problems: in 1976, Frank & Gyárfás [START_REF] Frank | How to orient the edges of a graph?[END_REF] gave a simple characterization of the existence of an orientation such that the outdgree of every vertex is between a lower and an upper bound given for each vertex. Asahiro et al. in [START_REF] Asahiro | Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree[END_REF][START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF][START_REF] Asahiro | Deegree constrained graph orientation: maximum satisfaction and minimum violation[END_REF] proved the NP-hardness of the weighted version of the problem where the maximum outdegree is minimized, gave some inapproximability results, and studied similar problems for different classes of graphs. Chrobak & Eppstein proved that for every planar graph a 3-bounded outdegree orientation and a 5-bounded outdegree acyclic orientation can be constructed in linear time [START_REF] Chrobak | Planar orientations with low out-degree and compaction of adjacency matrices[END_REF].

Other problems involving other criteria on the orientation have been studied such as acyclicity, diameter or connectivity. Robbins' theorem (1939) for example states that the graphs that have strong orientations are exactly the 2-edge-connected graphs [START_REF] Robbins | A theorem on graphs with an application to a problem of traffic control[END_REF] and later (1985), Chung et al. provided a linear time algorithm for checking whether a graph has such an orientation and finding one if it does [START_REF] Chung | Strongly connected orientations of mixed multigraphs[END_REF]. Then in 1960, Nash-Williams generalized Robbin's theorem showing that an undirected graph has a k-arcconnected orientation if and only if it is 2k-edge-connected [START_REF] Nash-Williams | On orientations, connectivity and odd vertex pairings in finite graphs[END_REF]. The problem called oriented diameter that consists in finding a strongly connected orientation with minimum diameter was introduced in 1978 by Chvatal & Thomassen: they proved that the problem is NP-hard for general graphs [START_REF] Chvatal | Distances in orientation of graphs[END_REF]. It was then proven to be NP-hard even if the graph is restricted to a subset of chordal graphs by [START_REF] Fomin | Complexity of approximating the oriented diameter of chordal graphs[END_REF] who gave also approximability and inapproximability results [START_REF] Fomin | Complexity of approximating the oriented diameter of chordal graphs[END_REF].

For an orientation Λ of G = (V, E) and a vertex v we call |d + Λ (v)d - Λ (v)| the imbalance of v in G w.r.t Λ and we call min v∈V |d + Λ (v)d - Λ (v)| the imbalance of Λ . Biedl et al. studied the problem of finding an acyclic orientation of unweighted graphs minimizing the imbalance of each vertex: they proved that it is solvable in polynomial time for graphs with maximum degree at most three but NP-complete generally and for bipartite graphs with maximum degree six and gave a 13 8 -approximation algorithm [START_REF] Biedl | Balanced vertex-orderings of graphs[END_REF]. Then Kára et al. closed the gap proving the NP-completeness for graphs with maximum degree four. Furthermore, they proved that the problem remains NP-complete for planar graphs with maximum degree four and for 5-regular graphs [START_REF] Kára | On the complexity of the balanced vertex ordering problem[END_REF].

Landau's famous theorem [START_REF] Landau | On dominance relations and the structure of animal societies III. The condition for a score structure[END_REF] gives a condition for a sequence of non-negative integers to be the score sequence or outdegree sequence of some tournament (i.e. oriented complete graph) and later, Harary & Moser characterized score sequences of strongly connected tournaments [START_REF] Harary | Graphs suppressible to an edge[END_REF]. Analogous results for the "imbalance sequences" of directed graphs are given by Mubayi et al. [START_REF] Mubayi | Realizing Degree Imbalances in Directed Graphs[END_REF]. In 1962, Ford & Fulkerson characterized the mixed graphs (i.e. partially oriented graphs) whose orientation can be completed in an eulerian orientation, that is to say, an orientation for which the imbalance of each vertex equals zero [START_REF] Ford | Flows in networks[END_REF]. Many other results related to orientation have been proposed. Some of them are reviewed in [START_REF] Bang-Jensen | Orientations of graphs and digraphs in 'Digraphs: Theory, Algorithms and applications[END_REF].

Let us denote by -→ O (G) the set of all the orientations of G, we consider the problem of finding an orientation with maximized imbalance:

(MAXIM) MAXIM(G) = max Λ ∈ - → O (G) min v∈V |d + Λ (v) -d - Λ (v)|
and we call MAXIM(G) the value of MAXIM for G. The minimum degree δ G of a graph G is a trivial upper bound for MAXIM(G). The rest of this paper is organized as follows. In the section 2, we give several characterizations of the the graphs verifying MAXIM(G) = 0. In Section 3, we show that MAXIM is generally NP-complete even for graphs with minimum degree 2 and inapproximable within a ratio 1 2 + ε for any constant ε > 0 and then give an approximation algorithm whose ratio is almost equal to 1 2 . In Section 4, we present a polynomial-time exact algorithm for cactus. Section 5 is devoted to mixed integer linear programming formulations of MAXIM where families of valid inequalities are presented for the most promising formulation. These formulation have been implemented and the computational results are reported in Section 6.

Since the value of MAXIM for a graph is the minimum of the values of MAXIM on its connected components, from here on out, all the graphs we consider are assumed to be connected. For a graph G and H a subgraph of G, we will use the notations V (H) and E(H) to refer to the set of vertices of G and the set of edges of H, respectively.

2 Characterizing the graphs for which MAXIM(G) = 0 Now we characterize the graphs verifying MAXIM(G) = 0. We start by unveiling several necessary conditions and properties of such graphs. First we can show that concerning such a graph, we can find an orientation satisfying several additional properties.

Proposition 1 Let G be a graph such that MAXIM(G) = 0 and u ∈ V . Then there exists an orientation Λ ∈ -→ O (G) such that u is the only vertex of G with imbalance equal to zero w.r.t. Λ .

Proof. Let Λ ∈ - → O (G) be an orientation minimizing |{v ∈ V /|d + Λ (v) -d - Λ (v)| = 0}|. We suppose that |{v ∈ V /|d + Λ (v) -d - Λ (v)| = 0}| ≥ 2. We choose two distinct vertices v and w in {v ∈ V /|d + Λ (v) -d - Λ (v)| = 0} and a path p = (v = u 0 , • • • , u n = w)
between v and w. If we switch the orientation of the edge u 0 u 1 , then the imbalance of u 0 becomes positive and necessarily the imbalance of u 1 becomes zero otherwise the resulting orientation would contradict the minimality of Λ . Using the same reasoning, if we switch the orientation of all the edges u 0 u 1 , • • • , u n-2 u n-1 , we obtain an orientation where both u n-1 and u n have an imbalance equal to zero while the imbalance is positive on all the vertices u 0 , • • • , u n-2 and unchanged on all other vertices. So now if we switch the orientation of the edge u n-1 u n as well, then the resulting orientation contradicts the minimality of Λ . Hence,

|{v ∈ V /|d + Λ (v) -d - Λ (v)| = 0}| = 1. Now let v be this unique vertex of G such that |d + Λ (v) -d - Λ (v)| = 0.
Let u = v be an arbitrary vertex and let p = (v = u 0 , • • • , u n = u) be a path between v and u. By switching the orientation of all the edges u 0 u 1 , • • • , u n-2 u n-1 , we obtain an orientation Λ where u has an imbalance equal to zero while the imbalance is positive for u 0 and unchanged on all other vertices. This yields the following necessary condition: if G is a graph such that MAXIM(G) = 0, then G is eulerian. For let u ∈ V , we know there exists

Λ ∈ - → O (G) such that {v ∈ V /|d + Λ (v) -d - Λ (v)| = 0} = {u}. Then d + Λ (u) = d - Λ (u), hence d(u) = d + Λ (u) + d - Λ (u) = 2d + Λ (u) is even.
The following lemma about eulerian graphs will be useful for the proof of our characterization.

Lemma 2 If G is an eulerian graph, then there exists an elementary cycle (hereafter just called cycle) C of G such that G -E(C) has at most one connected component that is not an isolated vertex.

Proof. Since G is eulerian and connected, it can be decomposed into edge-disjoint cycles that we can order C 1 , • • • ,C n according to the following condition: ∪ i k=1 C i is connected, ∀i ∈ 1, n . Then C n is the cycle we are looking for. Now let us define a certain family of graphs which will prove to be exactly the graphs for which the optimal objective value of MAXIM is zero. Intuitively they are the graphs for which every block is an odd cycle.

Definition 3

We define the class of graphs C odd as follows: a simple graph G is in

C odd if there exists n odd cycles C 1 , • • • ,C n (n ≥ 1) such that: • ∪ n i=1 C i = G, • |V (∪ i-1 k=1 C k ) ∩V (C i )| = 1, ∀i ∈ 2, n . (1)
Theorem 4 For any simple graph G, MAXIM(G) = 0 if and only if G ∈ C odd .

Proof. • ⇐ We work by induction on the number n of cycles contained in the graph.

Nothing is required for these cycles except that they must be elementary. If n = 1, then our graph is an odd cycle which implies MAXIM(G) = 0. Let n ≥ 2, we assume that all graphs of

C odd with k ≤ n -1 cycles verify MAXIM(G) = 0. Let G ∈ C odd with n cycles C 1 , • • • ,C n as in (1). Suppose there exists Λ ∈ - → O (G) with strictly positive imbalance. Let us call G = ∪ n-1
i=1 C i the graph obtained from G after removing C n and let us take a look at Λ |G : the orientation of the edges of G obtained from Λ restricted to E(G ). As G is a graph of n -1 cycles in C odd , our inductive hypothesis implies that we have a vertex

u ∈ V (G ) such that |d + Λ |G (u) - d - Λ |G (u)| = 0. Necessarily, u = V (G ) ∩V (C n ). Thus |d + Λ (u) -d - Λ (u)| = |d + Λ |Cn (u) - d - Λ |Cn (u)| > 0 implying that MAXIM(C n ) > 0, a contradiction because C n is an odd cycle.
• ⇒ Since MAXIM(G) = 0, we know that G is eulerian. We work again by induction on the number of elementary cycles n. If n = 1, then our graph is eulerian with a unique cycle, hence it is a cycle. Now as MAXIM(G) = 0, necessarily it is an odd cycle and is therefore in C odd . Let n ≥ 2, we assume that all graphs with k ≤ n -1 cycles verifying MAXIM(G) = 0 are in C odd . Let G be a graph with n cycles such that MAXIM(G) = 0. Thanks to Lemma 2, there exists a cycle C of G such that G -E(C) has at most one connected component G that is not an isolated vertex. Suppose that MAXIM(G ) > 0, let Λ ∈ -→ O (G ) with strictly positive imbalance. Let u 0 ∈ V (G ) ∩ V (C), we name the vertices of C as follows:

u 0 , u 1 , • • • , u k = u 0 .
Without loss of generality, we can assume that d + Λ (u 0 )d - Λ (u 0 ) > 0; if it was not the case, replace Λ by its reverse. We complete Λ in an orientation of G by orienting the edges of C: we orient u 0 u 1 from u 0 to u 1 and go on as follows:

∀i ∈ 1, k -1 , if u i ∈ V (G ), we orient u i u i+1 as u i-1 u i , otherwise, we orient u i u i+1 as u i u i-1 .
Where orienting an edge ab as another edge cd means orienting it from a to b if cd was oriented from c to d and from b to a otherwise. Let us have a look at the resulting orientation Λ (cf Fig. 1): when completing Λ in Λ , the imbalance of the vertices in V (G )\{u 0 } was left unchanged, the imbalance of the vertices in V (C)\V (G ) equals 2 and the imbalance of u 0 was either left unchanged or augmented by two. Hence Λ has strictly positive imbalance which contradicts MAXIM(G) = 0, therefore, MAXIM(G ) = 0. Suppose |V (G ) ∩V (C)| ≥ 2 and let u and v be 2 distinct vertices in V (G ) ∩V (C) such that u = v. Thanks to Proposition 1, we know that there exists an orientation

Λ ∈ - → O (G ) such that {w ∈ V /|d + Λ (w) -d - Λ (w)| = 0} = {v} and without loss of generality, d + Λ (u) -d - Λ (u) > 0.
We name the vertices of C as follows:

u = u 0 u 1 • • • u k = u 0 , v = u l
and we complete Λ in an orientation of G by orienting the edges of C: we orient u 0 u 1 from u 0 and u 1 and go on as follows:

∀i ∈ 1, k -1 \ {l}, if u i ∈ V (G )
, we orient u i u i+1 as u i-1 u i , otherwise, we orient u i u i+1 as u i u i-1 .

And we orient u l u l+1 as u l u l-1 . In the resulting orientation Λ , the imbalance of the vertices in V (G )\{u, v} was left unchanged, the imbalance of the vertices in V (C)\V (G ) equals 2, the imbalance of v was augmented by two and the imbalance of u was either left unchanged or augmented by two. Hence

Λ contradicts MAXIM(G) = 0, therefore, |V (G ) ∩V (C)| = 1. Suppose C is even. We call u ∈ V (G ) such that V (G ) ∩ V (C) = {u}, and Λ ∈ - → O (G ) such that {v ∈ V /|d + Λ (v) -d - Λ (v)| = 0} = {u}.
We name the vertices of C as follows: u = u 0 u 1 • • • u k = u 0 and we complete Λ in an orientation of G by orienting the edges of C: we orient u 0 u 1 from u 0 to u 1 and u i u i+1 as u i u i-1 , ∀i ∈ 1, k -1 . In the resulting orientation Λ , the imbalance of the vertices in V (G )\{u} was left unchanged, the imbalance of the vertices in V (C)\V (G ) equals 2 and, C being even, the imbalance of u was augmented by two. Hence Λ contradicts MAXIM(G) = 0, therefore, C is odd. As G is a graph with at most n -1 cycles verifying MAXIM(G) = 0, by the induction hypothesis, there exist C 1 , • • • ,C n-1 odd cycles such that:

• ∪ n-1 i=1 C i = G , • |V (∪ i-1 k=1 C k ) ∩V (C i )| = 1, ∀i ∈ 2, n -1 . Adding the odd cycle C n = C, we obtain that G ∈ C odd .
+ Λ (u 0 ) -d - Λ (u 0 )| ≥ |d + Λ (u 0 ) -d - Λ (u 0 )| > 0 . G u 0 u 1 u k-1 C
Now in order to widen our perception of those graphs, let us show another characterization.

+ Λ (u 0 ) -d - Λ (u 0 )| ≥ |d + Λ (u 0 ) -d - Λ (u 0 )| > 0 . G u v u 1 u k-1 C
Theorem 5 For every simple graph G, G ∈ C odd ⇔ G is eulerian with no even cycle Proof. • ⇒ By construction, every graph in C odd is eulerian with no even cycle.

• ⇐ We will once again work by induction on the number of cycles n.

If n = 1, then our graph is eulerian with a unique odd cycle, hence it is an odd cycle and is therefore in C odd . Let n ≥ 2, we assume that all eulerian graphs with no even cycle and k ≤ n -1 odd cycles are in C odd . Let G be a graph with no even cycle and n odd cycles. Thanks to Lemma 2, there exists an odd cycle C of G such that G -E(C) has only one connected component G that is not an isolated vertex. As G is eulerian and even-cycle-free with n -1 odd cycles, by induction hypothesis, G ∈ C odd , hence there exist

C 1 , • • • ,C n-1 odd cycles such that: • ∪ n-1 i=1 C i = G , • |V (∪ i-1 k=1 C k ) ∩V (C i )| = 1, ∀i ∈ 2, n -1 . Suppose there exist u and v (u = v) belonging to V (∪ n-1 k=1 C k ) ∩ V (C).
Since G is connected, let p be an elementary path in G between u and v. We can assume that u and v are the only vertices of C contained in p, otherwise we could replace v by the first vertex of C encountered when traveling on p from u. C defines two other vertex-disjoint paths between u and v: one even that we will call p even and one odd that we will call p odd . p being vertex disjoint with either p even or p odd , by concatenating it with the one corresponding to its parity, we obtain an even cycle of G, contradicting our hypothesis on G (cf. Fig. 3(a) and 3(b)). This yields that

|V (C) ∩V (G )| = 1. From that we can conclude • ∪ n i=1 C i = G, • |V (∪ i-1 k=1 C k ) ∩V (C i )| = 1, ∀i ∈ 2, n . Hence G ∈ C odd .
C i 0 C i 1 C p p odd p even (b) C intersects two cycles

Complexity and (in)approximability

In this section we prove the NP-completeness and inapproximability of our problem and give an approximation algorithm based on the special case of bipartite graphs.

Concerning the complexity of MAXIM, we show that the problem is NP-complete. More precisely, that answering if MAXIM(G) equals 2 for a graph G such that δ G = 2 is NP-complete. For that purpose, we introduce a variant of the satisfiability problem that we reduce to a MAXIM instance: the not-all-equal at most 3-SAT(3V).

Not-all-equal at most 3-SAT(3V) is a restriction of not-all-equal at most 3-SAT which is itself a restriction of 3-SAT known to be NP-complete [START_REF] Schaefer | The complexity of satisfiability problems[END_REF], where each clause contains at most three literals and in each clause, not all the literals can be true. Since 2-SAT can be solved in polynomial time, we hereafter deal only with formulas having at least one three-literals clause. The added restriction of not-all-equal at most 3-SAT(3V) is that each variable (not literal) appears at most three times in a formula. The resulting problem is still NP-complete.

Lemma 6

The not-all-equal at most 3-SAT(3V) problem is NP-complete.

Proof. See Appendix A. Now we associate to a not-all-equal at most 3-SAT(3V) instance ϕ with n variables

{x 1 , • • • , x n } and m clauses {c 1 , • • • , c m } a graph G ϕ for which the value w.r.t. MAXIM
will give the answer to whether ϕ is satisfiable or not. If a variable x i occurs only in positive literals (resp. only in negative literals), it follows that a satisfying assignment of the variables of ϕ must necssarily give the value TRUE (resp. FALSE) to x i , therefore x i can be removed from ϕ with conservation of the satisfiability. Thus, without loss of generality, we can assume that in any not-all-equal at most 3-SAT(3V) formula, every variable occurs at least once as a positive literal and at least once as a negative literal. G ϕ consists of gadgets that mimic the variables and the clauses of ϕ and additional edges that connect them together:

• the gadget corresponding to a variable x i consists of two vertices labeled x i and ¬x i and one edge connecting them;

• the gadget corresponding to a two-literals clause c j = (l 1 ∨ l 2 ), where l 1 and l 2 are its literals, consists in two vertices labeled a j l 1 and b j l 2 corresponding to l 1 and l 2 respectively (the index "l k " of the vertices labels stands for the literal it represents, i.e. x i if l k is the variable x i and ¬x i if l k is the negation of the variable x i ) and one edge connecting them;

• the gadget corresponding to a three-literals clause gadget consists in six vertices and six edges. For a clause c j = (l 1 ∨ l 2 ∨ l 3 ), where l 1 , l 2 and l 3 are its literals (the order is arbitrary), three vertices labeled a j l 1 , b j l 2 and b j l 3 correspond to l 1 , l 2 and l 3 respectively. Three additional vertices are labeled u j , v j and w j and the gadgets' edges are a j l 1 u j , a j l 1 v j , u j w j , v j w j , w j b j l 2 and w j b j l 3 ;

• ∀i ∈ 1, n , the vertex labeled x i (resp. ¬x i ) is connected to all the vertices labeled

a j x i , b j x i or b j x i (resp. a j ¬x i , b j ¬x i or b j ¬x i ), ∀ j ∈ 1, m .
As an example, for a formula

ϕ = (x 1 ∨ ¬x 2 ∨ x 3 ) ∧ (¬x 1 ∨ ¬x 3 ∨ x 4 ) ∧ (x 1 ∨ ¬x 2 ∨ x 4 ) ∧ (x 2 ∨ ¬x 4 ), (2)
the corresponding graph G ϕ is represented in Fig. 4.

Fig. 4:

G ϕ for ϕ = (x 1 ∨ ¬x 2 ∨ x 3 ) ∧ (¬x 1 ∨ ¬x 3 ∨ x 4 ) ∧ (x 1 ∨ ¬x 2 ∨ x 4 ) ∧ (x 2 ∨ ¬x 4 ) x 1 ¬x 1 x 2 ¬x 2 x 3 ¬x 3 x 4 ¬x 4 a 1 x 1 b 1 ¬x 2 b 1 x 3 a 2 ¬x 1 b 2 ¬x 3 b 2 x 4 a 3 x 1 b 3 ¬x 2 b 3 x 4 a 4 x 2 b 4 ¬x 4 v 1 v 2 v 3 u 1 u 2 u 3 w 1 w 2 w 3 clause gadgets variable gadgets Theorem 7 A not-all-equal at most 3-SAT(3V) formula ϕ is satisfiable if and only if MAXIM(G ϕ ) = 2.
Proof. • ⇒ Suppose ϕ is satisfiable and let v :

{x 1 , • • • , x n } → {TRUE, FALSE} be a satisfying assignment of x 1 , • • • , x n . We know that δ G ϕ = 2 which yields MAXIM(G ϕ ) ≤ 2. So let us build an orientation Λ ∈ - → O (G ϕ )
for which the imbalance is greater than or equal to 2. First, we assign an orientation to the edges of the variable gadget:

Λ (x i ¬x i ) = # » x i ¬x i if v(x i ) = TRUE; # » ¬x i x i otherwise. Fig. 5: G ϕ corresponding to ϕ = (x 1 ∨ ¬x 2 ∨ x 3 ) ∧ (¬x 1 ∨ ¬x 3 ∨ x 4 ) ∧ (x 1 ∨ ¬x 2 ∨ x 4 ) ∧ (x 2 ∨ ¬x 4 ) satisfied by v(x 1 , x 2 , x 3 , x 4 ) = (FALSE, TRUE, TRUE, TRUE). x 1 ¬x 1 x 2 ¬x 2 x 3 ¬x 3 x 4 ¬x 4 (x 1 ∨ ¬x 2 ∨ x 3 ) (¬x 1 ∨ ¬x 3 ∨ x 4 ) (x 1 ∨ ¬x 2 ∨ x 4 ) (x 2 ∨ ¬x 4 )
(a) orientation of the edges in the variable gadgets

x 1 ¬x 1 x 2 ¬x 2 x 3 ¬x 3 x 4 ¬x 4 (x 1 ∨ ¬x 2 ∨ x 3 ) (¬x 1 ∨ ¬x 3 ∨ x 4 ) (x 1 ∨ ¬x 2 ∨ x 4 ) (x 2 ∨ ¬x 4 )
(b) orientation of the edges between the variable gadgets and the clause gadgets

x 1 ¬x 1 x 2 ¬x 2 x 3 ¬x 3 x 4 ¬x 4 (x 1 ∨ ¬x 2 ∨ x 3 ) (¬x 1 ∨ ¬x 3 ∨ x 4 ) (x 1 ∨ ¬x 2 ∨ x 4 ) (x 2 ∨ ¬x 4 )
(c) orientation of the edges in the clause gadgets For example, for the formula ϕ = (

x 1 ∨ ¬x 2 ∨ x 3 ) ∧ (¬x 1 ∨ ¬x 3 ∨ x 4 ) ∧ (x 1 ∨ ¬x 2 ∨ x 4 ) ∧ (x 2 ∨ ¬x 4
) satisfied by the assignment v(x 1 , x 2 , x 3 , x 4 ) = (FALSE, TRUE, TRUE, TRUE), the edges of the variable gadgets of graph G ϕ are oriented as in figure 5(a). Since each variable x i occurs at least once as a positive literal and at least once as a negative literal, 2

≤ d G ϕ (x i ) ≤ 3 and 2 ≤ d G ϕ (¬x i ) ≤ 3, ∀i ∈ 1, n .
Then to ensure our objective on the imbalance of Λ , the orientation of the edges connecting vertex gadgets and clause gadgets must be such that ∀i ∈

1, n , |d + Λ (x i ) -d - Λ (x i )| = d G ϕ (x i ) and |d + Λ (¬x i ) -d - Λ (¬x i )| = d G ϕ (¬x i ). In other words, for i ∈ 1, n , if v(x i ) = TRUE (resp. v(x i ) = FALSE)
, then the edges adjacent to the vertex x i are oriented from x i (resp. to x i ) and the edges adjacent to the vertex ¬x i are oriented to ¬x i (resp. from ¬x i ), e.g. Fig. 5(b). So far, all the edges in the variables gadgets and the edges connecting the vertex gadgets and the clause gadgets have been oriented and the vertices in the variables gadgets have imbalance greater than or equal to 2. In order to complete our orientation Λ we have to orient the edges in the clause gadgets. Let c j = (l 1 ∨ l 2 ) be a two-literals clause. Since v satisfies ϕ, we know that exactly one of the two literals is true w.r.t. v. Which, according to the way we oriented edges so far, means that exactly one of a j l 1 and b j l 2 has one incoming arc from a variable gadget and the other has one outgoing arc to a variable gadget. If a j l 1 is the one with the incoming arc from a variable gadget (meaning that v(l 1 ) = TRUE), then we assign

Λ (a j l 1 b j l 2 ) = # » b j l 2 a j l 1 , otherwise the opposite. We obtain |d + Λ (a j l 1 ) -d - Λ (a j l 1 )| = |d + Λ (b j l 2 ) -d - Λ (b j l 2 )| = 2. Let c j = (l 1 ∨ l 2 ∨ l 3 ) (the order is identical to the one chosen to build the clause gadget, i.e. d G ϕ (a j l 1 ) = 3 and d G ϕ (b j l 2 ) = d G ϕ (b j l 3 ) =
2) be at three-literals clause. If the edge connecting a j l 1 to a variable gadget is oriented to a j l 1 (meaning that v(l 1 ) = TRUE), then we assign Λ (a j l

1 u j ) = # » u j a j l 1 , Λ (a j l 1 v j ) = # » v j a j l 1 , Λ (u j w j ) = # » u j w j and Λ (v j w j ) = # » v j w j . Since v(l 1 ) = TRUE, either both v(l 2
) and v(l 3 ) are FALSE or exactly one of v(l 2 ) and v(l 3 ) is TRUE and one is FALSE. If both are FALSE then b j l 2 and b j l 3 have an outgoing arc to a variable gadget. In that case, we orient w j b j l 2 and w j b j l 3 to w j and we obtain |d

+ Λ (a j l 1 ) -d - Λ (a j l 1 )| = 3, |d + Λ (b j l 2 ) -d - Λ (b j l 2 )| = |d + Λ ((b j l 3 ) -d - Λ ((b j l 3 )| = |d + Λ (u j ) -d - Λ (u j )| = |d + Λ (v j ) -d - Λ (v j )| = 2 and |d + Λ (w j ) - d - Λ (w j )| = 4. If exactly one of v(l 2 ) and v(l 3
) is TRUE and one is FALSE, then exactly one of b j l 2 and b j l 3 has an incoming arc from a variable gadget and the other an outgoing arc to a variable gadget. If b j l 2 is the one with the incoming arc from a variable gadget (meanings that v(l 2 ) = TRUE and v(l 3 ) = FALSE), then we assign Λ (w j b j l 2 ) = # » w j b j l 2 and Λ (w j b j l 3 ) = # » b j l 3 w j , otherwise the opposite. We

obtain |d + Λ (a j l 1 ) -d - Λ (a j l 1 )| = 3 and |d + Λ (b j l 2 ) -d - Λ (b j l 2 )| = |d + Λ (b j l 3 ) -d - Λ (b j l 3 )| = |d + Λ (u j ) -d - Λ (u j )| = |d + Λ (v j ) -d - Λ (v j )| = |d + Λ (w j ) -d - Λ (w j )| = 2.
If, on the other hand, the edge connecting a j l 1 to a variable gadget is oriented from a j l 1 (meanings that v(l 1 ) = FALSE), then we assign Λ (a j l 1 u j ) = # » a j l 1 u j , Λ (a j l 1 v j ) = # » a j l 1 v j , Λ (u j w j ) = # » w j u j and Λ (v j w j ) = # » w j v j . By symmetry, we conclude in the same

way that |d + Λ (a j l 1 ) -d - Λ (a j l 1 )| = 3 and |d + Λ (b j l 2 ) -d - Λ (b j l 2 )| = |d + Λ (b j l 3 ) -d - Λ (b j l 3 )| = |d + Λ (u j ) -d - Λ (u j )| = |d + Λ (v j ) -d - Λ (v j )| = |d + Λ (w j ) -d - Λ (w j )| = 2.
Consequently, the imbalance of the resulting orientation Λ is greater than or equal to 2, e.g. Fig. 5(c).

• ⇐ Now we assume that MAXIM(G ϕ ) = 2, let Λ ∈ - → O (G ϕ
) with optimal imbalance. Since all the vertices in the variable gadgets have degree at most 3, each vertex x i (or ¬x i ) is necessarily adjacent to only incoming arcs or only outgoing arcs w.r.t. Λ . We will show that the assignment v :

{x 1 , • • • , x n } → {TRUE, FALSE} of x 1 , • • • , x n defined by v(x i ) = TRUE if d + Λ (x i ) > d - Λ (x i ); FALSE otherwise; satisfies ϕ. Suppose ϕ does not satisfy a clause c j , j ∈ 1, m . If c j is a two-literals clause (l 1 ∨ l 2 ) then either v(l 1 ) = v(l 2 ) = TRUE or v(l 1 ) = v(l 2 ) = FALSE, i.e.
either both a j l 1 and b j l 2 have an incoming arc from a variable gadget or both have an outgoing arc to a variable gadget and in both cases, whichever is the orientation assigned to a j l 1 b j l 2 by Λ , either a j l 1 or b j l 2 has a zero imbalance which contradicts our assumption. So c j is a three-literals clause (l 1 ∨ l 2 ∨ l 3 ) (the order is identical to the one chosen to build the clause gadget, i.e. d G ϕ (a j l 1 ) = 3 and

d G ϕ (b j l 2 ) = d G ϕ (b j l 3 ) = 2). Then either v(l 1 ) = v(l 2 ) = v(l 3 ) = TRUE or v(l 1 ) = v(l 2 ) = v(l 3 ) = FALSE, i.e
. either all a j l 1 , b j l 2 and b j l 3 have an incoming arc from a variable gadget or they all have an outgoing arc to a variable gadget. In the first case,

it implies Λ (a j l 1 u j ) = # » u j a j l 1 , Λ (a j l 1 v j ) = # » v j a j l 1 , Λ (u j w j ) = # » u j w j , Λ (v j w j ) = # » v j w j , Λ (w j b j l 2 ) =
# » w j b j l 2 and Λ (w j b j l 3 ) = # » w j b j l 3 , and we obtain |d + Λ (w j )d - Λ (w j )| = 0 which contradicts the optimality of Λ . Similarly, in the second case it implies that the orientations assigned to the edges of the clause gadgets are the opposite from the previous ones and we obtain the same contradiction. So we can conclude that v does satisfy ϕ.

Corollary 8 MAXIM is NP-complete and inapproximable within 1 2 + ε where ε ∈ R * + , unless P = NP.

Proof. Let ε ∈ R * + , suppose that there exists a polynomial approximation algorithm giving val ≥ ( 1 2 + ε) MAXIM(G) for an input graph G. Let ϕ be a not-all-equal at most 3-SAT(3V) formula and G ϕ its associated graph. Since G ϕ contains at least one threeliterals clause gadget, we know that G ϕ contains an even cycle and δ G ϕ = 2. This leads to MAXIM(G ϕ ) ∈ {1, 2} and since

( 1 2 + ε) MAXIM(G ϕ ) ≤ val ≤ MAXIM(G ϕ )
, if the polynomial approximation algorithm returns a value less than or equal to 1 then

( 1 2 + ε) MAXIM(G ϕ ) ≤ 1 ⇒ MAXIM(G ϕ ) < 2 ⇒ MAXIM(G ϕ ) = 1;
and if it returns a value greater than 1, then MAXIM(G ϕ ) is greater than 1 hence equal to 2. In other words the polynomial approximation algorithm output answers whether ϕ is satisfiable or not which implies P = NP.

Let us use cut(A) to denote the set of edges having only one endpoint in A. Now we consider the case of bipartite graphs: if E) is a bipartite graph, the orientation that consists in assigning to each edge in E the orientation from its endpoint in V 1 to its endpoint in V 2 has an imbalance equal to δ G , i.e. optimal. This simple case permits us to obtain the following lower bound:

G = (V 1 ∪ • V 2 ,
Theorem 9 For every graph G, MAXIM(G) ≥ δ G 2 -1. Proof. Let (V 1 ,V 2 ) be a partition of V corresponding to a cut C = cut(V 1 ) ⊂ E such that we have |cut({v}) ∩ C| ≥ d(v)
2 , ∀v ∈ V . Such a cut exists: for example a maximum cardinality cut verifies this property, otherwise we could find a higher cardinality cut by switching a vertex v ∈ V s.t. |cut({v}) ∩C| < d(v) 2 from V 1 to V 2 (or the contrary). Moreover, if we iterated this process starting from a random k, we would converge in polynomial time to such a cut. Now we define Λ ∈ -→ O (G) as follows. We begin by orienting all edges in C from V 1 to V 2 . Then for any i ∈ {1, 2}, we orient the edges of the induced subgraph G[V i ]. We add a new vertex v 0 and an edge between v 0 and each vertex with an odd degree in G[V i ] if it is not eulerian and we consider a decomposition of its edges into edge-disjoint cycles. We orient each of these cycles as a directed cycle. Removing v 0 if necessary, the imbalance of each vertex in

G[V i ] is now in {-1, 0, 1} which implies that ∀v ∈ V we have |d + Λ (v) -d - Λ (v)| ≥ d(v) 2 -1, hence, MAXIM(G) ≥ δ G 2 -1.
From the proof proposed above, it is easy to see that when

δ G ≡ 0[4] then MAXIM(G) ≥ δ G 2 while MAXIM(G) ≥ δ G -1 2 when δ G is odd and MAXIM(G) ≥ δ G 2 -1 when δ G ≡ 2[4]
. This leads to an approximation algorithm whose ratio is 1

2 (resp. 1 2 -1 2δ , 1 2 -1 δ ) when δ G ≡ 0[4], (resp. δ G is odd, δ G ≡ 2[4]).

Exact algorithm for cacti

The class of graphs defined in the previous section is a special case of cacti. A cactus is a connected simple graph for which every edge belongs to at most one simple cycle. Equivalently, a cactus is a connected graph for which every block, or maximal subgraph with no cut-vertex, is a single edge or a cycle. We will start by recalling the structure induced by the blocks of a graph.

Definition 10 Let G = (V, E) be a graph, V B the set of its blocks and V C the set of its cutvertices. The block tree of G is the graph T

= (V B ∪ • V C , E ) where E = {Zu|Z ∈ V B , u ∈ V C and u ∈ V (Z)}.
Observe that the block tree of a connected graph is a tree [START_REF] Diestel | Graph Theory[END_REF]. In Figure 6 we have an example of a cactus graph G (a), the isolation of its blocks (b) and finally its block tree T (c).

The next lemma is related to the minimum degree of a cactus.

Lemma 11 Let G be a cactus graph,

δ G ≤ 2.
Proof. Let G be a cactus graph and T its block tree. Let u ∈ V (T ) be a leaf of T . By the definition of a cut vertex, u corresponds necessarily to a block of G. If u corresponds to a bridge of G, then one of its endpoint (the one that is not a cutvertex) is a leaf of G which implies δ G =1. If u corresponds to a cycle of G, being a leaf of T , it contains only one cutvertex of G and therefore the degree of its other vertices equals 2. (c) And the block tree T : cut vertices ( ), even cycles ( ), odd cycles ( ) and bridges ( )

The previous lemma automatically provides an upper bound for MAXIM(G).

Proposition 12 Let G be a cactus,

MAXIM(G) ≤ 2.
Note that an edge of a cactus is a single edge block if and only if it is a bridge. We have already characterized which of the cacti verify MAXIM(G) = 0, and the previous result states that the only two other possibilities are 1 or 2. The following will permit us to determine which. Let G = (V, E) be a cactus and T = (V B ∪ • V C , E ) its block tree, a subset A ∈ V B will hereafter refer to a subset of vertices of T as well as the subgraph consisting in the union of the blocks of G corresponding to these vertices. We define for a cactus G the smallest subset S ⊆ V B containing all even cycles of G in addition to all vertices of T satisfying one the following conditions:

• If Y ∈ V B corresponds to an odd cycle of G that shares a cut-vertex with a cycle or with two bridges contained in S, then Y ∈ S,

• if Y ∈ V B corresponds to a bridge of G that shares a cut-vertex with a block contained in S, then Y ∈ S.

In Figures 6(a

S = V B

Theorem 13 Let G be a cactus,

MAXIM(G) = 2 ⇐⇒ S = V B and δ G = 2.
The idea of this result and its proof is that if we have a cactus G, we consider the subgraph S 0 of G consisting in the union of all the even cycles of G and that can be oriented with imbalance at least 2. Then we can extend the orientation of S 0 into an orientation of S, keeping an imbalance of at least two for each vertex with at least two oriented edges. Now if δ G = 2 and S = V B , we obtain an orientation of G with imbalance at least 2. Moreover, for a cactus G, the subset S can be computed in polynomial time by a basic search on the block tree of G which means that we can derive a polynomial time algorithm solving MAXIM for any input cactus.

In order to prove Theorem 13, we first show two lemmas that will be useful in the proof of our theorem.

Lemma 14 Let G = (V, E) be a graph, cc ∈ E a bridge of G. Let us call G c the connected component of G\cc containing c and G c c the graph obtained by adding c and cc to the connected component of G\cc containing c (see Fig. 8). Then

MAXIM(G) ≤ max Λ ∈ - → O (G c ) min( min v∈V (G c )\{c} |d + Λ (v) -d - Λ (v)|, |d + Λ (c) -d - Λ (c)| + 1).
+ Λ (c) -d - Λ (c)| ≤ |d + Λ |Gc (c) -d - Λ |Gc (c)| + 1. Moreover, MAXIM(G) = min v∈V |d + Λ (v) -d - Λ (v)| ≤ min v∈V (G c )\{c} |d + Λ |Gc (v) -d - Λ |Gc (v)| which yields MAXIM(G) ≤ min( min v∈V (G c )\{c} |d + Λ |Gc (v) -d - Λ |Gc (v)|, |d + Λ |Gc (c) -d - Λ |Gc (c)| + 1) ≤ max Λ ∈ - → O (G c ) min( min v∈V (G c )\{c} |d + Λ (v) -d - Λ (v)|, |d + Λ (c) -d - Λ (c)| + 1).
Lemma 15 Let G be a cactus such that δ G = 2. Then there exists a cycle of G with at most one gate (vertex adjacent to any vertex not belonging to the cycle).

Proof. Let T be the block tree of G. If T has no leaf, then it is a vertex graph, hence G is a cycle which necessarily has no gate. If T has a leaf l, it necessarily corresponds to a block of G. If l was a bridge, the degree of its endpoint in G which is not a cutvertex would be 1, hence l is a cycle of G. And being a leaf in T , it has at most one gate in G.

Proof (Theorem 13).

• ⇐ We assume that S = V B and δ G ≥ 2. From Proposition 12, we know that MAXIM(G) ≤ 2. We will build an orientation

Λ ∈ - → O (G) such that min v∈V |d + Λ (v) -d - Λ (v)| = 2.
We start by orienting the edges of the subgraph S 0 consisting in the union of all the even cycles of G. S 0 having no odd cycles, it is bipartite and we can therefore choose an orientation of the edges of S 0 such that |d +

Λ |S 0 (v) -d - Λ |S 0 (v)| = d S 0 (v) ≥
2, ∀v ∈ V (S 0 ). We now recursively extend Λ to the rest of the blocks in S ensuring an imbalance of at least 2 for each vertex adjacent to at least two oriented edges. Let Z ∈ V B be an unoriented block of G that is either:

• an odd cycle of G sharing a cut-vertex with an oriented cycle or two oriented bridges, • a bridge sharing a cut vertex with an oriented block. If there was no such block and the graph G was not totally oriented, the set of oriented blocks of G denoted by #» S would contradict the minimality of S. If Z is an odd cycle, we choose a cut vertex c of Z adjacent to oriented edges and name the vertices of

B c = v 1 v 2 • • • v k = c. We assign: • Λ (v i v i+1 ) = # » v i v i+1 if i is odd; # » v i+1 v i otherwise , ∀i ∈ 1, k -1 .
Let us now consider the imbalance of the vertices of Z. Since c is adjacent to either a cycle or two bridges in #» S , it is adjacent to at least two edges in #» S and therefore

|d + Λ | #» S (c) -d - Λ | #» S (c)| ≥ 2 according to our inductive hypothesis. Since |d + Λ |Z (c) - d - Λ |Z (c)| = 0, |d + Λ (c) -d - Λ (c)| = |d + Λ | #» S (c) -d - Λ | #» S (c)| ≥ 2. If there is another cut- vertex c of Z that is adjacent to a block in #» S such that d + Λ | #» S (c ) -d - Λ | #» S
(c ) and

d + Λ |Z (c ) -d - Λ |Z (c )
do not have the same sign, then we switch the assignment of Λ of the edges of the whole connected component of #» S containing c for its opposite. Necessarily, c is the only vertex this connected component shares with Z otherwise Z would be contained in a bigger block of G. Then doing so, the imbalance of all vertices is left unchanged except for that of c which is now equal to |d

+ Λ | #» S (c ) - d - Λ | #» S (c )| + |d + Λ |Z (c ) -d - Λ |Z (c )| = |d + Λ | #» S (c ) -d - Λ | #» S (c )| + 2.
This process is repeated for all the cut-vertices c of Z different from c adjacent to a block in #» S to be such that

|d + Λ (c ) -d - Λ (c )| ≥ 2. If u ∈ V (Z) is not a cut-vertex, then |d + Λ (u) -d - Λ (u)| = |d + Λ |Z] (u) -d - Λ |Z]
(u)| = 2 and Λ becomes an orientation of #» S ∪ {Z} with imbalance at least two for all the vertices of G adjacent to at least two oriented edges. If Z is a bridge, we take c one of its endpoints adjacent to an oriented edge, we call u the other one and assign

Λ (cu) = #» cu if d + Λ | #» S (c) > d - Λ | #» S (c); #» uc otherwise.
Concerning the imbalance of c, by inductive hypothesis, |d

+ Λ #» S (c) -d - Λ #» S (c)| ≥ 1, then |d + Λ (c) -d - Λ (c)| = |d + Λ | #» S (c) -d - Λ | #» S (c)| + |d + Λ |Z (c) -d - Λ |Z (c)| ≥ 2. If u is ad- jacent to a block in #» S as well and d + Λ | #» S (u) -d - Λ | #» S (u) and d + Λ |Z (u) -d - Λ |Z (u) do
not have the same sign then we switch the assignment of Λ of the edges of the whole connected component of #» S containing u for its opposite. This connected component necessarily doesn't contain c otherwise z would be contained in a bigger block of G. Then doing so, the imbalance of all vertices is left unchanged except for that of u which is now equal to |d

+ Λ | #» S (u) -d - Λ | #» S (u)| + |d + Λ |Z (u) -d - Λ |Z (u)| = |d + Λ | #» S (u) -d - Λ | #» S (u)| + 1 ≥ 2.
Λ thus becomes an orientation of #» S ∪ {Z} with imbalance at least two for all the vertices of G adjacent to at least two oriented edges.

We now add Z to #» S and proceed like this for all blocks Z in S\ #» S until #» S = S. Now since V B = S and δ G = 2, we conclude that Λ is an orientation of all the edges of G with an imbalance equal to 2. In Fig. 9 can be found the orienting process of the cactus presented in Fig. 7. First, the even cycles are oriented (Fig. 9(a)), then the blocks adjacent to the even cycles (Fig. 9(b)) and then iteratively the unoriented blocks adjacent to oriented blocks (Fig. 9(c),(d), (e) and (f)). In Fig. 9(c) and (e), the vertices with imbalance zero are circled in red, and in the next step, the orientation is reversed on one of the subtree where the circled vertex is the root in order to ensure an orientation imbalance of at least 2.

• ⇒ If δ G < 2 then MAXIM(G) < 2. So we assume that δ G = 2 and S V B . Let c ∈ V ( S) ∩ V (S)
. Belonging to both V (S) and V ( S), c must belong to at least two different blocks of G and is therefore a cutvertex of G. Let Z be a block in S adjacent to c, Z is necessarily a bridge of G otherwise all the blocks adjacent to Z would be in S thus contradicting c ∈ V ( S), and for the same reason, Z is the only bridge in S adjacent to c. Calling c the endpoint of Z that is not c and G c the subgraph of G obtained by taking the connected component of G\cc containing c, we are in the conditions of lemma 14 and thus we obtain

MAXIM(G) ≤ max Λ ∈ - → O (G c ) min( min v∈V (G c )\{c} |d + Λ (v) -d - Λ (v)|, |d + Λ (c) -d - Λ (c)| + 1).
Proceeding like this for all c ∈ V ( S) ∩V (S) yields that MAXIM(G) is smaller than

max Λ ∈ - → O ( S)
min( min

v∈V ( S)\V (S) |d + Λ (v) -d - Λ (v)|, min v∈V ( S)∩V (S) |d + Λ (v) -d - Λ (v)| + 1). Now if we choose a connected component S0 of S we get that MAXIM(G) is smaller than max Λ ∈ - → O ( S0 )
min( min

v∈V ( S0 )\V (S) |d + Λ (v) -d - Λ (v)|, min v∈V ( S0 )∩V (S) |d + Λ (v) -d - Λ (v)| + 1).
Now we show that the right-hand part of the previous inequality is lower than or equal to 1. Suppose it equals 2 and let Λ ∈ -→ O ( S0 ) satisfying min( min

v∈V ( S0 )\V (S) |d + Λ (v) -d - Λ (v)|, min v∈V ( S0 )∩V (S) |d + Λ (v) -d - Λ (v)| + 1) ≥ 2. ( 3
)
Thus we have d S0 (v) ≥ 2, ∀v ∈ V ( S0 )\V (S) and we know that for any v ∈ V ( S0 ) ∩ V (S), all the blocks in S0 adjacent to v are odd cycles, hence d S0 (v) ≥ 2. So δ S0 ≥ 2 and according to lemma 15, there is a cycle C of S0 with at most one gate. If C has no gate then it means that S0 consists only of C and since we know that all the cycles of S0 are odd, it directly contradicts the existence of Λ . Hence C has exactly one gate g.

So for all v ∈ V (C)\{g}, |d + Λ (v) -d - Λ (v)| = |d + Λ |C (v) -d - Λ |C (v)| and if we name the vertices of C g = v 1 v 2 • • • v k = g the assignment of Λ must be • Λ (v i v i+1 ) = # » v i v i+1 if i is odd; # » v i+1 v i otherwise , ∀i ∈ 1, k -1 .
or its reverse so that Λ satisfies our assumption. Thus we have max

Λ ∈ - → O ( S0 )
min( min

v∈V ( S0 )\V (S) |d + Λ (v) -d - Λ (v)|, min v∈V ( S0 )∩V (S) |d + Λ (v) -d - Λ (v)| + 1) = max Λ ∈ - → O ( S0 \C)

min( min

v∈V ( S0 \C)\V (S)

|d + Λ (v) -d - Λ (v)|, min v∈V ( S0 \C)∩V (S) |d + Λ (v) -d - Λ (v)| + 1).
If there exists a vertex of degree one in S0 \C then it is adjacent to a bridge in S0 and is thereofre in V ( S\C)\V (S), thus contradicting (3). So we assume that δ S0 \C = 2 and we can reiterate the same process with another odd cycle with exactly one gate until we are left with an odd cycle C end with no gates and conclude that max

Λ ∈ - → O (C end )
min( min

v∈V (C end )\V (S) |d + Λ (v)-d - Λ (v)|, min v∈V (C end )∩V (S) |d + Λ (v)-d - Λ (v)|+1) ≥ 2;
Since this is impossible for an odd cycle, we deduce that (3) is wrong. Hence, MAXIM(G) ≤ 1.

As already mentioned, Theorem 13 leads to a simple polynomial-time algorithm to compute MAXIM(G) for cacti. Starting from the set S 0 of even cycles, we add blocks to S using the two operations defined above: bridges sharing a cut-vertex with a block in S, and odd cycles sharing a cut-vertex with either a cycle or two bridges that are already in S, are added to S.

In this section, we gradually introduce two formulations for the MAXIM problem. For our purposes, we shall consider the original graph G = (V, E) is directed (consider any arbitrary orientation) and let B ∈ {-1, 0, 1} |V |×|E| stand for its incidence matrix, i.e., the column corresponding to the arc uv (or, equivalently, to the edge uv directed from node u to node v), has only nonzero entries in the rows corresponding to the nodes u and v: B u,uv = 1 and B v,uv = -1, respectively.

In order to describe an orientation of the graph G, we take orientation variables x ∈ {-1, 1} |E| interpreted as follows. For each edge uv ∈ E which is originally directed from node u to node v: if x uv = 1 then uv is directed from u to v (i.e., the orientation is the same as the original one) and is directed from v to u otherwise (i.e., the edge is "reversed" with respect to the original orientation). Then if we look at the product of B with an orientation vector x ∈ {-1, 1} |E| we obtain

B v x = d + x (v)-d - x (v), ∀v ∈ V , where d + x (v) (resp. d - x (v))
is the outdegree (resp. indegree) of v ∈ V in G w.r.t. the orientation described by x and B v denotes the row of the matrix B which corresponds to node v. Hence the MAXIM problem can be expressed as the following non-linear formulation.

       max h s.t. h ≤ |B v x|, ∀v ∈ V x ∈ {-1, 1} |E| .
Let us derive from the preceding non-linear formulation an equivalent linear formulation. To that purpose, we remove the absolute value of the constraint by squaring it : h 2 ≤ (B v x) 2 , ∀v ∈ V . Since it still is not linear, we have to consider variables representing the product of two variables and for that we substitute the x variables by their 0-1 version. So developing, we obtain

(B v (2x -1)) 2 = ∑ uv∈E B v,uv (2x uv -1) 2 = ∑ uv∈E B 2 v,uv (2x uv -1) 2 + 2 ∑ uv,wv∈E uv =wv B v,uv B v,wv (2x uv -1)(2x wv -1) = ∑ uv∈E (4x 2 uv -4x uv + 1) + 2 ∑ uv,wv∈E uv =wv B v,uv B v,wv (4x uv x wv -2x uv -2x wv + 1) =d(v) + 2 ∑ uv,wv∈E uv =wv B v,uv B v,wv (4x uv x wv -2x uv -2x wv + 1).
Furthermore, since maximizing h is equivalent to maximizing its square root, substituting h 2 by h, we obtain the following formulation.

         max h s.t. h ≤ d(v) + 2 ∑uv,wv∈E uv =wv B v,uv B v,wv (4x uv x wv -2x uv -2x wv + 1), ∀v ∈ V x ∈ {0, 1} |E| .
In order to linearize it, we introduce product variables z uv,wp ∈ {0, 1}, uv, wp ∈ E, uv = wp representing the variables product x uv x wp . For a pair of edges (uv, wp) ∈ E 2 , uv = wp, we add the constraints z uv,wp ≤ x uv , z uv,wp ≤ x wp and z uv,wp ≥ x uv + x wp -1 so as to force z uv,wp = x uv x wp . We can relax the integer constraint on the z variables and we obtain the following mixed integer linear programming formulation.

(MIP1)                      max h s.t. h ≤ d(v) + 2 ∑uv,wv∈E uv =wv B v,uv B v,wv (4z uv,wv -2x uv -2x wv + 1), ∀v ∈ V z uv,wp ≤ x uv z uv,wp ≤ x wp z uv,wp ≥ x uv + x wp -1 , ∀uv, wp ∈ E, uv = wp x ∈ {0, 1} |E| , z uv,wp ≥ 0, uv, wp ∈ E, uv = wp, h ∈ R.
Theorem 16 For any graph G,

MIP1(G) = MAXIM(G),
Where MIP1(G) is the square root optimal of the objective value of MIP1 for G.

Proof. x ∈ {0, 1} |E| covers all the possible orientations of G and for every vertex v ∈ V , the first constraint is equivalent to h

≤ (d + x (v) -d - x (v)) 2 .
Thus we have a first mixed integer linear programming formulation for our problems with O(m 2 ) variables, O(m) of which are integer variables and O(m 2 ) constraints.

Let us take a look at the linear program obtained by relaxing the integer constraint of MIP1 on an input graph G = (V, E), and let us consider the triplet (x l p , z l p , h l p ) where x l p uv = 1 2 , ∀uv ∈ E; z l p uv,wp = 0 for all pairs of edges uv, wp ∈ E that share no endpoint;

z l p uv,wv = 1+B v,uv B v,wv 4
for all pairs of edges uv, wv ∈ E (i.e. all pairs of edges in E that share an endpoint), and h l p = δ 2 G .

Lemma 17 (x l p , z l p , h l p ) is a feasible solution of the linear relaxation of MIP1 whith objective value δ 2 G .

Proof. Observe that ∀uv, wp ∈ E, 0 = x l p uv + x l p wp -1 ≤ z l p uv,wp ≤ x l p uv = x l p wv = 1 2 .

Moreover, ∀v ∈ V ,

d(v) + 2 ∑ uv,wv∈E uv =wv B v,uv B v,wv (4z l p uv,wv -2x l p uv -2x l p wv + 1) =d(v) + 2 ∑ uv,wv∈E uv =wv B v,uv B v,wv (1 + B v,uv B v,wv -1 -1 + 1) =d(v) + 2 ∑ uv,wv∈E uv =wv (B v,uv B v,wv ) 2 =d(v) + 2 ∑ uv,wv∈E uv =wv 1 =d(v) + (d(v) -1)d(v) =d(v) 2 ≥ δ 2 G .
The previous lemma proves that the optimal value of the linear relaxation of MIP1 is at least the minimum degree of the input graph squared, which corresponds to the trivial upper bound of MAXIM(G).

We present a second formulation with reduced number of variables and constraints. This second formulation involves the same orientation variables x ∈ {-1, 1} |E| we described earlier and a second type of variables that are binary: indicator variables y v k with v ∈ V a vertex of G and k ∈ -d(v), d(v) . They have the following interpretation:

y v k = 1 if and only if B v x = d + x (v) -d - x (
v) = k, so that the following equation trivially holds

∑ k∈ -d(v),d(v) ky v k = B v x, ∀v ∈ V.
Given the interpretation for the variables y, among those of the form y v k , for some fixed node v ∈ V , exactly one of them has value 1. Thus, the following constraints are satisfied

∑ k∈ -d(v),d(v) y v k = 1, ∀v ∈ V.
Notice that for a vertex v ∈ V , the difference between its oudegree and indegree w.r.t. any orientation and its degree have the same parity. Thus instead of running k

through -d(v), d(v) , we can limit to k ∈ -d(v), d(v) , s.t. k ≡ d(v)[2], i.e. the only possible values of d + x (v) -d - x (v) when x runs through {-1, 1} |E| .
Then we can show the MAXIM problem may be formulated as the mixed integer program

(MIP2)                        max h s.t. h ≤ ∑ k∈ -d(v),d(v) k≡d(v)[2] min(|k|, δ G )y v k , ∀v ∈ V ∑ k∈ -d(v),d(v) k≡d(v)[2] y v k = 1, ∀v ∈ V ∑ k∈ -d(v),d(v) k≡d(v)[2] ky v k = B v x, ∀v ∈ V x ∈ [-1; 1] |E| , y v k ∈ {0, 1}, ∀(v, k) ∈ V × -d(v), d(v) , s.t. k ≡ d(v)[2], h ∈ R.
Theorem 18 For any graph G,

MIP2(G) = MAXIM(G),
Where MIP2(G) is the optimal objective value of MIP2 for G.

Proof. First, if the orientation variables x were constrained to be integers, since

y v k = 1 if and only if B v x = d + x (v)-d - x (v) = k and x ∈ {0, 1}
|E| covers all the possible orientations of G and for every vertex v ∈ V , the first and third constraints lead to h ≤ |d +

x (v)-d - x (v)| and the optimal objective value of the resulting formulation would equal MAXIM(G). Now we know that the incidence matrix B is totally unimodular. Hence, there exists an integer optimal solution (x , y , h ) of MIP2. If x ∈ {-1, 1} |E| then (x , y , h ) is solution of the all-integer version of MIP2 mentioned above and therefore optimal, i.e. its objective value is MAXIM(G). Otherwise x describes a partial orientation of G, i.e. for an edge uv ∈ E, if x uv = 1 then the original orientation of the edge is preserved, if x uv = -1 then it is reversed and if x uv = 0 then the edge is left unoriented. We know that for each vertex v ∈ V , B v x ≡ d(v) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF]. So the number of edges adjacent to v on which x is non-zero must have the same parity as the degree of v. In other words, the number of edges adjacent to v on which x is zero must be even. That is to say, let

E = {uv ∈ E|x uv = 0} and G = (V, E ), d G (v) ≡ 0[2] for each vertex v ∈ V . Since
G is eulerian, we can take a cycle of G , orient it in a way that does not change the imbalance of any vertex, remove it and proceed like this until there are no more edges in G . The resulting (complete) orientation can be described by an orientation vector x ∈ {-1, 1} |E| and the triplet (x , y , h ) is a solution of the all-integer version of MIP2 having the same objective value as (x , y , h ), hence it is optimal and therefore equal to MAXIM(G).

We now have a second mixed integer linear programming formulation of MAXIM with O(m + n) variables, O(m) of which are integer variable and O(n) constraints.

Let us consider the triplet (x l p , y l p , h l p ) where x l p uv = 0, ∀uv ∈ E; y v,l p k = 0, ∀(v, k) ∈ V × -d(v) + 1, d(v) -1 , s.t. k ≡ d(v) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF]; and y v,l p -d(v) = y v,l p d(v) = 1 2 , ∀v ∈ V . Observe that (x l p , y l p , h l p ) is a feasible solution of the linear relaxation of MIP2 whith objective value δ G . In other words, the linear relaxation MIP2 is generally weak. Let us then try to strengthen it using some valid inequalities.

Remember from Section 2 that it is easy to check whether MAXIM(G) = 0. One can then set variables y v 0 to 0 when MAXIM(G) > 0. We also know from the discussion at the end of Section 3 that MAXIM(G) can almost not be less than δ G 2 . More precisely, if δ G ≡ 0 [START_REF] Bang-Jensen | Orientations of graphs and digraphs in 'Digraphs: Theory, Algorithms and applications[END_REF] then MAXIM(G) ≥ δ G 2 while MAXIM(G) ≥ δ G -1 2 when δ G is odd and MAXIM(G) ≥ δ G 2 -1 when δ G ≡ 2 [START_REF] Bang-Jensen | Orientations of graphs and digraphs in 'Digraphs: Theory, Algorithms and applications[END_REF]. More generally, if l is a known lower bound for MAXIM(G), then all variables y v k for |k| < l can be fixed to 0. To find such a lower bound, we use a standard greedy algorithm to find a locally maximum cut and orient edges as described in the proof of Theorem 9.

Let u be an upper bound for MAXIM(G). We already know that MAXIM(G) ≤ δ G , so we can assume that u ≤ δ G . Consider the following inequality

h ≤ u - n ∑ v=1 ∑ k∈ 0,u-1 k≡d(v)[2] λ v k (y v k + y v -k ), ∀λ ∈ Λ u (4)
where the vertices of G are numbered from 1 to |V | = n, and

Λ u = λ = (λ v k ) (v,k)∈ 1,n × 0,u-1 ∈ N nu λ v k+1 ≤ λ v k , ∀(v, k) ∈ 1, n × 0, u -2 ∑ n v=1 λ v k = u -k, ∀k ∈ 0, u -1 .
Observe that coefficients λ v k are non-negative integer numbers and are non increasing in k. For each k, there exists only one v such that λ v k+1 = λ v k -1 while λ w k+1 = λ w k for any w = v. Let us prove that inequalities (4) are valid inequalities for the convex hull of feasible solutions of MIP2 denoted by P 2 .

Proposition 19 Inequalities (4) are valid for P 2 .

Proof. Consider a feasible solution (x, y, h) of P 2 . If y v k = 0 and y v -k = 0 for any v ∈ 1, n and any k ∈ 0, u -1 , then ∑ n v=1 ∑ k∈ 0,u-1 k≡d(v) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF] λ v k (y v k + y v -k ) = 0 and inequality (4) becomes h ≤ u. The last is valid since u is an upper bound for MAXIM(G).

Let us now assume that h ≤ u -1, then there exist v ∈ 1, n and k ≤ u -1 such that either y v k or y v -k is equal to 1 while y w k = 0 for any w ∈ 1, n and k such that |k | < k. Using the fact that y w k is non increasing, we deduce that ∑ k ∈ 0,u-1 k ≡d(w) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF] λ w k (y w k + y w -k ) ≤ λ w k ∑ k ∈ k,u-1 k ≡d(w) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF] (y w k + y w -k ) ≤ λ w k . Summing up these inequalities for all w and using the fact that ∑ n v=1 λ v k = uk leads to h ≤ k which is valid by k definition. Observe that the first family of inequalities included in MIP2 can be seen as a special case of inequalities [START_REF] Bang-Jensen | Orientations of graphs and digraphs in 'Digraphs: Theory, Algorithms and applications[END_REF].

Let us now study the separation problem of inequalities (4).

Proposition 20 Inequalities (4) can be separated in polynomial time.

Proof. Given a fractional solution (x, y, h), one can check whether an inequality of type (4) is violated by looking for coefficients λ ∈ Λ u maximizing ∑ n v=1 ∑ k∈ 0,u-1 k≡d(v) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF] λ v k (y v k + y v -k ). Remember that for each k, there exists only one v such that λ v k+1 = λ v k -1 while λ w k+1 = λ w k for any w = v. Let v k be such v. Then ∑ n v=1 ∑ k∈ 0,u-1 k≡d(v) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF] λ v k (y v k + y v -k ) can be written as ∑ k∈ 0,u-1 ∑ k ∈ 0,k (y

v k k + y v k -k
). This immediately leads to the following algorithm. First, all λ v k are initially set to 0. Then, we select v u-1 maximizing ∑ k∈ 0,u-1 k≡d(v) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF] (y v k + y v -k ) and we increment by 1 all λ v u-1 k

:

λ v u-1 k = λ v u-1 k
+ 1 for any k ≤ u -1. More generally, for each w ∈ 0, u -1 , we select v w maximizing ∑ k∈ 0,w k≡d(v) [START_REF] Asahiro | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree[END_REF] (y v k + y v -k )

and we increment by 1 all λ v w k for k ≤ w. The algorithm has clearly a polynomial-time complexity.

Fig. 1 :

 1 Fig. 1: The vertices of C in G are left unchanged imbalance-wise, the other vertices of C are set to 2 and in the end |d+ Λ (u 0 )d - Λ (u 0 )| ≥ |d + Λ (u 0 )d - Λ (u 0 )| > 0 .

Fig. 2 :

 2 Fig. 2: The vertices of C in G are left unchanged imbalance-wise except for v which is set to 2, like the other vertices of C and in the end |d+ Λ (u 0 )d - Λ (u 0 )| ≥ |d + Λ (u 0 )d - Λ (u 0 )| > 0 .

Fig. 3 :

 3 Fig.3: In both cases, concatenating p with p even or p odd yields an even cycle in G

Fig. 6 :

 6 Fig. 6: Building the block tree

  ) and 7 are examples of two cacti along with their subsets S.

Fig. 7 :

 7 Fig. 7: A graph G such that δ G = 2 and S = V B .

Fig. 8 :

 8 Fig. 8: A graph G and a bridge cc .

Fig. 9 :

 9 Fig. 9: Orienting the edges of G verifying δ G = 2 and S = V B in such a way that MAXIM(G) = 2.

Table 1 :

 1 Numerical results graph L MIP1 U MIP1 t MIP1 v LP2 t LP2 L MIP2 U MIP2 t MIP2 nb (4) nb[START_REF] Chung | Strongly connected orientations of mixed multigraphs[END_REF][START_REF] Chvatal | Distances in orientation of graphs[END_REF] nb[START_REF] Biedl | Balanced vertex-orderings of graphs[END_REF][START_REF] Chrobak | Planar orientations with low out-degree and compaction of adjacency matrices[END_REF] |V | |E| δ G

	K 10	5	5 25.17	5 0.01	5	5 0.03	4	2	0 10	45 9
	K 50			25 1.56	25	25 3.27 24	12	0 50 1225 49
	K 150 K 200	full memory	75 143.37 99 427.48	75 99	75 288.36 74 99 859.44 100	52 75	150 11175 149 0 200 19900 199
	K 225			150 603.84 112 147 296.16 74	46	0 225 25200 224
	G 4

Acknowledgments

The authors wish to thank the associate editor and the anonymous referees for many valuable comments and suggestions that have led to a substantially improved paper.

A second family of valid inequalities is defined for each vertex v, each integer number p ∈ 1, d(v) and each subset of p edges incident to v. ∑ {{v j 1 },...,{v j i },...,{v j p }}⊂cut({v}) B v,{v j i } x {v j i } + ∑ k∈ 0,p-1

Proposition 21 Inequalities (5) are valid for P 2 .

Proof. If all variables y v 2k-d(v) are equal to 0 for k ∈ 0, p -1 , then inequality ( 5) is implied by the fact that x ∈ [-1; 1] |E| .

Assume that y v 2k 0 -d(v) = 1 for some k 0 ∈ 0, p -1 . This requires that among all edges of cut({v}) there are exactly k 0 (resp. d(v)k 0 ) edges {v j} such that B v,{v j} x {v j} = 1 (resp. B v,{v j} x {v j} = -1). Consequently ∑ {{v j 1 },...,{v j i },...,{v j p }}⊂cut({v}) B v,{v j i } x {v j i } is upper bounded by k 0 -(pk 0 ) = 2k 0p. Moreover, we have ∑ k∈ 0,p-1 2(pk)y v 2k-d(v) = 2(pk 0 ). Inequality (5) immediately follows.

The separation problem of inequalities ( 5) is also easy to solve.

Proposition 22 Inequalities (5) can be separated in polynomial time.

Proof. Given a fractional solution (x, y, h), for each vertex v and any p ∈ 1, d(v) , we order the edges of cut({v}) in descending order according to B v,{v j} x {v j} and we select the first p edges. Then a violated inequality can be detected by comparison of

Let us now consider any cycle C and the two following inequalities.

Proposition 23 Inequalities (6) and (7) are valid for P 2 . Proof. Let us focus on the validity of inequalities (6) (inequalities [START_REF] Chrobak | Planar orientations with low out-degree and compaction of adjacency matrices[END_REF] being provable in the same way). After orientation of the edges of the cycle C , let C + be the set of vertices of C for which their two incident edges are oriented outward from these vertices to their neighbours. We also define C -in the same way be considering vertices having two edges of the cycle oriented from their neighbours to them. The remaining set of vertices of the cycle is denoted by C * (they have an incoming incident edge and an outgoing incident edge). These definitions are illustrated on Fig. 10. It is now easy to see that we always have

Proposition 24 Inequalities (6) and (7) can be separated in polynomial time.

Proof. Let us again focus on inequalities ( 6) since ( 7) can be separated in a similar way. Given a fractional solution (x, y, h), we need an algorithm to either compute a cycle

) < 0 or to certify that such a cycle does not exist. For each edge uv, let us consider a weight

). Then we clearly have

We are then looking for an undirected cycle having a negative total weight. This can be done, for example, by computing a minimum weight / 0-join, where the last is a set of edge disjoint cycles. This can be done using the algorithm of [START_REF] Edmonds | Matching, Euler tours and the Chinese postman problem[END_REF]. Notice that this algorithm can provide many negative weight cycles with some 0 weight cycles. If the total weight of the / 0-join is strictly negative, a negative weight cycle can be easily extracted. A different algorithm can also be found in [START_REF] Ben-Ameur | Designing Steiner Networks with Unicyclic Connected Components: An Easy Problem[END_REF] (see section 6 of the reference).

Given any clique K and any number p ∈ 1, |K | , we consider the two following inequalities.

Inequalities ( 8) can be seen as a generalization of the obvious inequalities

≤ 1 obtained when p = 1.

Proposition 25 Inequalities (8) and (9) are valid for P 2 .

Proof. We can focus on inequalities [START_REF] Chung | Strongly connected orientations of mixed multigraphs[END_REF]. To maximize the left hand side of (8), we can assume that all edges in cut(K ) are oriented from K to outside (this is due to the fact that the coefficient pk increases when k decreases). Then, y v d(v)-2k = 1 is equivalent to say that exactly k edges, inside K and incident to v, are oriented from v to outside. Observe that inequality ( 8) is equivalent to

Let q be the number of vertices of K whose outdegree (in the graph induced by K ) is at most p -1 after orientation. The left hand side of ( 10) is given by pq. The sum of the q lowest outdegrees is exactly given by ∑ v∈K ∑

. Using landau's theorem for tournaments [START_REF] Landau | On dominance relations and the structure of animal societies III. The condition for a score structure[END_REF], we can write that

2 . Adding p(p+1)

to both sides, we get

. Moreover, from (qp) 2 ≥ qp, we get that p 2 +q 2 +p-q 2 ≥ pq proving [START_REF] Degraaf | Grid Minors of Graphs on the Torus[END_REF].

To separate inequalities [START_REF] Chung | Strongly connected orientations of mixed multigraphs[END_REF], the following heuristic is used. Given a fractional solution (x, y, h), for each vertex v and any p ∈ 1, d(v) + 1 , we use a greedy approach to find a locally maximum-weight clique where the weight of any vertex u ∈ V is

. We start with K := {v} and then recursively find u = arg max{∑

Computational results

In order to assess the performance of formulations MIP1 and MIP2, we present some computational results related to a wide variety of graphs. All algorithms were written in C++ calling IBM's ILOG CPLEX optimizer c and experiments have been performed using a processor 1.9GHzx4, 15.6GB RAM with four cores.

While the implementation of MIP1 is pretty straightforward: the model is created with all inequalities described in Section 5 and then the mixed-integer-linearprogramming solver of CPLEX is run with default parameters, the implementation of MIP2 needs to be detailed.

First of all, an initial solution is determined by computing a locally maximum cut using the standard greedy algorithm described in the proof of Theorem 9. A starting integer solution is then known for both formulations MIP1 and MIP2.

For both formulations and each instance, we set a limited total processing time of 15 minutes (900 seconds). If this limit is reached, then the process is interrupted and returns both the objective value of the current best integer solution L MIP1 or L MIP2 and the current best upper bound U MIP1 or U MIP2 .

For formulation MIP2, a cutting-plane algorithm is implemented based on the inequalities of Section 5. Inequalities are generated in the following order:

• We look for a violated inequality of the type (4) according to the proof of Proposition 20. • We generate cliques using the heuristic described in the end of section 5 and check for a violated inequalities of the types ( 8) and ( 9). ). If we find a negative weighted cycle, then corresponding inequality of the type ( 6) is violated. We do the same with the weight 1 2

) for an edge vw to find a violated inequality of the type [START_REF] Chrobak | Planar orientations with low out-degree and compaction of adjacency matrices[END_REF]. For the sake of simplicity, inequalities ( 6) and ( 7) are not separated using the algorithms of [START_REF] Edmonds | Matching, Euler tours and the Chinese postman problem[END_REF] and [START_REF] Ben-Ameur | Designing Steiner Networks with Unicyclic Connected Components: An Easy Problem[END_REF] but using a simple integer linear program computing a minimumweight cycle.

After various experimentations, we chose not to put the inequalities of type ( 5) in the cutting-plane phase because when included, while the number of generated inequalities increases excessively with the size of the graph, the optimal objective value of the linear program is left unimproved.

After the addition of violated inequalities, the linear relaxation is solved to get a fractional (x, y, h) solution and the process is repeated until no more violated inequalities can be found. The optimal objective value of the last LP is denoted by v LP2 . Notice that the cutting-plane phase is intentionally limited to less than 10 minutes (600 seconds). Thus, if either no more valid inequalities can be generated or the time spent in the cutting-plane phase reaches 10 minutes, we switch to branch&bound. The time spent in the cutting-plane phase us denoted by t LP2 .

CPLEX's mixed integer programming solver is used with default parameters to solve MAXIM. Notice that some automatic internal cuts are generated by the solver to accelerate the branch&bound. As already mentioned, the total running time is limited to 15 minutes. The time spent in the branch&bound phase is denoted by t MIP2 while the best lower and upper bounds are respectively denoted by L MIP2 and U MIP2 .

For each of the instances we report L MIP1 , U MIP1 , t MIP1 , v LP2 , t LP2 , L MIP2 , U MIP2 , and t MIP2 , where t LP2 , t MIP1 and t MIP2 are expressed in seconds. We also report nb [START_REF] Bang-Jensen | Orientations of graphs and digraphs in 'Digraphs: Theory, Algorithms and applications[END_REF] , nb [START_REF] Chung | Strongly connected orientations of mixed multigraphs[END_REF][START_REF] Chvatal | Distances in orientation of graphs[END_REF] and nb [START_REF] Biedl | Balanced vertex-orderings of graphs[END_REF][START_REF] Chrobak | Planar orientations with low out-degree and compaction of adjacency matrices[END_REF] , respectively the number of inequalities of the type (4), ( 8) & ( 9) and ( 6) & ( 7) generated for each instance G = (V, E) along with |V |,|E| and δ G .

The graph instances used for the computations are denoted as follows:

• K n : the complete graph with n vertices,

• G n k : the n-dimensional grid of length k, i.e. the cartesian product of n paths graphs of length k:

,n 2 : the 2-dimensional grid, i.e. the cartesian product of two path graphs of length n 1 and n 2 :

• tG n k : the n-dimensional toroidal grid of length k, i.e. the cartesian product of n cycless of length k:

,n 2 : the 2-dimensional toroidal grid, i.e. the cartesian product of cycles of length n 1 and n 2 :

• P n,m : a randomly generated planar graph with n vertices and m edges, • R n,m : a randomly generated graph with n vertices and m edges.

More about the toroidal grids can be found in [START_REF] Degraaf | Grid Minors of Graphs on the Torus[END_REF].

Table 1 shows that formulation MIP2 has a significantly better performance than MIP1. On many instances we can observe that the cutting plane algorithm of MIP2 drastically improved the upper bound δ G , sometimes so far as to the optimal objective value as can be seen for example on the complete graphs, the planar graphs or most of the n-dimensional toroidal grids. while the number and nature of the generated inequalities varies a lot, it seems to never grow excessively. We can see that as soon as the size of the instance becomes substantial, formulation MIP1 seems to degenerate, needing too much time and/or memory to be processed, while MIP2 shows its ability to handle large size graphs.

Further research

While computing the most imbalanced orientation of a graph is generally difficult, the problem turns out to be easy for cacti. It may be the same for other graph classes. Characterizing such graph classes would be interesting.

Two mixed integer linear programming formulations of MAXIM have been presented. Several families of valid inequalities have been presented to strengthen one of the two formulations. Exhibition of other families of valid inequalities might be helpful to solve larger size problems.

Finally, one can also the study the weighted version of the most imbalanced orientation problem.

Appendix A Proof of Lemma 6

Let ϕ be a not-all-equal at most 3-SAT formula with n variables {x 1 , • • • , x n } and m clauses {c 1 , • • • , c m } and for all i ∈ 1, n , let k i ∈ N be the number of occurences of x i in ϕ. We assume that there is at least one variable x i that has at least 4 occurences in ϕ (otherwise ϕ is already a not-all-equal at most 3-SAT(3V) formula) and we will build from ϕ a not-all-equal at most 3-SAT(3V) ϕ such that ϕ and ϕ are equisatisfiable as follows.

• For all i ∈ 1, n , if k i ≥ 4 then we introduce k i new variables {x 1 i , • • • , x k i i } and for l ∈ 1, k i we replace the l-th occurence of x i in ϕ with x l i .

• For all i ∈ 1, n , if k i ≥ 4 then we add k i new clauses {c

is an assignment of the variables x i and x l i satisfying ϕ for • ∀ j ∈ 1, m , the values of the literals of c j w.r.t. v and v are piecewise equal so v (c j ) = v(c j ) = TRUE and v is not-all-equal for c j as well as v is;

x i ) = TRUE and v (c k i x i ) = TRUE and v is not-all-equal for each of these clauses since they all consist of two literals having opposite values w.r.t. v .

As an example, for a formula

where x 1 occurs five times and x 3 four so we add nine new variables x

3 , x 2 3 , x 3 3 and x 4 3 and nine new clauses:

Now suppose there exists an assignment v of the x i and x l i satisfying ϕ and let i ∈ 1, n such that k i ≥ 4. If we take a look at the clauses c 1

x i , • • • , c k i x i , we notice that if v (x 1 i ) = FALSE then for c 1

x i to be satisfied, v (¬x 2 i ) = TRUE, i.e. v (x 2 i ) = FALSE, then for c 2 x i to be satisfied, v (¬x 3 i ) = TRUE ...etc. Repeating this argument, we obtain that if v (

Similarly, if v (x k i i ) = TRUE then for c k i x i to be satisfied, v (¬x k i -1 i ) = FALSE, i.e. v (x k i -1 i ) = TRUE, then for c k i -1

x i to be satisfied, v (¬x k i -2 i ) = FALSE ...etc. Hence if v (x k i i ) = TRUE then v (x

Hence for all i ∈ 1, n such that k i ≥ 4, we can replace x 1 i , • • • , x k i i by a unique variable x i and doing so the clauses c 1

x i , • • • , c k i x i become trivial and can be removed and only ϕ remains. So the following assignment of x 1 , • • • , x n : v :

x i → v (x i ) ∀i ∈ 1, n s.t. k i ≤ 3;

satisfies ϕ. We have just shown that ϕ and ϕ are equisatisfiable.


Baptiste Girault

Guillaume Geandier

Dominique Eyidi

Pierre-Olivier Renault

Eric Le Bourhis

Philippe Goudeau

Size effects on the mechanical behavior of nanometric W/Cu multilayers

The mechanical behavior of nanostructured W/Cu composites prepared by ion beam sputtering has been investigated using a method combining X-ray diffraction and tensile testing. Tests were performed on a synchrotron light source to analyze the elastic response of the tungsten phase. Three different microstructures have been analyzed: the specimen composed of the thinner tungsten layers reveals an elastic behavior different from the one expected assuming bulk elastic constants. However, Transmission Electron Microscopy (TEM) and Grazing-Incidence Small-Angle X-ray Scattering (GISAXS) measurements reveal discontinuities in the copper layers. As the strain in the related copper clusters as well grains boundary contributions are not experimentally accessible, atomistic calculation are of utmost importance.

INTRODUCTION

Nanometer scaled materials meet non negligible surface contribution yielding deviations from mechanical bulk materials behavior. Stratified samples have attracted much attention since one dimension can be tailored down to the nano-scale, leading to novel electronic, magnetic, optical and mechanical applications. Despite the number of studies devoted to length scale dependence of strength and deformation mechanisms in nano-scale multilayers [START_REF] Misra | View point set "deformation and ductility of nanoscale metallic multilayers[END_REF][2][3][4][5][6], few of these focus on the mechanical response in the elastic domain. Elastic constants analysis in nanocrystalline metallic thin films and multilayers by means of a method combining X-ray diffraction and tensile testing has been a constant challenge in our laboratory for several years [7][8][9][10]. The present paper focuses on experiments involving stratified W/Cu samples with tungsten layer thicknesses ranging from 10.8 nm down to 1.5 nm and presenting constant average copper layer thickness of 0.2 nm. X-ray measurements were performed at the European Synchrotron Radiation Facility (Grenoble, France).

EXPERIMENTS

Specimen preparation

W/Cu multilayers were deposited by ion-beam sputtering in a NORDIKO 3000 device at room temperature, tungsten being the first deposited layer, on 127.5 µm thick polyimide (Kapton ® ) dogbone foils and on 200 µm and 600 µm thick naturally oxidized Si (001) wafers. The gauge part of dogbone samples has a size of 6 × 15 mm². Sample characteristic data, including the number of (W,Cu) layer pairs and the total film thickness of each specimen, are given in Table I. The film mean residual stresses were evaluated using the curvature method with the dedicated 200 µm Si cantilevers. The global stress states set in thin films were strongly compressive. X-ray diffraction pole figures measurements showed that W layers exhibit both <110> and <111> fiber-texture [11]. X-ray reflectometry measurements combined with atomic concentration determined by EDX (Energy dispersive X-ray) allowed us to establish effective thicknesses shown in Table I However, Transmission Electron Microscopy (TEM) (Fig. 1) and recent Grazing-Incidence Small-Angle X-ray Scattering (GISAXS) [12] investigations have revealed that copper layer may be discontinuous. Thus, W/Cu composites are not exactly multilayers but tungsten matrix containing periodic copper dispersoïd layers.

Tensile testing and X-ray diffraction

Combined tensile tests and XRD measurements were realized in a seven-circle diffractometer at the BM02 beam line of the European Synchrotron Radiation Facility (ESRF, Grenoble, France). A 200 N Deben™ mini-tensile testing device allows performing in situ tensile tests and can be equipped with several load cells (capacity from 5 N to 200 N) according to the chosen force range investigated [7].

The measurement of lattice strains by X-ray diffraction enables to determine the applied or residual strains in crystalline materials. The lattice strain is measured along a direction which is defined with respect to the sample geometry by the angles φ and ψ defined in Fig. 2. The technique based on the well-known "sin 2 ψ method" [START_REF] Noyan | Residual stress measurement by diffraction and interpretation[END_REF][START_REF] Hauk | Structural and residual stress analysis by non destructive methods: evaluation, application, assessment[END_REF] consists in applying a uniaxial tensile force to the film/substrate sample and monitoring the shift of one or several {hkl} peak positions. The applied force is recorded via the load cell supplied on the tensile tester. The elastic strain of tungsten phase is obtained by X-ray measurement of the lattice plane distance defined by:

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ref hkl hkl d d ln ,ψ ϕ ε (1)
where hkl d is the lattice plane distance in tungsten layers when the specimen is submitted The ψ values were chosen with respect to preferred crystallographic orientations set in the layers of each sample, that is <110> and <111> fiber-textured for W layers of dispersoïd composites. Due to the low copper X-ray scattering factor and deposited copper quantities, no diffracting information can be extracted from copper dispersoïd layers. Improved jaws have been used to guarantee specimen flatness during loading which greatly reduced uncertainties.

These measurements dedicated to tungsten elastic constant determination have been performed with numerous load steps ranging from 1.5 N to 17 N. The whole load range was supposed to be included in the sample elastic strain domain (according to prior laboratory tests).

It should be noted that these measurements would not have been possible with a conventional laboratory X-ray source, even with very long acquisition times, since uncertainties are of the same order as the peak shifts; here the X-ray synchrotron source allows performing good quality measurements, with a rather high dynamic, in a quite short recording time (around 2 hours for each loading step).

RESULTS AND DISCUSSION

Results are focused on W-{310} strain measured on W/Cu 1.5/0.2. Interfaces between the substrate and the first tungsten layer and between all W and Cu sub-layers (considered as continuous layers for calculation, in a first approximation) are assumed to be perfect, i.e. the strain is transmitted unchanged through interfaces. In this case, by neglecting the edge effects, a biaxial stress state can be assumed (σ 33 = 0, axis n o 3 being the normal to the specimen surface). Considering bulk elastic constants, it is thus possible to evaluate effective stress applied to tungsten sub-layers and the strain induced from increment load supported by film/substrate sample (using bulk elastic constants). Since W is mechanically isotropic, linear elasticity may be applied and Hooke's law allows estimating the strain expected in W layers for each value of the applied force by means of equation 2:

( ) ( ) W W W W W W W W W W W E E E 22 11 2 22 11 11 , 0 sin 1 σ σ ν ψ σ σ ν σ ν ε ψ ϕ + - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + - + = °= (2)
where E W and ν W refer to the Young's modulus and Poisson's ratio of tungsten layers, σ 11 W is the stress in W layers along the tensile axis (longitudinal stress) and σ 22 W the stress along the perpendicular axis (transversal stress).

Applied stress along tensile direction (σ 11 W ) and induced stress along the perpendicular direction (σ 22 W ) can be calculated as follows:

( )( ) ( )( ) ( )( ) ( )( ) [ ] ( )( ) ( )( ) [ ] ⎪ ⎩ ⎪ ⎨ ⎧ - - + - - = - - + - - + - - = - - = - - = - = W Cu K Cu Cu W K Cu K K W K Cu W W W Cu K Cu Cu W K Cu K K W Cu K W W W W tot W W W W W tot W W W f E f E C f E f E f E B E A C B C A C B B A ν ν ν ν ν ν ν ν ν ν ν ν ν ν ν ν σ σ σ σ 2 2 2 2 2 2 2 2 2 2 22 2 2 11 1 1 1 1 1 1 1 1 1 1 with and (3)
where f K , f W , and f Cu are the volume fractions of the Kapton® substrate, tungsten layers and copper layers, respectively; E K , ν K , E Cu , ν Cu refer to the Young's moduli and Poisson's ratios of the substrate, and copper layers, respectively; σ tot represents the total applied stress, i.e. F/S, S being the specimen transversal section. Experimentally determined values (E K = 5 GPa, ν K = 0.34) were employed for the Kapton® substrate while bulk polycrystalline Poisson's ratios (ν W = 0.28 and ν Cu = 0.343) were considered. X-ray measurements allow thus determining strain associated to each loading increment (first loading state taken as a reference) as a function of the applied stress along the tensile direction. Figure 3 shows the strain determined from W-{310} diffraction peak shift along a particular direction defined by φ = 0° (corresponding to the tensile direction) and ψ = 63.4°. These experimental data concern the W/Cu periodic dispersoïd composite presenting the thinnest W layer thickness, i. e. W/Cu 1.5/0.2. As shown in figure 3, the experimental strain obtained deviated from that calculated using bulk elastic constants (continuous line). Instead, the bulk calculated response predicts well the experimental data obtained on a thick (200 nm) W layer.

We observe that the (ε, σ) slope value is much more important for the nanostructured layer than for 'bulk' materials. The elastic softening of W layers may be explained by a size effect. Indeed, the grain size being only about 1.5 nm, a large part of atoms is located close to a surface, an interface or a grain boundary. However, we have to keep in mind that the interface roughness or even mixing effect may also contribute to this variation.

CONCLUSIONS

Elastic strain measurements have been realized using a method combining X-ray diffraction and tensile testing. High accuracy X-ray strain measurements are essential for the determination of elastic constants since the strain range is limited (a few tenths of percent). Moreover, the diffracting volume in polycrystalline thin films can be very small and the photon energy has to be tunable to avoid peak overlapping for multiphase materials. For all these reasons, performing tensile tests with a high precision goniometer at a synchrotron beam line is essential. Preliminary results obtained monitoring W-{310} diffraction peak shift on W/Cu 1.5/0.2 sample clearly show a size effect on the mechanical response. Indeed, nanostructured tungsten layers elastic response strongly differs from the one expected for a bulk material. This might be attributed to an elastic constant softening for a 1.5 nm tungsten grain size. However, further analysis is needed to confirm such a tendency and particularly, the mechanical influence of copper inclusions. Indeed, composite systems containing two materials with different mechanical properties present a complex mechanical behavior since their elastic strain domains and ductility are different. So far, monitoring the strains in both elements during tensile tests is not possible in such samples. In order to understand in detail the causes of elastic constant softening, our team develops atomistic simulations. Simulated tensile testing of self-supported single-crystal film of W have revealed a Young's modulus softening coupled with a strengthening of the Poisson's ratio. This effect becomes larger when monocrystalline layer thickness decreases under 2 nm [START_REF] Villain | [END_REF]. These first results are qualitatively consistent with experimental measurements. However, in order to corroborate X-ray experiments, it is imperative to realize atomistic calculations on polycrystals. This is done using the Voronoi method for building polycrystals. It allows to realize bulk tungsten polycrystals with different grain size, preliminary step before modeling model polycrystalline thin films. The objective will be thus to study the elastic response of a layered polycrystalline W/Cu composite, by atomistic simulation. Eventually, it will provide a better understanding of the influence of discontinuous copper layers on the mechanical behavior.

Figure 1 :

 1 Figure 1: TEM Bright Field realized on W/Cu 10.8/0.2 showing the thin film stratification and suggesting copper layer discontinuities (confirmed by GISAXS).

Figure 2 :

 2 Figure 2: XRD Geometry: ψ is the angle between the surface normal of the sample and the measuring direction, i.e. the normal to the diffracting planes, and φ is the azimuth, i.e. the rotation angle around the normal to the sample surface.

  to the global force F along the tensile axis, and ref hkl d the value of this distance in the reference load state along the same direction defined by (ψ , φ ).

Figure 3 :

 3 Figure 3: Strain deduced from the shift of the W(310) diffraction peak measurements as a function of estimated applied stress increment (the first loaded state being chosen as the reference state) in W layers along the loading axis, for ψ = 63.4° and φ = 0°, for the thinnest W layer thickness. (λ XR = 0.127 nm). The dotted line represents the linear regression obtained from experimental data while the continuous line is calculated from equations (2) and (3) considering bulk elastic constants. The straight red line fits well the elastic strain measured on a 200-nmthick tungsten layer (performed with similar deposition conditions) following W(211) diffracting plane (ψ = 61.9° and φ = 0°).

Table I :

 I . Specifications of W/Cu samples submitted to in situ tensile tests at ESRF BM02 beamline. The uncertainties on thicknesses and stresses are about 5% and 10% respectively.

	Sample	Effective thicknesses	Number of (W,Cu)	Total film thicknesses	Residual stresses
	designation	Λ	t W	t Cu	layer pairs		Film	W layers
		(nm)	(nm)	(nm)		(nm)	(GPa)	(GPa)
	W/Cu 10.8/0.2	11.0 10.8	0.2	15	174	-2.8	-5.3
	W/Cu 2.8/0.2	3.0	2.8	0.2	60	198	-3.2	-5.8
	W/Cu 1.5/0.2	1.7	1.5	0.2	100	185	-3.2	-6.8

ACKNOWLEDGMENTS

The authors would like to thank P. Guérin for preparing the stratified thin films at PhyMat, D. Babonneau from PhyMat for GISAXS measurements at ESRF and N. Boudet and J.-F. Bérar for assistance during XRD experiments at BM02 ESRF beam line. This work has been granted by the French Agency for Research (ANR) through the Pnano project entitled Cmonano (ANR-05-PNANO-069).