Energy and Performance Trade-off in Nanophotonic Interconnects using Coding Techniques

Nanophotonic is an emerging technology considered as one of the key solutions for future generation on-chip interconnects. Indeed, this technology provides high bandwidth for data transfers and can be a very interesting alternative to bypass the bottleneck induced by classical NoC. However, their implementation in fully integrated 3D circuits remains uncertain due to the high power consumption of on-chip lasers. However, if a specific bit error rate is targeted, digital processing can be added in the electrical domain to reduce the laser power and keep the same communication reliability. This paper addresses this problem and proposes to transmit encoded data on the optical interconnect, which allows for a reduction of the laser power consumption, thus increasing nanophotonics interconnects energy efficiency. The results presented in this paper show that using simple Hamming coder and decoder permits to reduce the laser power by nearly 50% without loss in communication data rate and with a negligible hardware overhead.

I. INTRODUCTION

Technology scaling down to the ultra-deep submicron domain enables the integration of hundreds of cores in a single chip. To enhance connecting many cores, chip-level communication needs disruptive interconnects to bring down the power budget. On-chip nanophotonics interconnects are an emerging technology considered as one of the key solutions for future generations of many cores [START_REF] Sun | Single-chip microprocessor that communicates directly using light[END_REF], providing high bandwidth and low latency. Interconnect architectures, e.g. Multiple Writer Single Reader (MWSR) [START_REF] Vantrease | Corona: System implications of emerging nanophotonic technology[END_REF], are composed of laser sources, Micro-ring Resonators (MRs), waveguides and photodetectors. Active optical devices are power hungry compared to the traditional electrical functions. Considering this power consumption gap, new approaches to share the power consumption between the electrical and optical domains are needed in order to reduce the global power consumption.

This paper addresses this challenge and proposes to add data protection in the electrical domain, which allows reducing the power consumption of optical transmission without any reduction in the communication quality. For this purpose, Error Correction Code (ECC) are used on the transmitter side and faulty bits detected by the receiver are corrected. Since additional faulty bits are acceptable using ECC, the optical power emitted by the laser source can be significantly reduced. The laser being a major contribution of the power consumption, the global power of the optical interconnect can therefore be significantly reduced under specific scenarios without compromising energy per bit figures. The paper is organized as follows. Section II gives the start of the art. III details the approach for with a simple example and IV introduce the generic architecture and the models we use.

Power and performance trade-off are explored in Section V and Section VI concludes the paper.

II. RELATED WORK

ECC is a commonly used technique in wired and wireless communications [START_REF] Goldsmith | Design challenges for energy-constrained ad hoc wireless networks[END_REF], [START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF]. The association of power scaling of an emitter and the use of ECC allows to obtain an efficient energy per bit transmission given a targeted BER [START_REF] Alam | On the energy savings of adaptive transmit power for wireless sensor networks radio transceivers[END_REF], [START_REF] Mineo | A closed loop transmitting power self-calibration scheme for energy efficient winoc architectures[END_REF]. Indeed, ECCs allow to correct errors in data communications, hence it is possible to maintain a given BER while decreasing the Signal-to-Noise Ratio (SNR). Moreover, these approaches are scalable to the Network-on-Chip (NoC) communication medium. In [START_REF] Mineo | A closed loop transmitting power self-calibration scheme for energy efficient winoc architectures[END_REF] the authors proposed to use a closed-loop transmission to dynamically tune the transceiver power and the ECC correctness capacity. This allows to guarantee a target BER while tracking the communication channel variability.

Regarding Optical NoC (ONoC), the laser output power is reduced under BER constraints, which allows for the reduction of the laser power [START_REF] Wu | Variation-aware adaptive tuning for nanophotonic interconnects[END_REF]. This approach has been extended in [START_REF] Li | Towards maximum energy efficiency in nanophotonic interconnects with thermal-aware on-chip laser tuning[END_REF] by considering the laser thermal sensitivity and the crosstalk to evaluate the BER. However, the authors did not investigate the use of ECC for data transmission. In this paper, for the first time, we jointly use ECC and laser output power tuning technique in order to further improve the ONoC energy efficiency. The proposed approach is complementary to existing techniques allowing to dynamically turn off lasers when no activity is detected [START_REF] Demir | Towards energy-efficient photonic interconnects[END_REF].

III. ECC FOR POWER/PERFORMANCE TRADE-OFF

Figure 1 illustrates our approach in the context of a simple optical link with one laser source, one writer (source core) and one reader (destination core). We first detail the basic communication schemes without ECC. Then, we revisit the transmission schemes when ECC is used.

A. Communication Without ECC

To communicate, the source core i) sets the corresponding MR to the modulation state and ii) sends the data (d 0 , d 1 and d 2 in the figure). Data are serialized and the corresponding stream of information bits leads to an On-Off-Keying (OOK) modulation of the optical signal at the wavelength λ x , which is emitted by the laser. The modulation is realized by electrooptic effect on the MR. Forward biased is applied to perform voltage tuning, which leads to a blue shift of the MR resonant wavelength. In our model, data '1' and '0' lead to OFF state and ON state, respectively: • OFF state: the MR resonant wavelength is detuned from the optical signal and the optical continues propagating with low losses. • ON state: the MR resonant wavelength and the optical signal are aligned. Most of the optical signal power is absorbed by the MR, which leads to a strong attenuation on the output. The difference between OFF and ON attenuation defines the extinction ratio. As an example, a 9.2dB extinction ratio at 9Gb/s with 4.32mW and for a 2Vpp CMOS driver has been reported in [START_REF] Li | An energy-efficient silicon microring resonator-based photonic transmitter[END_REF]. In Figure 1, this is illustrated by the gap between the two optical signal power levels (mark 1 ). The modulated signal then propagates along the waveguide until the reader, where it is dropped to the photodetector (the optical signal is dropped by MR, by putting it in ON state). The photocurrent is then converted back to a digital data transmitted to the destination core. The transmission can be characterized as follows:

• Power: during the transmission, the modulated optical signals experience losses (not shown in the figure but discussed later on). The laser thus must emit a high enough optical power in order to reach the targeted BER (e.g. 10 -9 ), knowing the losses, the MR extinction ratio, and the photodetector dark current. The laser efficiency being relatively low (e.g. around 5%), its contribution in the optical link power budget is significant. • Performance: thanks to the direct modulation of the data (i.e. without ECC), the transmission time is reduced to the minimum if the target BER is reached. The following section discusses how the use of ECC impacts the optical communications.

B. Communication With ECC

When an ECC is used, the data to be emitted are first encoded (ed 0 , ed 1 and ed 2 in Figure 1, mark 2 ) before serialization and modulation. Due to the added bits to be transmitted, the communication time is longer (mark 3 ). In the receiver, the optical signals are converted back into electrical signals and the data are decoded. This allows detecting and correcting errors, which in turns improves the BER. Hence, assuming a same target BER as for the communication without ECC, the constraints on the SNR are leveraged when ECC is used. This leads to reducing the power of the optical signals, as suggested in the figure with the decreased amplitudes of the emitted signal (mark 4 ) and the modulated signal (mark 5 ); it is worth mentioning that the extinction ratio is the same). Hence, a global reduction of the optical link power is achievable if the energy saved on the laser side is larger than the energy spent in the data coding/decoding and in the transmission of the added bits.

C. Performance/Power Trade-offs

In short, not using ECC leads to fast but power hungry communications, while ECC increases the communication time but is potentially more power efficient. This complementary trend well suits execution constraints of nowadays applications running on complex 3D-Integrated Circuits. While execution deadlines have to be met for real-time applications, energy saving strategies can be applied for power hungry multimedialike applications (e.g. by degrading the BER).

This paper proposes to configure nanophotonics interconnects by jointly i) selecting the ECC used for data transmission and ii) tuning the laser output power. Hence, by considering i) application requirements and power budget and ii) ECC performance and power figures, a manager configures at runtime the optical link. The configuration is two-fold. First, the most appropriate communication scheme with or without ECC (w ECC or w/o ECC in the figure) is selected and both writer and receiver are configured accordingly. Second, the optical power of the signal emitted by the laser is set in order to respect the BER requirements. This is achieved by tuning the laser current in the laser output power controller. The use of a shared, or centralized, manager to configure one emitter and one receiver ONIs is a common solution in ONoCs [START_REF] Wu | Suor: Sectioned undirectional optical ring for chip multiprocessor[END_REF]. In these architectures, a source sends a request to the manager by specifying the destination and the communication requirements while the manager responds with the suitable configuration to apply on both source and destination sides.

Hence, adding the communication scheme (w or w/o ECC) within the requests has a limited impact on the manager cost (not detailed in this paper). The choice of the communication scheme is handled by the Operating System.

IV. ARCHITECTURE AND MODELS

This section presents the architectures we consider and the corresponding models.

A. 3D Integrated Circuits with Nanophotonic Interconnects

We assume a 3D-IC with an electrical layer and an optical layer implementing computing cores and the nanophotonic interconnect, respectively. Figure 2-a illustrates an example with four optical network interfaces (ONI) communicating using four MWSR channels (in this illustrative example, we assume a single waveguide per channel). There are thus three writers and one reader per channel: each writer is composed of N W modulators and the reader is composed of N W photodetector/passive MR couples.

B. MWSR Channel

Figure 2-b illustrates an MWSR channel in the tonics interconnect, which is obtained by extending the pointto-point link from Figure 1 with wavelengths and writers. For this purpose, we assume N W signal wavelengths, from λ 0 to λ N W -1 , emitted by lasers and combined using a multiplexer (MUX), which can be implemented using multimode interference (MMI) coupler [START_REF] Mandorlo | Controlled multi-wavelength emission in full cmos compatible micro-lasers for on chip interconnections[END_REF]. The un-modulated optical signals propagate on the waveguide until reaching the writer for which the channel access has been granted. The source core transmits the encoded data to the destination core using all the channel wavelengths. In our implementation, we assume an encoder/decoder pair for each wavelength, meaning that the (serial) stream of data sent by the source core is transmitted in parallel on the optical channel. Other implementations exist but are out of the scope of this paper.

As illustrated in Figure 2-c, each encoder allows transmitting data without ECC or with an ECC such as Hamming [START_REF] Wu | Variation-aware adaptive tuning for nanophotonic interconnects[END_REF][START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF] (noted as H [START_REF] Wu | Variation-aware adaptive tuning for nanophotonic interconnects[END_REF][START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF] in the rest of the paper). In this work, we chose Hamming for its simplicity, but other coding techniques can be used. The design of the interface is a challenging task due to the high operating frequency implied by the modulation speed. A complete description of such interface is given in Section IV-C.

The modulated signals propagate along the waveguide, cross intermediate writers and eventually reach the reader. The received data are decoded in parallel and the resulting decoded data are streamed to the destination core, as illustrated in Figure 2-d. It is worth mentioning that a high modulation speed, noted as F mod , leads to similar design complexity for encoder and decoder.

As previously explained, an optical link manager ensures that the same ECC is used on source and destination sides. It is also responsible for adapting the laser output power, which is achieved by using configurable CMOS current generator. In this work, we assume a single control signal for all the laser sources on a channel. The ECC and the laser output power are selected according to performances, power and BER requirements. The design of the manager and the implementation of the algorithms are out of the scope of this paper.

C. Electrical/Optical Interfaces

The design of interface is a challenging task due to the different signal frequencies between electrical and optical domains [START_REF] Wang | A holistic modeling and analysis of optical-electrical interfaces for inter/intra-chip interconnects[END_REF] [START_REF] Ortin-Obon | Capturing the sensitivity of optical network quality metrics to its network interface parameters[END_REF]. For example, a modulation frequency F mod set to 10GHz provides a throughput of 10Gbit/s on 1-bit serial data transmission. This is a typical bandwidth in the optical domain while, in the electrical domain, IPs would rather communicate at a much lower frequency, noted F IP , e.g. 1GHz, but with parallel data bus of N data width, such 64-bits.

Figures 2.c and 2.d illustrate the generic micro-architectures of the interfaces. The energy/performance manager (see Section III-C) selects the coding technique according to the communication requirements (e.g. task priority, BER). In addition to the mode with direct modulation (uncoded transmission), different coded modes (Hamming encoders with paths 0, to n -1 in the figure) can be selected. The encoded data are outputted to a mux connected to a serializer in order to generate the stream of data at the required F mod speed. The clock of the serializer register equals the modulation speed . The serializer is a well-known architecture based on a registers pipeline with a depth equal to the input size. These registers can be loaded with the input data by the use of a two-bits mux located in each register input's. Regarding the deserializer, its architecture is also based on a registers pipeline with a depth equal to the output size. These straightforward solutions allow to achieve a high throughput required by the optical modulation speeds while limiting the area (see Section V-A for synthesis results).

The receiver part, illustrated in Figure 2.d, is based on a similar micro-architecture than the emitter. It relies on decoders and on the use of a trans-impedance amplifier associated to a comparator. Obviously, the receiver path must be configured similarly to the emitter, i.e. by using a Hamming decoder with a size similar to the coder. This paper does not investigate data flow control and multi-wavelenghts allocation, which have already been efficiently addressed in [START_REF] Wang | A holistic modeling and analysis of optical-electrical interfaces for inter/intra-chip interconnects[END_REF] and [START_REF] Ortin-Obon | Capturing the sensitivity of optical network quality metrics to its network interface parameters[END_REF], respectively.

D. BER and Performance Models

Without coding, the SNR can be calculated from BER with

SN R = [erfc -1 (1 -2.BER)] 2 (1)
where erfc -1 is the inverse of the complementary error function. A minimum distance Hamming linear code is defined by an integer m ≥ 2, a block length of n = 2 m -1 and message length k = n -m. Hence the code rate of Hamming codes is R c = k/n, which is the highest possible for codes with minimum distance of three and block length n. The BER of a Hamming code is defined by

BER = p -p(1 -p) n-1 (2)
√ SN R) (3)
The energy per bit is linked to the SNR with the code rate R c . Calculating the SNR from BER when considering Hamming codes requires to invert Equations 3 and 2. The optical signal power to be received by the photodetector (OP signal ) is defined with

SN R = × (OP signal -OP crosstalk ) i n (4)
where OP crosstalk is the worst case crosstalk in the MWSR channel, is the photodetector responsitivity (1 A/W in this work) and i n is the dark current (4µA). Finally, the minimum laser output power OP laser is estimated using the transmission model proposed in [START_REF] Li | Towards maximum energy efficiency in nanophotonic interconnects with thermal-aware on-chip laser tuning[END_REF]. In this model, the authors evaluate the total signal transmission in a MWSR channel by taking into account the transmission in each MR (i.e. MR in writers and reader) and the waveguide loss. We have chosen this model for its accurate estimation of the crosstalk, which is obtained by taking into account the distance between signal and MR resonant wavelengths. Figure 3 illustrates the MR signals transmission in ON and OFF states. In the figure, λ M R is the MR resonant wavelength in the OFF state and ∆ λ is the wavelength shift between ON and OFF states. The Extinction Ratio (ER) is the transmission ratio between ON and OFF states for signal at λ M R . Other key characteristics of the modulators, not illustrated in the figure, are the modulation speed and the power consumption P M R . In this work, these values are extracted from [START_REF] Rakowski | Low-power, low-penalty, flip-chip integrated, 10gb/s ring-based 1v cmos photonics transmitter[END_REF], which leads to ER = 6.9dB and P M R = 1.36mW The performance is given by the Communication Time (CT), which corresponds to the relative increase of the transmission time due to parity bits. It is thus normalized to a transmission time without ECC. For instance, when using H(7,4), 75% parity bits are added to the payload which leads to CT = 1.75.

E. Power Models

P channel is the channel power consumption per wavelength and is given by: P channel = P EN C+DEC + P M R + P laser with P EN C+DEC the encoder and decoder power, P laser the laser power and P M R the modulation power (all the power values are given per wavelength). P EN C+DEC is obtained from synthesis results and is reported in the results section. P laser is obtained from the required on-chip laser output power and the laser efficiency. We consider the CMOS compatible PCM-VCSELs laser sources described in [START_REF] Sciancalepore | Thermal, modal, and polarization features of double photonic crystal vertical-cavity surface-emitting lasers[END_REF] and we assume a temperature dependent lasing efficiency. In this paper, we do not take into account the thermal tuning power, which we assume to be the same for communications with and without ECC.

V. RESULTS

A. Synthesis Results

Emitter and receiver interfaces with three possible communication modes (H [START_REF] Wu | Variation-aware adaptive tuning for nanophotonic interconnects[END_REF][START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF], H(71,64), and uncoded) have been synthesized on 28nm FDSOI technology. The interfaces have been designed for a 64-bit bus width IP (i.e. N data = 64) clocked at F IP = 1GHz and allowing to reach F mod of 10Gbit/s. The synthesis results are summarized in Table I. To encode the 64-bits of the IP bus, the interface requires 16 parallel H(7,4) coders and decoders, while only one H(71,64) codec is required. The Hamming blocks are clocked at F IP and compute the result in one clock cycle (outputs are clocked with registers). The SER and DES are working at F mod . The critical path results show positive slacks, compared to the aimed frequencies, allowing transmissions at 10 Gbit/s.

The area is 2013µm 2 and 3050µm 2 for the emitter and the receiver, respectively. Static power is negligible thanks to the 28nm low leakage technology. Consumed dynamic power depends on the selected data-path and hence on the active coding blocks. Indeed, the used path is activated by an enable signal. The dynamic power of the transmitter ranges from 3.1µW for an uncoded transmission to 9.5µW for a transmission with H [START_REF] Wu | Variation-aware adaptive tuning for nanophotonic interconnects[END_REF][START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF]. For the receiver interface, it ranges from 4.2µW for an uncoded transmission to 10.1µW for a transmission with H [START_REF] Wu | Variation-aware adaptive tuning for nanophotonic interconnects[END_REF][START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF]. H [START_REF] Wu | Variation-aware adaptive tuning for nanophotonic interconnects[END_REF][START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF] corresponds to the solution with the highest dynamic power consumption in the interfaces due to the highest overhead of Hamming bits. However, as this coder reaches the highest error correcting efficiency, it also allows for the highest reduction of the laser power.

In the following, we will compare the power consumption of the interface, the modulators and the laser sources. Then, we will investigate whether the improved communication quality made possible using encoded communication reduces the Laser power consumption significantly enough to overcome the increased modulation power consumption.

B. BER and Laser Power Trade-Offs

For on-chip light sources, we assume an integrated CMOS-compatible vertical-cavity surface-emitting lasers (VC-SEL) [START_REF] Sciancalepore | Thermal, modal, and polarization features of double photonic crystal vertical-cavity surface-emitting lasers[END_REF]. The temperature of the VCSEL depends on the optical power to be emitted (OP laser ) and ii) the activity of the electrical layer. Following the methodology detailed in [START_REF] Li | Towards maximum energy efficiency in nanophotonic interconnects with thermal-aware on-chip laser tuning[END_REF], the laser power consumption P laser is estimated assuming 25% chip activity. As illustrated in Figure 4, P laser linearly increases within the 0 -500µW optical power range but follows an exponential trend for larger values. This trend is due to the efficiency of the laser which drastically drops with high temperature.

Using the model described in Section IV-D, we evaluate the optical power signal needed to reach the targeted BER according to a given coding technique. For this purpose, we assume an MWSR architecture with 12 ONIs, 16 wavelengths, 6 cm waveguide length, 0.274dB/cm waveguide loss [START_REF] Dong | Low loss silicon waveguides for application of optical interconnects[END_REF] and ER = 6.9dB [START_REF] Rakowski | Low-power, low-penalty, flip-chip integrated, 10gb/s ring-based 1v cmos photonics transmitter[END_REF]. We assume transmissions with H(7,4), H(71,64) and without ECC, and targeted BER values range from 10 -3 to 10 -12 , Figure 5. As expected, the transmission without codes leads to the higher laser power consumption. For instance, each laser source consumes 14.3mW for BER = 10 -11 . In case H(71,64) is used, P laser drops to 7.12mW and it further decreases to 6.64mW for H [START_REF] Wu | Variation-aware adaptive tuning for nanophotonic interconnects[END_REF][START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF]. This significant reduction in the laser power is due to the added redundancy bits, which improve the optical channel robustness. Since additional errors in the transmission are acceptable, the optical power emitted by the light sources can be reduced. Interestingly, while targeting a 10 12 BER without ECC is not possible since it exceeds the maximum optical power deliverable by the laser (i.e. 700µW), reaching this BER is possible using H(71,64) and H(7,4) (P laser = 7.1mW and 7.6mW respectively). In the following, we will investigate the energy/bit figures and the communication time overheads due to the transmission of the redundancy bits . C. Performance and Power Trade-off Figure 6.a summarizes the channel power consumption per wavelength for BER = 10 -11 . For communication without ECC, the laser sources cost for 92% of the total power. Hence, the laser power reductions achieved using H(71,64) and H(7,4) lead to significant improvement of the total power (-45% and -49% respectively). Regarding the energy-perbit figures, since H(7,4) is the less energy efficient solution due to the large number of redundancy bits to transmit. In this study, H(71,64) is the most energy efficient solution with 3.76pJ/bit wrt. 3.92pJ/bit for a communication w/o ECC (i.e. 4% improvement). Furthermore, H(71,64) also demonstrates the lower power consumption thanks to the nearly 50% reduction: for the 16-wavelengths channel we consider, the power consumption drops from 251mW to 136mw for each waveguide. Assuming 16 waveguides per MWSR channel and 12 ONIs, the total power saving reaches 22W for the whole interconnect. To summarize, our method allows significant reduction in the power while maintaining the energy/bit figures: this contributes to solve the power wall and temperature (hot spot) issues in nanophotonic interconnects. It is worth mentioning that additional power saving can be achieved by turning off the lasers when no activity is detected [START_REF] Demir | Towards energy-efficient photonic interconnects[END_REF]. Reducing the power also comes at a price of larger communication time since the size of the data stream proportionally increases with the added redundancy bits. Figure 6.b illustrates the power/performance trade-off for BER ranging from 10 -6 to 10 -12 . For a given BER, all the coding techniques belong to the Pareto front, thus demonstrating the potential of the proposed approaches to overcome performance and power issues in nanophotonic interconnects.

VI. CONCLUSION

In this paper, we investigated the use of Error Correcting Code (ECC) to reduce the laser output power according to the communication quality requirement. We have shown that using ECC not only allows reducing the laser power consumption, but also allows to target BER not reachable without coding techniques and without compromising energy per bit. Since lasers significantly contribute to the optical channel power, global power reduction of the optical interconnect is also possible under specific scenario. This trend has been observed especially for H(71,64) ECC. In our future work, we will further investigate the achievable energy efficiency improvement by simulating the execution of standard benchmark applications on nanophotonic interconnects.

Fig. 1 .

 1 Fig. 1. General principle of the use of ECC in an ONoC

Fig. 2 .

 2 Fig. 2. ECC configuration and laser power management: detailed principle where p = 1 2 erfc(

Fig. 3 .

 3 Fig. 3. Optical signal transmission in MR

Fig. 4 .

 4 Fig.[START_REF] Chouhan | System-level design space exploration methodology for energy-efficient sensor node configurations: An experimental validation[END_REF]. P laser is estimated from the output optical power OP laser , the chip activity and the temperature-dependant laser efficiency.

Fig. 5 .

 5 Fig.5. P laser for a given MWSR channels is calculated from the targeted BER and the selected ECC code.

Fig. 6 .

 6 Fig. 6. a. (left) Power contribution in an MWSR channel for BER = 10 -11 . b. (right) Power and performance trade-off wrt. BER and ECC.

TABLE I SYNTHESIS

 I RESULTS OF AN INTERFACES PROVIDING NO ECC, H(7,4) AND H(71,64). F IP = 1GHz, N data = 64bits, ANDF mod = 10Gbit/s, TECHNOLOGY IS 28nm FDSOI.

					Total	Critical			Power
	Hardware block			Area	Path	Static	Dynamic	Total
					(µm 2 )	(ps)	(nW )	(µW )	(µW )
	Transmitter
	1-bit MUX (3 to 1)		14	80	0.2		0.23	0.23
	H(7,4) coders 1			551	210	1.7		3.13	3.13
	H(71,64) coder			490	350	1.6		2.51	2.52
	112-bits SER, H(7,4)		433	70	6.5		6.21	6.22
	71-bits SER, H(71,64)		276	70	4.1		3.24	3.25
	64-bits SER, wo ECC		249	70	3.6		2.93	2.93
	Total, H(7,4) com.						9.57	9.59
	Total, H(71,64) com.		2013		17.7	5.99	6.01
	Total, w/o ECC com.						3.16	3.18
	Receiver
	64-bits MUX (3 to 1)		815	80	10.8	1.55	1.56
	H(7,4) decoders			783	300	2.5		3.80	3.80
	H(71,64) decoder		648	570	2.2		2.63	2.64
	112-bits DESER, H(7,4)		365	60	5.5		4.75	4.75
	71-bits DESER, H(71,64)	231	60	3.5		3.02	3.02
	64-bits DESER, wo ECC	208	60	3.0		2.75	2.75
	Total, H(7,4) com.						10.1	10.1
	Total, H(71,64) com.		3050		27.5	7.21	7.23
	Total, w/o ECC com.						4.29	4.32
		14
		12
	Laser [mW]	6 8 10	Laser Power for 25% Activity
	P	4
		2
		0 0	100	200	300	400	500	600	700	800
						OP Laser [µW]


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. We study this problem denoted by MAXIM. We first present different characterizations of the graphs for which the optimal objective value of MAXIM is zero. Next we show that it is generally NP-complete 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. Finally we describe a polynomial-time approximation algorithm whose ratio is almost equal to 1 2 .

Introduction and notation

Let G = (V, E) be an undirected simple graph, 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. 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 and thus 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 criterion 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 thus 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 were 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) which orientation can be completed in a 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 first section, we give several characterizations of the the graphs verifying MAXIM(G) = 0. In section 2, we will 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 will give an approximation algorithm whose ratio is almost equal to 1 2 . Since the value of MAXIM for a graph is the minimum of the values of MAXIM on its connected component, from here on in, all the graphs we consider are assumed to be connected. For any graph G we will use the notations V (G) and E(G) to refer to the set of vertices of G and the set of edges of G respectively.

1 Characterizing the graphs for which MAXIM(G) = 0 Now we ask ourselves which are the graphs verifying MAXIM(G) = 0. We will 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 prove 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. Being G 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.

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

C odd if there exists C 1 , • • • ,C n odd cycles (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)
Then for any simple graph G, MAXIM(G) = 0 if and only if G ∈ C odd .

Proof. • ⇐ We will work by induction on the number of cycles n 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 Λ |E(G ) the orientation of the edges of G obtained from Λ as its restriction on 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 + Λ |E(G ) (u) -d - Λ |E(G ) (u)| = 0. Necessarily, u = V (G ) ∩V (C n ). Thus |d + Λ (u) - d - Λ (u)| = |d + Λ |E(Cn) (u) -d - Λ |E(Cn) (u)| > 0 implying that MAXIM(C n ) > 0 which is absurd because C n is an odd cycle. • ⇒ Since MAXIM(G) = 0,
we know that G is eulerian. We will again work by induction on the number of 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 an 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 Figure 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 contraditcts

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 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 directly 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.

Theorem 4 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.

+ Λ (u 0 ) -d - Λ (u 0 )| ≥ |d + Λ (u 0 ) -d - Λ (u 0 )| > 0 . G u v u 1 u k-1 C
• ⇐ 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 travelling 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. 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 .

Complexity, inapproximability and approximability

In this section we will 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 will show that the problem is NPcomplete. More precisely, that answering if MAXIM(G) equals 2 for a graph G such that δ G = 2 is NP-complete. For that purpose we will introduce a variant of the satisfiability problem that we will 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 5

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

Proof. See Appendix A. Now we will 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 they represent, 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)
Fig. 3:

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
the corresponding graph G ϕ is represented in Figure 3.

Theorem 6 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 ϕ )
which 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.
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 4(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. Figure4(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 Fig. 4:

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 is the one with the incoming arc from a variable gadget (meanings 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

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)
|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 which was 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 (meanings 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. Figure 4(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 ϕ doesn't 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 have 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 which was 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 7 MAXIM is NP-complete and inapproximable within 1 2 + ε where ε ∈ R * + , unless P = NP.

Proof. Let ε ∈ R * + , suppose that there existed 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 is absurd unless P = NP.

Now we consider the case of bipartite graphs: if G = (V 1 V 2 , E) is a bipartite graph, the orientation that consists in assigning to each edge in E the orientation from its extremity in V 1 to its extremity in V 2 has an imbalance equal to δ G , i.e. optimal. This simple case permits us to obtain the following lower bound: Theorem 8 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 ⊂ E such that we have |δ ({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. |δ ({v}) ∩ C| < d(v) 2 from V 1 to V 2 (or the contrary). Moreover, if we iterated this process starting from a random cut, we would converge in polynomial time time to a 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 isn't 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 [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]. This leads to an approximation algorithm whose ratio is 1 2 (resp.

Further research

While computing the most imbalanced orientation of a graph is generally difficult, the problem turns out to be easy for cactus graphs. It may be the same for other graph classes, characterizing such graph classes would be interesting. We are currently looking for efficient mathematical programming formulations to solve the problem for large size graphs. Details will follow in the extended version of the paper. One can also study the weighted version of the problem.

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 .

  orientation of the edges in the clause gadgets a variable gadget and the other has one outgoing arc to a variable gadget. If a j l 1

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

	1 2 -1 δ	1 2 -1 2δ ,

Appendix A Proof of Lemma 5 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.

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 1 1 , x 2 1 , x 3 1 , x 4 1 , x 5 1 , x 1 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

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.