Imen Saïd
email: imensaid@gmx.fr

Christian Malosse

Virginie Durier

Colette Rivault

I Said

M Christian

D Virginie

R Colette

INTRASPECIFIC SIGNALS INDUCING AGGREGATION IN PERIPLANETA AMERICANA (L.) (INSECTA: DICTYOPTERA)

Keywords: Periplaneta americana, aggregation, cuticular hydrocarbons, volatile fatty acids, behavioural tests

Chemical communication is necessary to induce aggregation and to maintain the cohesion of aggregates in Periplaneta americana (L.) cockroaches. We aimed to identify the chemical message inducing aggregation in this species. Two types of bioassays were used, binary choice tests in Petri dishes and tests in Y-olfactometer. Papers conditioned by direct contact of conspecifics induce aggregation when proposed in binary choice tests and were attractive in a Y-olfactometer. The identification of the molecules present on these conditioned papers indicated that dichloromethane extracts contained mainly cuticular hydrocarbons whereas methanol extracts contained more volatile molecules. Only a mixture of extracts in both solvents induced aggregation. High concentrations of cuticular hydrocarbons are necessary to induce aggregation when presented alone. When presented with volatile molecules present in methanol extracts, low concentrations of cuticular hydrocarbons are sufficient to induce aggregation if they are presented in contact. Among volatile molecules collected on filter paper, a mixture of three compounds: hexadecanoic acid, pentadecanoic acid and pentaethylene glycol induced aggregation. Our results provide evidence that aggregation processes in P. americana relies on a dual mechanism: attraction over long distances by three volatile molecules and maintenance on site by contact with cuticular hydrocarbons.

Introduction

Animal aggregation is a general phenomenon that can be seen as a collection of units arranged in space to form a coherent whole [START_REF] Parrish | Animal groups in three dimensions[END_REF]Hamner 1997, Krause and[START_REF] Krause | Living in groups[END_REF]. Among the many definitions given to the word aggregation, two main types of grouping can be distinguished: -active aggregation when animals are recruited to a particular location by an environmental attractive source (food, shelter…) although they do not interact with one another, and -congregation when the attractive source is the group itself [START_REF] Parrish | Animal groups in three dimensions[END_REF]. Individuals of many species present alternate phases of dispersion and aggregation depending on their current behaviour. After a dispersion phase they are able to form cohesive groups that rely not only on their individual abilities to find the best suitable environmental conditions but also on their abilities to recognize group members and to distinguish them from individuals of other groups of the same species or individuals of another species that they avoid when necessary. Usually aggregates are formed in places presenting particular microclimatic conditions that fulfil the ecological requirements of the species. For example, choice of rest sites can be oriented by microclimatic factors such as temperature, humidity, darkness, size, nature of substrate, etc. Disruption of favourable climatic conditions induces the departure of the animals. Climatic conditions are not the only factors that force animals to form congregations together, social cues orient them towards one another and consequently they gather on a common site. When a group is maintained by mutual attraction of group members [START_REF] Grassé | Le fait social: ses critères biologiques, ses limites[END_REF], it necessitates active information transfer among individuals.

In insects, information is often conveyed by chemical messages or pheromones. Pheromones are molecules secreted to the outside by some individuals and perceived and analysed by conspecifics to orient their behaviour [START_REF] Wyatt | Pheromones and animal behaviour: Communication by smell and taste[END_REF]. They can be classified in six functional groups: sex, aggregation, dispersal, alarm, recruitment and maturation. The pheromone message informs conspecifics about the presence of a resource or about their ability to mate.

In insects, group formation is often sustained by release of an aggregation pheromone, which induces a behavioural response by conspecifics leading to congregation, i.e. leading to an increase of the density of individuals in the vicinity of the emitting individuals [START_REF] Ali | Chemical communication in insect communities: a guide to insect pheromones with special emphasis on social insects[END_REF]. Contrary to sex pheromones, aggregation pheromones attract conspecifics of either sexes or the same sex as the emitter [START_REF] Wertheim | Pheromone-mediated aggregation in nonsocial arthropods: an evolutionary ecological perspective[END_REF]). Aggregation pheromones have been defined as having an arrestant effect that slows the linear progression by reducing the speed of locomotion or by increasing turning rates and thus inducing the maintenance of individuals on a selected area [START_REF] Ali | Chemical communication in insect communities: a guide to insect pheromones with special emphasis on social insects[END_REF]. This definition restricts the pheromone action to a local area when individuals are passing by. To increase encounter probability, attraction from a distance is necessary to improve the effective radius of the aggregation pheromone where, for example, bark beetle larvae follow a pheromone gradient to locate the pheromone source or the emitting conspecifics [START_REF] Deneubourg | Kinetics of larval gregarious behavior in the bark beetle Dentroctonus micans (Coleoptera: Scolytidae)[END_REF]). Aggregation processes first necessitate oriented movements towards an attractive source and then individuals are maintained in the selected area by increase in the frequency of contacts among individuals, which permit close range chemical interactions [START_REF] Applebaum | Density-dependent physiological phase in insects[END_REF] where they can benefit from aggregation to feed on their host plant and to overcome their host's resistance [START_REF] Borden | Aggregation pheromones in the Scolytidae[END_REF][START_REF] Byers | Chemical ecology of bark beetles[END_REF].

Many cockroach species are known to be gregarious [START_REF] Cornwell | A Laboratory Insect and an Industrial Pest[END_REF]) although the mechanisms of group formation are not clearly established. Adult males and females and nymphs of all developmental stages gather together in common shelters during their diurnal resting phase [START_REF] Roth | The biotic associations of cockroaches[END_REF][START_REF] Cornwell | A Laboratory Insect and an Industrial Pest[END_REF][START_REF] Bell | The American Cockroach[END_REF]. During the nocturnal phase, each individual forages in the areas surrounding the shelters where they are able to return using navigation cues and chemical communication [START_REF] Rivault | Homing in German cockroaches, Blattella germanica (L.) (Insecta:Dictyoptera): Multi-channnelled orientation cues[END_REF].

Aggregates are maintained by mutual attraction among members due to chemical communication (Rivault andCloarec 1998, Rivault et al. 2002). Aggregation pheromones are clearly identified in only a few cockroach species. In Blaberus craniifer (B.), the pheromone produced by the mandibular glands, is a mixture of undecane and tetradecane [START_REF] Brossut | Le grégarisme chez Blaberus craniifer: isolement et identification de la phéromone[END_REF]. In Blaberus distanti (K.), it is a mixture of undecane, 4-heptanone, 2,6-dimethyl-4heptanone and octanol [START_REF] Brossut | Gregarism in cockroaches and in Eublaberus in particular[END_REF]. In Blattella germanica (L.), the identification of the active molecules remains unclear although data indicate that molecules secreted from the rectal pad cells into the rectum and then excreted with the faeces are able to induce aggregation [START_REF] Ishii | An aggregation pheromone of the german cockroach Blattella germanica (Orthoptera: Blattellidae).1-Site of the pheromone production[END_REF], other chemical components also induce attraction such as lactic acid [START_REF] Mcfarlane | Aggregation of larvae of Blattella germanica by lacticacid present in excreta[END_REF], free fatty acids [START_REF] Ritter | Recent development in insect pheromone research in particular in the Netherlands[END_REF] alkylamines and blattellastanoside A and B [START_REF] Sakuma | The aggregation pheromone of the German cockroach, Blattella germanica (L.) (Dictyoptera: Blattellidae): Isolation and identification of the attractant components of the pheromone[END_REF][START_REF] Sakuma | Aggregation arrestant pheromone of the german cockroach Blattella germanica (L.) (Dictyoptera: Blattellidae): isolation and structure elucidation of blattellastanoside-A and-B[END_REF], or cuticular hydrocarbons [START_REF] Rivault | Cockroach aggregation: discrimination between strain odours in Blattella germanica[END_REF]).

Among urban cockroach species, Periplaneta americana (L.) is gregarious and chemical communication is clearly involved in aggregation processes. Papers conditioned by conspecific odours are chosen as resting sites [START_REF] Leoncini | Could species segregation be a consequence of aggregation processes? Example of Periplaneta americana (L.) and P. fuliginosa (Serville)[END_REF]. Cuticular hydrocarbons play an important part in this message that enables aggregation on the odour source through tactile and/or volatile pathways (Saïd et al. 2005a). Nevertheless, the concentration of cuticular hydrocarbons necessary to induce aggregation on a conditioned site must be very high, far beyond biological levels (Saïd et al. 2005a). Therefore, we assumed that cuticular hydrocarbons do not carry the entire aggregation message and that other molecules must be involved. We hypothesized that a volatile part of the message should attract cockroaches over longer distances than cuticular hydrocarbons. After attraction to a specific locality, the increase in frequency of contact among individuals permits close-range chemical interactions via cuticular hydrocarbons. Cuticular hydrocarbons could then act as an arrestant signal capable of maintaining cockroaches around the signal source.

Our aim was to identify emitted volatile secretions of P. americana and to evaluate their attractive effects and to investigate their action in aggregation processes in relation to the presence of cuticular hydrocarbons.

Material and methods

Insect breeding

P. americana (Insecta: Dictyoptera) were reared in stock colonies at 27°C under a 12 h dark-12 h light photocycle. Commercial dog pellets and water were provided ad libitum.

Two types of behavioural bioassays evaluated the efficiency of the chemical stimuli to attract conspecific cockroaches and to induce aggregation: binary choice tests in Petri dishes and tests in a Y-olfactometer.

Binary Choice Tests

Tests were made in round plastic Petri dishes (diameter: 140 mm, height 15 mm). Tests were put in place during the light phase of a diurnal cycle, during the cockroach resting phase.

Groups of 10 first instar nymphs were presented a choice between two filter papers used as resting sites. Papers folded in 'W' and placed upright in the dish, measured 9 cm² (1.5 x 6 cm).

During tests nymphs were deprived of water and food. Each larva was used only once to avoid bias in results.

One of the filter papers was a control paper and the other one was conditioned with different odours as detailed below.

Data were collected 24 h later when nymphs had spent an entire circadian cycle in the test dishes and had had the opportunity to choose their rest site. Numbers of individuals on each filter paper were then counted.

Papers were conditioned either by live insects or by extracts in different solvents of these conditioned papers. For all the tests involving solvent extracts, papers were prepared 15 hours prior to the test to let the solvent evaporate completely.

1-Control tests

Cockroaches were given the choice between two clean filter papers to verify the symmetry of the experimental set up and the use of filter papers as resting sites by the nymphs.

2-Conspecific contact conditioned papers (CC papers)

Papers were conditioned by placing them in a dish with normally fed and watered nymphs during the first three days of the first instar with a ratio of 20 nymphs per paper.

During this time, nymphs rested on these papers and thus the papers were conditioned by general body contact.

Nymphs were given a choice between a CC paper and a control clean filter paper.

3-CC paper extracts

CC papers were extracted in two solvents, dichloromethane (SDS, France, purity: 99.95%) for apolar compounds, and methanol (SDS, France, purity: 99.95%) for more polar compounds. Papers were immersed first in dichloromethane for 2 min, and then in methanol for 2 min. Extracts were concentrated under nitrogen flow. The solvent was evaporated so that 10 μl of the extract corresponded to one filter paper. Extracts were preserved at -18°C.

Dichloromethane and methanol extracts of CC papers were tested separately or in mixture. When only one extract was tested, 10 μl of that extract were deposited on one paper.

Control papers were obtained by depositing 10 μl of the corresponding solvent on a paper.

When both extracts were presented together, 10 µl of each extract were deposited on the same filter paper and 10 µ of each solvent on the control paper.

Nymphs were given a choice between: -a CC paper extract in dichloromethane and a solvent control; -a CC paper extract in methanol and a solvent control; -a mixture of both types of extracts and a control solvent.

4-Conspecific volatile conditioned papers (VC papers)

Odours emitted by nymphs were trapped with filter paper in an airtight glass vial. Ten last instar nymphs were placed in a tight glass vial connected to a glass cartridge containing adsorbent substrate. Nymphs were replaced every three hours for two successive 12-h photophases. The vial with nymphs was ventilated by a charcoal purified humidified air flow (pump New air, France) carrying odours to the glass cartridge containing filter papers, which are an effective adsorbent of P. americana volatiles [START_REF] Tirard | Are polyamines involved in olfaction? An EAG and Biochemical study in Periplaneta americana antennae[END_REF].

Nymphs were given a choice between a VC paper and a control clean filter paper.

-VC paper extracts

The extraction process used for VC papers was the same as for CC papers. VC papers were extracted only in methanol. Methanol extracts were preferred because methanol gave a better extraction of the more volatile part of the profile present on the CC papers. Ten μl of the extract corresponded to one filter paper. Ten μl of the methanol extracts were deposited on one paper. The control paper was obtained by depositing 10 μl of methanol on one paper.

Nymphs were given a choice between a paper with VC paper extracts and a solvent control.

6-Synthetic Fatty acids

Methanol solutions of seven synthetic chemical compounds (Sigma Aldrich, Germany) identified in the VC paper extracts were prepared at 10 µg/µl, then serially diluted: dodecanoic acid (purity: 99%), tetradecanoic acid (purity: 95%), pentadecanoic acid (purity: 99%), hexadecanoic acid (purity: 99%), hexadecenoic acid (purity: 99%), octadecanoic acid (purity: 99%) and penthaethylene glycol (purity: 98%). Ten µl of a 100 ng/µl solution of one chemical compound was deposed on a filter paper (total dose 1 µg).

Nymphs were given a choice between a paper conditioned with one of the compounds and a solvent control paper.

A mixture of two fatty acids (hexadecanoic acid and pentadecanoic acid) and penthaethylene glycol was prepared following their relative proportions in the VC paper methanol extracts: 70 µg hexadecanoic acid + 20 µg pentadecanoic acid + 10 µg penthaethylene glycol.

Nymphs were given a choice between a paper conditioned with this mixture and a solvent control.

Tests in a Y-Olfactometer

The role of volatile components in the aggregation behaviour of P. americana was tested in a Y-olfactometer. Males were tested individually in a glass Y-olfactometer (two 25 cm long arms and a 20 cm long common stem, the arms were 3 cm in diameter). The two arms were connected to the common stem with external Teflon-covered screws so that the connection could not be detected from inside. A pump (New air, France) drew air at a constant flow rate (150 ml/min) controlled by a flow-meter (Brooks, U.S.A.). The air was humidified and purified with active charcoal before reaching the olfactometer. Each arm was connected to one glass vial (50 or 250 ml), sealed with Teflon screws, containing the odour sources. The air flow through the left arm carried the stimulus and the air flow through the right arm carried the control odour. For each bioassay, males to be tested were isolated, 12 hours before a test, in small plastic boxes, thus avoiding CO2 anaesthesia just before a test. At the beginning of a test, one of these boxes was placed in front of the common stem of the olfactometer to let the tested male in without the experimenter having to manipulate it. The activity of each male was recorded for 5 min. The olfactometer was cleaned after each test.

1-Control tests. Males were given a choice between two odourless air flows to verify the experimental set up.

2-CC papers. These papers were prepared following the method described previously (papers were conditioned for three days with a ratio of 20 first instar nymphs per paper).

Males were given a choice between the odour emitted by six CC papers and clean air to test the attraction of volatile components in the odorized arm.

3-CC paper methanol extracts.

As methanol extracts carry more volatile components, males were given a choice between an air flow carrying the odour of 60 µl of CC paper methanol extracts deposited on a filter paper and an air-flow carrying the odour of 60 µl of methanol deposited on a filter paper.

4-CH extracts in Dichloromethane

CH extracts in dichloromethane were proposed to the tested males to test the effect of more heavy molecules contained in the CC paper blend. Extracts were obtained with previously frozen first instar nymphs that were immersed in dichloromethane for 2 min. After removing the cockroaches, extracts were evaporated under nitrogen flow until a volume corresponding to a concentration of 20 equivalent nymphs / 10 µl was reached. An equivalent larva is defined as the amount of CHs extracted from one larva [START_REF] Heifetz | Cuticular hydrocarbons control behavioural phase transition in Schistocerca gregaria larvea and elicit biochemical responses in antennae[END_REF]. This concentration was chosen because CC papers were conditioned by 20 first instar nymphs per paper. CH extracts were preferred to dichloromethane CC paper extracts to avoid pollution by molecules from faeces although these extracts contained mainly CHs.

Males were given the choice between an air flow carrying the odour of 60 µl of CH extracts deposited on a filter paper and an air-flow carrying the odour of 60 µl of dichloromethane deposited on a filter paper.

5-CC paper methanol extracts with CH extracts presented with contact possibility.

As CH extracts might be perceived mainly by contact instead of through the olfactory channel, they were presented on a disc of filter paper placed inside the far end of the arm odorized by CC paper methanol extracts. We hypothesized that the CC paper methanol extracts would attract the males into the odorized arm and the presence of the CH extracts would arrest them in that arm.

Males were given a choice between an air-flow carrying the odour of 60 µl of CC paper methanol extracts deposited on a filter paper and an air-flow carrying the odour of 60 µl of methanol deposited on a filter paper. The arm odorized by the CC paper methanol extracts contained a filter paper disc (diameter = 3 cm) conditioned with 30 µl of CH extracts (20 equivalent nymphs / 10 µl). This disc was placed at the far end inside this arm to allow direct contact by nymphs.

6-VC papers. VC papers containing volatile odours emitted by nymphs were prepared as described above. Males were given a choice between the odour emitted by six VC papers and clean air.

7-VC paper methanol extracts. VC paper methanol extracts were prepared as described above. Males were given a choice between an air-flow carrying the odour of 60 µl of this extract deposited on a filter paper and an air-flow carrying the odour of 60 µl of methanol deposited on a filter paper.

Chemical analyses

Gas chromatography (GC) analyses

CC and VC paper extracts were analysed by GC. The GC analyses were made with two different column-oven programs (Saïd et al. 2005a).

The first program was adapted to CHs. It started at 100°C, and then temperature was increased gradually up to 210°C at 20°C/min, and again up to 320°C at 4°C/min. The final temperature hold time was 15 min.

The second program was adapted to volatile molecules. It started at 35°C for 1 min, then temperature increased gradually up to 50°C at 20°C/min and stayed at 50°C for 5 min, then temperature increased to 250°C at 6°C/min and was maintained at 250°C for 4 min. Data were collected and treated with Galaxie software (Varian 2002).

Gas chromatography-Mass spectrometry (GC-MS) analyses

Identification of chemical compounds present in the tested extracts was made by GC-MS. These analyses were carried out using a Varian 3400 gas chromatograph coupled to a Saturn II mass spectrometer with a SPI injector programmed at 250°C. Two different columns were used. For CC paper extracts we used a VF5-MS (50 m long x 0.20 mm internal diameter x 0.33 µm thick film) and the carrier gas Helium at 20 psi. For VC paper extracts we used a VF35MS (30 m long x 0.32 mm internal diameter x 0.5 µm thick film) and the carrier gas at 10 psi. The two columns were heated following the same program: The initial temperature of the column was 50°C for 1 min, and then the temperature was increased gradually up to 300°C at 8°C /min. Interpretation on mass-spectrum GC-MS was conducted using the database of National Institute Standard and Technology (NIST). The spectrum of the unknown components was compared with the spectrum of known components stored in the NIST library.

Data analyses

The distribution of binary choice tests as a function of the proportions of aggregated nymphs on one of the resting papers was calculated according to the method described by [START_REF] Deneubourg | Selforganization mechanisms in ant societies (II): Learning in a foraging and division of labor[END_REF] X² tests were used to compare distributions of tests. Times spent in the odorized arm and control arm of the Y-olfactometer tests were analysed using Wilcoxon matched-pairs test (Statistica, 2004).

Results

Selection of one of the filter paper as resting site in binary choice tests in Petri dishes, results both from perception of volatile molecules and from contact with heavier molecules present in the deposited blend. In Y-olfactometer tests, times spent in each arm depended on the attractive effect of the volatile blend perceived by the subjects. Both types of test are complementary and reveal information about chemical blends able to attract and to maintain the insects in a given area.

Control tests

Nymphs aggregated on either of the filter papers in binary choice tests. The distribution of tests in relation to the number of nymphs on one of the resting sites formed a 'U' shape curve when nymphs were given a choice between two control papers. This distribution indicated that nymphs choose equally either of the control papers (X² = 0.028, p < 0.05) (Fig. 1). This confirms that P. americana is a gregarious species.

Adult males exhibited no stress in the Y-olfactometer. They walked normally in the common stem, made a choice and then entered one of the arms. They went in and out of the arms several times. Males spent 48 % of the test duration the common stem. Control tests, with two odourless air flows, revealed a small, but not significant, preference for the right arm (t-test, t = 1.27, P > 0.05) (Table 1). To avoid this bias and to be sure an odour was attractive, all odours to be tested were presented in the left arm.

CC papers

Binary choice tests

Nymphs aggregated on the CC papers in 74 % of the tests (Fig. 1). Nymphs aggregated preferentially on the conditioned site (X² = 34, P< 0.001).

Nymphs aggregated on the papers conditioned with CC paper dichloromethane extracts in 42 % of the tests (X² = 1.88, P > 0.05). Nymphs aggregated on the papers conditioned with CC paper methanol extracts in 44 % of the tests (X² = 2.31, P > 0.05). In neither of these two experiments, nymphs selected the conditioned site to aggregate.

When papers were conditioned with the mixture of both dichloromethane and methanol extracts, they induced aggregation in 58 % of the tests. Nymphs selected significantly the site conditioned with the mixture of the two extracts (X² = 9.25, P < 0.001).

GC-MS analyses

CHs accounted for 90.29 % of the total amount of CC paper dichloromethane extracts.

P. americana CHs have been identified previously (Saïd et al. 2005a). A few other molecules appeared in small peaks, each representing less than 1% of the total amount. As these molecules were present in higher quantities in the CC paper methanol extracts, they were identified in these extracts.

CC paper methanol extracts contained a larger number of molecules having different chemical functions. CHs present in the CC paper methanol extracts still represented 60% of the total amount. Most of the remaining compounds were fatty acids: 24% of the total amount. Hydrocarbons and ketones were also present, but in very small amounts (Fig. 2, Table. 1). As all these molecules have smaller molecular weights than CHs, they are more volatile.

Tests in a Y-olfactometer

Males spent significantly more time in the arm odorized with CC papers than the control arm (t-test, t = 4.35, P < 0.001) (Table . 2). They also spent significantly more time in the arm odorized with methanol CC paper extracts (t-test, t= 2.77, P < 0.01). Therefore, CC paper methanol extracts contained attractive volatile molecules that were present on the CC papers.

When the arm was odorized with CH extracts of 20 first instar nymphs, males did not spend significantly more time in the odorized arm (t-test, t = 0.43, P > 0.05).

Nevertheless, when a circular disc conditioned with the same concentration of CHs was added at the far end inside the arm odorized by CC paper methanol extracts, males spent significantly more time in the odorized arm than in the control arm (t-test, t = 3.54, P < 0.001).

Time spent in the arm odorized with CC paper methanol extracts increased significantly from 105 s to 145 s (Table 2) when CH extracts that could be touched were added (X 2 = 6.4, P < 0.05).

Both types of tests (binary choice tests with young nymphs and Y-olfactometer tests

with adult males) led to similar conclusions. Test results were enhanced when cockroaches could perceive volatiles emitted by conspecifics and could have contacts with conspecific CHs. In binary choice tests CC papers provide both volatiles that can be extracted in methanol and CHs that had been deposited. In the Y-olfactometer, cockroaches could perceive both volatiles from the CC papers carried by the air-flow and have contact with CH extracts placed in the arm.

The selection of the conditioned paper or the increase of the time spent in the conditioned arm, both indicated that nymphs were attracted from a distance and then maintained on site by contact with CHs. Therefore, to identify the active part of the complex volatile blend extracted from CC papers, volatile molecules were selectively collected and their efficiency was tested.

VC papers

Binary choice tests

Papers conditioned by volatiles emitted by nymphs (VC papers) induced aggregation in 97 % of the tests (Fig. 1). Nymphs selected significantly the conditioned site to aggregate (X² =34, P < 0.001).

Similarly, nymphs selected significantly the site conditioned with VC paper methanol extracts (53% of the tests) (X² = 5.76, P < 0.05).

Tests in a Y-olfactometer

Males spent significantly more time in the arm odorized with VC papers than in the control arm (t-test, t = 2.68, P <0.01) (Table 2).

They also spent significantly more time in the arm odorized with methanol VC paper extracts (t-test, t = 2.38, P <0.05). These extracts contained volatile molecules present in the VC papers.

GC-MS analysis

Nine molecules were identified in the VC paper methanol extracts. They included 3,5bis(1,1dimethyl ethyl) phenol, penta-ethylene glycol, five saturated fatty acids: dodecanoic acid, tetradecanoic acid, pentadecanoic acid, hexadecanoic acid, octadecanoic acid and two unsaturated fatty acids: hexadecenoic acid and octadecenoic acid (Fig. 3, Table 3). Hexadecanoic acid was the major compound in the natural blend.

Volatile synthetic chemical compounds

Six synthetic fatty acids and of pentaethylene glycol, identified in the VC paper extracts, were tested individually in binary choice tests.

When papers were conditioned with dodecanoic acid (X² = 0, P > 0.05) or octadecanoic acid (X² = 0.04, P > 0.05), nymphs did not select significantly the conditioned sites to aggregate. When papers were conditioned with tetradecanoic acid (X² = 0.33, P > 0.05) or hexadecenoic acid (X² = 2.27, P > 0.05), not only the conditioned sites were not selected, but aggregation levels were low (Fig. 4).

When papers were conditioned with hexadecanoic acid (X² = 0.8, P > 0.05) or penthaethylene glycol (X² = 2.57, P > 0.05), nymphs selected the conditioned site more often than the control papers although no significant differences between the two sites could be evidenced.

When papers were conditioned with pentadeanoic acid, nymphs selected preferentially the conditioned papers (X² = 7.14, P < 0.01). Pentadeanoic acid was the only fatty acid able to induce significant choice of the conditioned site (Fig. 4).

Papers conditioned with a mixture of the three more attractive molecules (hexadecanoic acid, pentadecanoic acid and pentaethylene glycol), induced aggregation in 60% of the tests.

Nymphs selected preferentially the conditioned site to aggregate (X² = 6, P < 0.05) (Fig. 4).

Discussion

To identify the molecules involved in aggregation processes in the cockroach P. americana, two types of bioassays (binary choice tests and Y-olfactometer) were used. Binary choice tests in Petri dishes have been used previously in our laboratory to test aggregation abilities in cockroaches (Rivault andCloarec 1998, Leoncini andRivault 2005). The choice of one of the sites to aggregate indicated that the molecular blend present on that site was able to induce the choice and to maintain the aggregation of the cockroaches. The stimulus can act through the olfactory pathway as well the tactile pathway. Tests in the Y-olfactometer gave slightly different results. The increase in time spent in one of the odorized arms indicated that the chemical blend was able to attract cockroaches from a distance and that it acted only through the olfactory pathway. Results of both types of bioassays are complementary and helped us to evidence and to compare the role of different types of molecular blends.

As our previous results [START_REF] Leoncini | Could species segregation be a consequence of aggregation processes? Example of Periplaneta americana (L.) and P. fuliginosa (Serville)[END_REF] [START_REF] Rivault | Cockroach aggregation: discrimination between strain odours in Blattella germanica[END_REF]. These conspecific contact conditioned papers contain a complex blend of molecules that included cuticular hydrocarbons, faeces, and emitted volatiles. When the blend was separated by extractions in different solvents (dichloromethane and methanol) into two parts, neither of the parts was able to induce aggregation. Neither dichloromethane extracts nor methanol extracts induced aggregation in binary choice tests. Only the mixture of both types of extracts induced aggregation. The efficiency of CC paper dichloromethane extracts that contained small amounts of CHs, increased when methanol extracts were added. This means that at least some of the molecules that are present in each type of extracts are required to induce aggregation and that they act simultaneously, in complement or in synergy. We know that, when presented alone, CHs can induce aggregation only at very high concentrations. The amounts of CHs necessary to induce aggregation in these experiments were far beyond a "natural stimulating" situation although some factors, like incomplete extraction or presence of solvent residues could reduce the efficiency of the tested blend (Saïd et al. 2005b). The presence of many molecules with molecular weights lower than those of the CHs in the methanol CC paper extracts led us to assume that molecules more volatile than CHs are involved in the aggregation processes.

Y-olfactometer tests confirmed this hypothesis. Males were attracted to arms odorized with CC papers or CC paper methanol extracts. This demonstrated that molecules perceived through the olfactory pathway were involved in aggregation processes. Furthermore, the efficiency of volatiles from CC paper methanol extracts was significantly improved when their action was combined with contact with low doses of CHs. This result indicated that very low doses of CHs are sufficient and necessary to maintain cockroaches in the odorized arm once they have been attracted there. Therefore, some of the molecules present in the methanol CC paper extracts seem to be attractive from a distance while cuticular hydrocarbons play the role of an arrestant, acting through contact, although the three most important cuticular hydrocarbons of the species profile could be collected in the volatile blend at very short distance and perceived by olfactory neurons (Saïd et al. 2005b). Their olfactory perception does not imply that they are detected as an aggregation signal and our present results indicate that this does not seem to be case. CH extracts of Schistocerca gregaria (F.) induce the transition from the solitarious to the gregarious phase in second and fifth instar larvae when perceived by contact [START_REF] Heifetz | Cuticular hydrocarbons control behavioural phase transition in Schistocerca gregaria larvea and elicit biochemical responses in antennae[END_REF]. CHs of many moths (Geometridae, Arctiida and Noctuidae) attract conspecifics over long distances and alkenes are found in volatile sex pheromones [START_REF] Howard | Ecological, behavioral, and biochemical aspects of insect hydrocarbons[END_REF].

Furthermore, filter papers conditioned by volatile compounds emitted by live cockroaches (VC papers) and methanol extracts of VC papers induced aggregation in binary choice tests and increased the time spent in the odorized arm of the Y-olfactometer.

For the first time long-chained fatty acids have been identified here in the volatile emissions of P. americana. Only 10 molecules were identified from VC paper methanol extracts: 3,5-bis(1,1dimethyl ethyl) phenol, penthaethylene glycol and seven fatty acids. No CHs were found in the VC paper methanol extracts. Although the VC paper methanol extracts contained no CHs, they induced aggregation on the conditioned site in binary choice tests. We assumed that the chemical blend attracted the cockroaches to the site. Then they were maintained on the site by increased contacts between individuals that favoured close range chemical interactions via CHs carried by the nymphs.

The methanol extracts of CC papers and VC papers have saturated and unsaturated fatty acids in common and both types of papers induced aggregation in our experimental tests. The VC papers had less molecules than the CC paper methanol extracts. This can be easily explained by the fact that faeces were also present on the CC papers that were conditioned for several days. Although faeces are attractive in some cockroach species [START_REF] Miller | Use of fecal extract trails to enhance trap catch in German cockroach (Dictyoptera: Blattellidae) monitoring stations[END_REF], their absence in the VC paper chemical blend did not impair aggregation. It seems likely that are not part of the aggregation message. According to [START_REF] Brossut | Pheromonal bases of gregarism and interattraction[END_REF], all attractive substances are not necessarily pheromones. Ethyl phenols were identified by [START_REF] Brossut | Allomonal secretions in cockroaches[END_REF] The identification of the molecules involved in aggregation processes in P. americana will not be complete until the secretion source of the volatile molecules (in particular hexadecanoic acid, pentadecanoic acid and pentaethylene glycol) collected via the VC papers remains unknown. These attractive volatile molecules cannot be given the status of pheromone signals until their origin is elucidated. The glandular system of P. americana is complex but does not include mandibular glands [START_REF] Brossut | L'univers chimique des blattes[END_REF], which is the secretion source of the aggregation pheromone of some Blaberidae species [START_REF] Brossut | Gregarism in cockroaches and in Eublaberus in particular[END_REF][START_REF] Brossut | Le grégarisme chez Blaberus craniifer: isolement et identification de la phéromone[END_REF] To conclude, our results evidenced that aggregation processes in Periplaneta americana relies on a dual mechanism: attraction over long distances by three volatile molecules (hexadecanoic acid, pentadecanoic acid, pentaethylene glycol) that could be the pheromonal signal and maintenance on site by CHs. Cuticular hydrocarbons are considered as specific recognition signals in many social insects [START_REF] Howard | Ecological, behavioral, and biochemical aspects of insect hydrocarbons[END_REF] and could play a similar role in cockroach aggregation processes by decreasing the interindividual tolerance threshold. Insect pheromones are frequently multicomponent blends that can in certain systems function synergistically [START_REF] Tillman | Insect pheromones. An overview of biosynthesis and endocrine regulation[END_REF]. (45,53,65,93,121,138) 10 18,74 0,7

2H indol 2-one 1, 3-dihydro (51,63,78,104,133) 11 19,29 0,5

Benzene acetic acid 3-OH (45,51,63,77,107,123,152) 12 20,5 2,1

Tetradecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,199,228) 13 20,59 0,9

Benzene propanoic acid 4-OH (45,55,65,77,91,107,120,121,149,166) 14 21,23 0,7

Pentadecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,199,242) 15 21,98 0,6

Hexadecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,199,213,239,256) 16 23,34 8,5

Octadecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,199,241,264,284) 17 25,83 7,3 Legend: N = number indicated in Fig. 3; RT: retention time (min); Area (%): relative amounts of compounds.

Name N RT Area (%) Phenol 3,1dimethyl ethyl) (41,57,65,77,91,107,123,135,151,163,175,191,206) 1 24,68 2,80 Dodecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,200) 2 25,33 1,64

Tetradecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,199,228) 3 28,56 7,89

Penta ethylen glycol (45,59,73,87,89,103,133) 4 29,38 8,30

Pentadecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,199,242) 5 30,04 3,81 Phthalate (41,57,76,104,121,149,205,223) 6 30,36 9,26

Hexadecenoic acid (41,55,60,67,69,73,81,96,110,123,148,179,236) 7 31,28 2,83

Hexadecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,199,213,239,256) 8 31,53 42,11

Phthalate (41,57,76,104,121,149,205,223) 9 31,71 7,17

Octadecenoic acid (41,55,60,67,73,81,96,110,123,135,166,264) 10 33,94 6,94

Octadecanoic acid (41,55,60,69,73,83,87,97,101,115,129,137,143,157,171,185,199,241,264,284) 11 34,18 5,88

  . A bimodal or U-shaped pattern of the frequency distribution of tests indicates that, in most tests, individuals aggregated all together and chose one or the other of the resting sites (classes 0-20 % and 81-100 %). Two similar branches of the U indicate that choices were random and that nymphs aggregated as often on either of the papers as expected in control tests. Different heights of the two branches of the U indicate a significant choice, and that subjects aggregated more often on one of the papers. Bell-shaped curves indicate that in most tests individuals were not aggregated all together. They formed groups of different sizes on both papers.

  demonstrated, aggregation is induced through chemical communication in P. americana. Papers conditioned by contact with conspecifics (CC papers) induced aggregation in binary choice tests. This result indicates that chemical factors deposited on the conditioned papers played a role in the choice of rest site and induced aggregation. Similar results were obtained with B. germanica under similar test conditions

  as allomones. They are secreted by sternal glands in P. americana and have a repellent effect. When tested individually, none of the compounds present in VC papers except pentadecanoic acid induced aggregation in binary choice tests. A mixture of two fatty acids (hexadecanoic acid, pentadecanoic acid) plus pentaethylene glycol induced the highest aggregation level observed in binary choice tests. The attractive effects of fatty acids for Periplaneta americana still remains controversial. Many fatty acids extracted from faeces were either repellent or ineffective (McFarlane and Alli 1986). Lactic acids and C2-C6 fatty acids were repellent at high concentrations and ineffective at low concentrations, whereas butyric acid presented in low concentrated aqueous solutions was attractive to P. americana nymphs (McFarlane and Alli 1986).

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Figure 1

Table 1 .

 1 Chemical compounds identified in the CC paper methanol extracts.Legend: N = number indicated in Fig.2; RT: retention time (min); Area (%): relative amounts of compounds.

	Name

Table 2 .

 2 Y-olfactometer tests with Periplaneta americana males. Time (mean ± SE in s) spent in the common stem and in each arm by males tested individually during 5 min. Left arm is always the odorized arm.

		N	Left arm	Right arm	Common stem
	Control test	25	68.16 ± 6.18	86.28 ± 10.33 145 ± 9.92
	CC papers	30	127 ± 12.45**	54 ± 6.44	118.24 ± 14.86
	CC paper methanol extracts	19	105 ± 18.6**	54 ± 5.85	140.82 ± 5.85
	CHs (extracts of 20 nymphs/paper)	34	83 ± 10.02	80 ± 6.45	136.20 ± 11.57
	CC paper methanol extracts + CH	19	145 ± 17.23**	41 ± 7.12	112.63 ± 7.12
	dichloromethane extracts presented
	in contact
	VC paper	22	84 ± 8.45**	50 ± 7.41	164.72 ± 7.41
	VC paper methanol extracts	21	85 ± 12.90**	57 ± 9.52	157.23 ± 14.59

Significant differences from control arm: **: P < 0.005 (Wilcoxon matched-pairs test between the left and the right arm). N = number of tests.

Table 3 :

 3 Chemical compounds identified in VC paper methanol extracts.

Acknowledgements

This work received financial support from the European Commission (IST Program: 2001-35506: LEURRE). I.S. was supported by a post-doctoral grant from the LEURRE program.


Robert Crowston

Michael Fellows

Gregory Gutin

Mark Jones

Eun Jung Kim

Frances Rosamond

Imre Z Rusza

Stéphan Thomassé

Anders Yeo

I Z Ruzsa

Satisfying more than half of a system of linear equations over GF(2): A multivariate approach

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

1.1 MaxLin2-AA and Max-r-Lin2-AA. While MaxSat and its special case Max-r-Sat have been widely studied in the literature on algorithms and complexity for many years, MaxLin2 and its special case Max-r-Lin2 are less well known, but Håstad [START_REF] Håstad | Some optimal inapproximability results[END_REF] succinctly summarized the importance of these 1 two problems by saying that they are "as basic as satisfiability." These problems provide important tools for the study of constraint satisfaction problems such as MaxSat and Max-r-Sat since constraint satisfaction problems can often be reduced to MaxLin2 or Max-r-Lin2, see, e.g., [START_REF] Alon | Solving MAX-r-SAT above a tight lower bound[END_REF][START_REF] Alon | Algorithms with large domination ratio[END_REF][START_REF] Crowston | Note on Max Lin-2 above average[END_REF][START_REF] Crowston | Systems of linear equations over F 2 and problems parameterized above average[END_REF][START_REF] Håstad | Some optimal inapproximability results[END_REF][START_REF] Kim | Improved Parameterized Algorithms for above Average Constraint Satisfaction[END_REF]. Accordingly, in the last decade, MaxLin2 and Max-r-Lin2 have attracted significant attention in algorithmics.

The problem MaxLin2 can be stated as follows. We are given a system of m equations in variables x 1 , . . . , x n , where each equation is i∈I j x i = b j and x i , b j ∈ {-1, 1}, j = 1, . . . , m, and where each equation is assigned a positive integral weight w j . We are required to find an assignment of values to the variables in order to maximize the total weight of the satisfied equations.

Let W be the sum of the weights of all equations in S and let sat(S) be the maximum total weight of equations that can be satisfied simultaneously. To see that W/2 is a tight lower bound on sat(S) choose assignments to the variables independently and uniformly at random. Then W/2 is the expected weight of satisfied equations (as the probability of each equation being satisfied is 1/2) and thus W/2 is a lower bound; to see the tightness consider a system consisting of pairs of equations of the form i∈I x i = -1, i∈I x i = 1 of the same weight, for some non-empty sets I ⊆ [n]. This leads to the following decision problem: MaxLin2-AA Instance: A system S of equations i∈I j x i = b j , where x i , b j ∈ {-1, 1}, j = 1, . . . , m and where each equation is assigned a positive integral weight w j ; and a nonnegative integer k. Question: sat(S) ≥ W/2 + k?

The maximization version of MaxLin2-AA (maximize k for which the answer is Yes), has been studied in the literature on approximation algorithms, cf. [START_REF] Håstad | Some optimal inapproximability results[END_REF][START_REF] Håstad | On the advantage over a random assignment[END_REF]. These two papers also studied the following important special case of MaxLin2-AA: Max-r-Lin2-AA Instance: A system S of equations i∈I j x i = b j , where x i , b j ∈ {-1, 1}, |I j | ≤ r, j = 1, . . . , m; equation j is assigned a positive integral weight w j , and a nonnegative integer k. Question: sat(S) ≥ W/2 + k?

Håstad [START_REF] Håstad | Some optimal inapproximability results[END_REF] proved that, as a maximization problem, Max-r-Lin2-AA with any fixed r ≥ 3 (and hence MaxLin2-AA) cannot be approximated within a constant factor c for any c > 1 unless P=NP (that is, the problem is not in APX unless P=NP). Håstad and Venkatesh [START_REF] Håstad | On the advantage over a random assignment[END_REF] obtained some approximation algorithms for the two problems. In particular, they proved that for Max-r-Lin2-AA there exists a constant c > 1 and a randomized polynomialtime algorithm that, with probability at least 3/4, outputs an assignment with an approximation ratio of at most c r √ m. The problem MaxLin2-AA was first studied in the context of parameterized complexity by Mahajan et al. [START_REF] Mahajan | Parameterizing above or below guaranteed values[END_REF] who naturally took k as the parameter1 . We will denote this parameterized problem by MaxLin2-AA [k]. Despite some progress [START_REF] Crowston | Note on Max Lin-2 above average[END_REF][START_REF] Crowston | Systems of linear equations over F 2 and problems parameterized above average[END_REF][START_REF] Gutin | A probabilistic approach to problems parameterized above or below tight bounds[END_REF], the complexity of MaxLin2-AA [k] has remained prominently open in the research area of "parameterizing above guaranteed bounds" that has attracted much recent attention (cf. [START_REF] Alon | Solving MAX-r-SAT above a tight lower bound[END_REF][START_REF] Crowston | Note on Max Lin-2 above average[END_REF][START_REF] Crowston | Systems of linear equations over F 2 and problems parameterized above average[END_REF][START_REF] Gutin | A probabilistic approach to problems parameterized above or below tight bounds[END_REF][START_REF] Kim | Improved Parameterized Algorithms for above Average Constraint Satisfaction[END_REF][START_REF] Mahajan | Parameterizing above or below guaranteed values[END_REF]) and that still poses well-known and longstanding open problems (e.g., how difficult is it to determine if a planar graph has an independent set of size at least (n/4) + k?). One can parameterize Max-r-Lin2-AA by k for any fixed r (denoted by Max-r-Lin2-AA[k]) or by both k and r (denoted by

Max-r-Lin2-AA[k, r]) 2 .
Define the excess for

x 0 = (x 0 1 , . . . , x 0 n ) ∈ {-1, 1} n over S to be ε S (x 0 ) = m j=1 c j i∈I j
x 0 i , where c j = w j b j .

Note that ε S (x 0 ) is the total weight of equations satisfied by x 0 minus the total weight of equations falsified by x 0 . The maximum possible value of ε S (x 0 ) is the maximum excess of S. Håstad and Venkatesh [START_REF] Håstad | On the advantage over a random assignment[END_REF] initiated the study of the excess of a system of equations and further research on the topic was carried out by Crowston et al. [START_REF] Crowston | Systems of linear equations over F 2 and problems parameterized above average[END_REF] who concentrated on MaxLin2-AA. In this paper, we study the maximum excess for both MaxLin2-AA and Max-r-Lin2-AA.

Note that the excess is a pseudo-boolean function [START_REF] Boros | Pseudo-Boolean optimization[END_REF], i.e., a function that maps {-1, 1} n to the set of reals.

1.2 Main Results and Structure of the Paper. Roughly speaking, a kernelization is a polynomial-time algorithm that transforms an instance I of the parameterized decision problem under consideration into an equivalent instance (called a kernel) I of the same problem such that both the size of I and the value of its parameter are bounded from above by a function in the parameter of I only. Henceforth, O(1) will denote an arbitrary absolute constant.

The main results of this paper are Theorems 3 and 4. In 2006 Mahajan et al. [START_REF] Mahajan | Parameterizing above or below guaranteed values[END_REF] introduced MaxLin2-AA [k] and asked what is its complexity. We answer this question in Theorem 3 by showing that MaxLin2-AA[k] admits a kernel with at most O(k 2 log k) variables. In our kernel, it is only the number of variables that is bounded from above by a polynomial in k. In our kernel, the number of equations is only bounded by an exponential function of k. These two results imply that MaxLin2-AA[k] admits a kernel and, hence, is fixed-parameter tractable (see Section 1.4).

The proof of Theorem 3 is based on two results: (a) If S is an irreducible system (i.e., a system that cannot be reduced using Rule 1 or 2 defined in Section 2) of MaxLin2-AA[k] and 2k ≤ m ≤ 2 n/(2k-1) -2, then S is a Yes-instance; (b) there is an algorithm for MaxLin2-AA[k] of complexity n 2k (nm) O (1) . To prove (a), we introduce a new notion of a sum-free subset of vectors over F 2 and show the existence of such subsets using linear algebra. We also prove that MaxLin2-AA[k] can be solved in time 2 O(k log k) (nm) O(1) (Corollary 1).

The other main result of this paper, Theorem 4, gives a sharp lower bound on the maximum excess for Max-r-Lin2-AA as follows. Let S be an irreducible system and suppose that each equation contains at most r variables. Let n ≥ (k -1)r + 1 and let w min be the minimum weight of an equation of S. Then, in time O(m O(1) ), we can find an assignment x 0 to variables of S such that ε S (x 0 ) ≥ k • w min . Essentially Theorem 4 follows from the existence of sum-free sets of vectors satisfying some simple conditions.

In Section 2, we give some reduction rules for Max-r-Lin2-AA, describe an algorithm H introduced by Crowston et al. [START_REF] Crowston | Systems of linear equations over F 2 and problems parameterized above average[END_REF] and give some properties of the maximum excess, irreducible systems and Algorithm H. In Section 3, we prove Theorem 3 and Corollary 1. A key tool in our proof of Theorem 4 is a lemma on sum-free subsets in a set of vectors from F n 2 . The lemma and Theorem 4 are proved in Section 4. We prove several corollaries of Theorem 4 in Section 5. The corollaries are relevant to parameterized and approximation algorithms, as well as lower bounds for the maxima of pseudo-boolean functions and their applications in graph theory.

Our results on parameterized algorithms improve a number of previously known results including those of Kim and Williams [START_REF] Kim | Improved Parameterized Algorithms for above Average Constraint Satisfaction[END_REF]. In Section 6, we discuss some recent results and open problems.

Corollaries of Theorem 4. The following results have been obtained

for Max-r-Lin2-AA[k] when r is fixed and for Max-r-Lin2-AA[k, r]. Gutin et al. [START_REF] Gutin | A probabilistic approach to problems parameterized above or below tight bounds[END_REF] proved that Max-r-Lin2-AA[k] is fixed-parameter tractable and, moreover, has a kernel with n ≤ m = O(k 2 ). This kernel is, in fact, a kernel of Max-r-Lin2-AA[k, r] with n ≤ m = O(9 r k 2 ). This kernel for Max-r-Lin2-AA[k] was improved by Crowston et al. [START_REF] Crowston | Systems of linear equations over F 2 and problems parameterized above average[END_REF], with respect to the number of variables, to n = O(k log k). For Max-r-Lin2-AA[k], Kim and Williams [START_REF] Kim | Improved Parameterized Algorithms for above Average Constraint Satisfaction[END_REF] were the first to obtain a kernel with a linear number of variables, n = O(k), for fixed r. This kernel is, in fact, a kernel with the number of variables n ≤ r(r + 1)k for Max-r-Lin2-AA[k, r]. In this paper, we obtain a kernel with n ≤ (2k -1)r for Max-r-Lin2-AA[k, r]. As an easy consequence of this result we show that the maximization problem Max-r-Lin2-AA is in APX if restricted to m = O(n) for all fixed r, where the weight of each equation is bounded by a constant. This is in sharp contrast with the fact mentioned above that for each r ≥ 3, Max-r-Lin2-AA with arbitrary weights is not in APX unless P=NP.

Fourier analysis of pseudo-boolean functions, i.e., functions f : {-1, 1} n → R, has been used in many areas of computer science (cf. [START_REF] Alon | Solving MAX-r-SAT above a tight lower bound[END_REF][START_REF] Choi | Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions[END_REF][START_REF] Crowston | Systems of linear equations over F 2 and problems parameterized above average[END_REF][START_REF] Donnell | Some topics in analysis of Boolean functions[END_REF]). In Fourier analysis, the Boolean domain is often assumed to be {-1, 1} n rather than more usual {0, 1} n and we will follow this assumption in our paper. Here we use the following well-known and easy to prove fact (see, e.g., [START_REF] Donnell | Some topics in analysis of Boolean functions[END_REF]): each function f : {-1, 1} n → R can be uniquely written as

f (x) = f (∅) + I∈F f (I) i∈I x i . (1)
where F ⊆ {I :

∅ = I ⊆ [n]}, [n] = {1, 2, . . . , n}, x i ∈ {-1, 1}
, and f (I) are non-zero reals. Formula ( 1) is the Fourier expansion of f and f (I) are the Fourier coefficients of f . The right hand side of ( 1) is a polynomial and the degree max{|I| : I ∈ F} of this polynomial will be called the degree of f . Let A be a (0, 1)-matrix with n rows and |F| columns and with entries a ij such that a ij = 1 if and only if term j in (1) contains x i .

In Section 5, we obtain the following lower bound on the maximum of a pseudo-boolean function f of degree r:

max x f (x) ≥ f (∅) + (rank(A) + r -1)/r • min{| f (I)| : I ∈ F}, (2)
where rank(A) is the rank of A over F 2 . (Note that since rank(A) does not depend on the order of the columns in A, we may order the terms in (1) arbitrarily.) To demonstrate the combinatorial usefulness of ( 2), we apply it to obtain a short proof of the well-known lower bound of Edwards-Erdős on the maximum size of a bipartite subgraph in a graph (the Max Cut problem). Erdős [START_REF] Erdős | On some extremal problems in graph theory[END_REF] conjectured and Edwards [START_REF] Edwards | An improved lower bound for the number of edges in a largest bipartite subgraph[END_REF] proved that every connected graph with n vertices and m edges has a bipartite subgraph with at least m/2 + (n -1)/4 edges. For short graph-theoretical proofs, see, e.g., Bollobás and Scott [START_REF] Bollobás | Better bounds for max cut[END_REF] and Erdős et al. [START_REF] Erdős | The size of the largest bipartite subgraphs[END_REF]. We consider the Balanced Subgraph problem [START_REF] Böcker | A faster fixedparameter approach to drawing binary tanglegrams[END_REF] that generalizes Max Cut and show that our proof of the Edwards-Erdős bound can be easily extended to Balanced Subgraph. 1) , where f is a function of the parameter k only. If membership can be decided in time O(|x| f (k) ) then L belongs to the parameterized complexity class XP. It is known that FPT is a proper subset of XP [START_REF] Downey | Parameterized Complexity[END_REF]. Analogs of NP are provided by the classes of parameterized problems of the W[t] Hierarchy giving the tower:

Parameterized Complexity and (Bi

)kernelization. A parameterized problem is a subset L ⊆ Σ * × N over a finite alphabet Σ. L is fixed-parameter tractable (FPT, for short) if membership of an instance (x, k) in Σ * × N can be decided in time f (k)|x| O(
FPT ⊆ W[1] ⊆ W[2] ⊆ • • • ⊆ XP.
For the definition of the classes W[t], see, e.g., [START_REF] Downey | Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF].

Given a pair L, L of parameterized problems, a bikernelization from L to L is a polynomial-time algorithm that maps an instance (x, k) to an instance (x , k

) (the bikernel ) such that (i) (x, k) ∈ L if and only if (x , k ) ∈ L , (ii) k ≤ f (k), and (iii) |x | ≤ g(k)
for some functions f and g. The function g(k) is called the size of the bikernel. The notion of a bikernelization was introduced in [START_REF] Alon | Solving MAX-r-SAT above a tight lower bound[END_REF], where it was observed that a parameterized problem L is fixed-parameter tractable if and only if it is decidable and admits a bikernelization to a parameterized problem L . A kernelization of a parameterized problem L is simply a bikernelization from L to itself; the bikernel is the kernel, and g(k) is the size of the kernel. Due to the importance of polynomial-time kernelization algorithms in applied multivariate algorithmics, low degree polynomial size kernels and bikernels are of considerable interest, and the subject has developed substantial theoretical depth, cf. [START_REF] Alon | Solving MAX-r-SAT above a tight lower bound[END_REF][START_REF] Bodlaender | On problems without polynomial kernels[END_REF][START_REF] Bodlaender | Cross-Composition: A new technique for kernelization lower bounds[END_REF][START_REF] Bodlaender | Kernel bounds for disjoint cycles and disjoint paths[END_REF][START_REF] Dom | Incrompressibility though Colors and IDs[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Fomin | Hitting forbidden minors: Approximation and kernelization[END_REF][START_REF] Gutin | All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic number of vertices[END_REF][START_REF] Gutin | A probabilistic approach to problems parameterized above or below tight bounds[END_REF].

The case of several parameters k 1 , . . . , k t , as for Max-r-Lin2-AA[k, r], can be reduced to the one parameter case by setting k = k 1 + • • • + k t , see, e.g., [START_REF] Dom | Incrompressibility though Colors and IDs[END_REF]. We remark that other ways of handling multiple parameters (other than just adding them up) is an area of active investigation, e.g., see [START_REF] Fellows | Towards Full Multivariate Algorithmics: Parameter Ecology and the Deconstruction of Computational Complexity[END_REF].

Maximum Excess, Irreducible Systems and Algorithm H

Recall that an instance of MaxLin2-AA consists of a system S of equations

i∈I j x i = b j , j ∈ [m], where ∅ = I j ⊆ [n], b j ∈ {-1, 1}, x i ∈ {-1,
1}. An equation i∈I j x i = b j has an integral positive weight w j . Recall that the excess for

x 0 = (x 0 1 , . . . , x 0 n ) ∈ {-1, 1} n over S is ε S (x 0 ) = m j=1 c j i∈I j x 0 i
, where c j = w j b j . The excess ε S (x 0 ) is the total weight of equations satisfied by x 0 minus the total weight of equations falsified by x 0 . The maximum possible value of ε S (x 0 ) is the maximum excess of S.

Remark 1.

Observe that the answer to MaxLin2-AA is Yes if and only if the maximum excess is at least 2k.

Remark 2. The excess ε S (x) is a pseudo-boolean function and its Fourier expression is ε S (x) = m j=1 c j i∈I j x i . Moreover, observe that every pseudoboolean function f (x) = I∈F f (I) i∈I x i (where f (∅) = 0) is the excess

over the system i∈I x i = b I , I ∈ F, where b I = 1 if f (I) > 0 and b I = -1 if f (I) < 0, with weights | f (I)|.
Thus, studying the maximum excess over a MaxLin2-AA-system (with real weights) is equivalent to studying the maximum of a pseudo-boolean function.

Consider two reduction rules for MaxLin2 studied in [START_REF] Gutin | A probabilistic approach to problems parameterized above or below tight bounds[END_REF]. Rule 1 was studied before in [START_REF] Håstad | On the advantage over a random assignment[END_REF]. In what follows, we will use the fact that a maximum independent set in a set M of vectors from F n 2 , can be found in polynomial time in n and |M | [START_REF] Korte | Combinatorial Optimization: theory and algorithms[END_REF].

Reduction

Henceforth, rank(A) will denote the rank of A over F 2 .

Reduction Rule 2. Let A be the matrix over F 2 corresponding to the set of equations in S, such that a ji = 1 if i ∈ I j and 0, otherwise. Let t = rank(A) and suppose columns a i 1 , . . . , a it of A are linearly independent. Then delete all variables not in {x i 1 , . . . , x it } from the equations of S.

Observe that after applying Rule 2, the resulting matrix A has rank equal n.

Lemma 1. [START_REF] Gutin | A probabilistic approach to problems parameterized above or below tight bounds[END_REF] Let S be obtained from S by Rule 1 or 2. Then the maximum excess of S is equal to the maximum excess of S. Moreover, S can be obtained from S in time polynomial in n and m.

If we cannot change a weighted system S using Rules 1 and 2, we call it irreducible.

Lemma 2. Let S be a system obtained from S by first applying Rule 1 as long as possible and then Rule 2 as long as possible. Then S is irreducible.

Proof. Let S * denote the system obtained from S by applying Rule 1 as long as possible. Without loss of generality, assume that x 1 ∈ {x i 1 , . . . , x it } (see the description of Rule 2) and thus Rule 2 removes x 1 from S * . To prove the lemma it suffices to show that after the removal of x 1 no pair of equations has the same left hand side. Suppose that there is a pair of equations in S * which has the same left hand side after the removal of x 1 ; let i∈I x i = b and i∈I x i = b be such equations and let I = I ∪ {1}. Then the entries of the first column of A, a 1 , corresponding to the pair of equations are 1 and 0, but in all the other columns of A the entries corresponding to the pair of equations are either 1,1 or 0,0. Thus, a 1 is independent from all the other columns of A, a contradiction.

Let S be an irreducible system of MaxLin2-AA. Consider the following algorithm. We assume that, in the beginning, no equation or variable in S is marked.

Algorithm H While the system S is nonempty do the following: 1. Choose an equation i∈I x i = b and mark a variable x l such that l ∈ I.

2. Mark this equation and delete it from the system.

3. Replace every equation i∈I x i = b in the system containing x l by i∈I∆I x i = bb , where I∆I is the symmetric difference of I and I (the weight of the equation is unchanged).

Apply Reduction Rule 1 to the system.

The maximum H-excess of S is the maximum possible total weight of equations marked by H for S taken over all possible choices in Step 1 of H.

The following lemma indicates the potential power of H. Lemma 3. Let S be an irreducible system. Then the maximum excess of S equals its maximum H-excess. Furthermore, for any set of equations marked by Algorithm H, in polynomial time, we can find an assignment of excess at least the total weight of marked equations.

Proof. We first prove that the maximum excess of S is not smaller than its maximum H-excess. By construction, for any assignment that satisfies all the marked equations, exactly half of the non-marked equations are satisfied. Therefore it suffices to find an assignment to the variables such that all marked equations are satisfied. Assign arbitrary values to the unmarked variables. Then assign values to the marked variables in the order opposite to which they were marked such that the corresponding marked equations are satisfied.

The above argument also proves the last statement of the lemma. Now we prove that the maximum H-excess of S is not smaller than its maximum excess. Let x 0 = (x 0 1 , . . . , x 0 n ) be an assignment that achieves the maximum excess, t. Observe that if at each iteration of H we mark an equation that is satisfied by x 0 , then H will mark equations of total weight t.

then, in time polynomial in |M | and n, we can find an M -sum-free set K of k + 1 vectors.

Proof. We first consider the case when k = 1. Since |M | < 2 n and the zero vector is in M , there is a non-zero vector v ∈ M . Since M contains a basis for F n 2 , the vector v can be written as a sum of vectors in M . Consider such a sum with the minimum number of summands:

v = u 1 + • • • + u , ≥ 2. Since u 1 + u 2 ∈ M , we may set K = {u 1 , u 2 }.
We can find such a set K in polynomial time by looking at every pair in M × M .

We now assume that k > 1. Since k

+ 1 ≤ |M | ≤ 2 n/k and k ≥ 2, we have n ≥ k + 1.
We proceed with a greedy algorithm that tries to find K. Suppose we have a set L = {a 1 , . . . , a l } of vectors in M , l ≤ k, such that no sum of two or more elements of L is in M . We can extend this set to a basis, so a 1 = (1, 0, 0, . . . , 0), a 2 = (0, 1, 0, . . . , 0) and so on. For every a ∈ M \L we check whether M \{a 1 , . . . , a l , a} has an element that agrees with a in all coordinates l + 1, . . . , n. If no such element exists, then we add a to the set L, as no element in M can be expressed as a sum of a and a subset of L.

If our greedy algorithm finds a set L of size at least k + 1, we are done and L is our set K. Otherwise, we have stopped at l ≤ k. In this case, we do the next iteration as follows. Recall that L is part of a basis of M such that a 1 = (1, 0, 0, . . . , 0), a 2 = (0, 1, 0, . . . , 0), . . . . We create a new set M in F n 2 , where n = n -l. We do this3 by removing the first l co-ordinates from M , and then identifying together any vectors that agree in the remaining n co-ordinates. We are in effect identifying together any vectors that only differ by a sum of some elements in L. It follows that every element of M was created by identifying together at least two elements of M , since otherwise we would have had an element in M \L that should have been added to L by our greedy algorithm. Therefore it follows that |M | ≤ |M |/2 ≤ 2 n/k-1 . From this inequality and the fact that n ≥ n -k, we get that |M | ≤ 2 n /k . It also follows by the construction of M that M has a basis for F n 2 , and that the zero vector is in M . (Thus, we have |M | ≥ n + 1.) If n ≥ k + 1 we complete this iteration by running the algorithm on the set M as in the first iteration. Otherwise (n ≤ k) and the algorithm stops.

Since each iteration of the algorithm decreases n , the algorithm terminates. Now we prove that at some iteration, the algorithm will actually find a set K of k + 1 vectors. To show this it suffices to prove that we will never reach the point when n ≤ k. Suppose this is not true and we obtained n ≤ k. Observe that n ≥ 1 (before that we had n ≥ k + 1 and we decreased n by at most k) and |M | ≥ n + 1. Since |M | ≤ 2 n /k , we have n + 1 ≤ 2 n /k , which is impossible due to n ≤ k unless n = 1 and k = 1, a contradiction with the assumption that k > 1.

It is easy to check that the running time of the algorithm is polynomial in |M | and n.

Theorem 2. Let S be an irreducible system of MaxLin2-AA[k] and let k ≥ 1. If 2k ≤ m ≤ min{2 n/(2k-1) -1, 2 n -2}, then the maximum excess of S is at least 2k. Moreover, we can find an assignment with excess of at least 2k in time O(m O(1) ).

Proof. Consider a set M of vectors in F n

2 corresponding to equations in S as follows: for each equation i∈I x i = b in S, define a vector v = (v 1 , . . . , v n ) ∈ M , where v i = 1 if i ∈ I and v i = 0, otherwise. Add the zero vector to M .

As S is reduced by Rule 2 and 2k ≤ m ≤ min{2 n/(2k-1) -1, 2 n -2}, we have that M contains a basis for F n 2 and 2k ≤ |M | ≤ min{2 n/(2k-1) , 2 n -1}. Therefore, using Lemma 4 we can find an M -sum-free set K of 2k vectors. Let {e j 1 , . . . , e j 2k } be the corresponding set of equations. Run Algorithm H, choosing at Step 1 an equation of S from {e j 1 , . . . , e j 2k } each time, and let S be the resulting system. Algorithm H will run for 2k iterations of the while loop as no equation from {e j 1 , . . . , e j 2k } will be deleted before it has been marked.

Indeed, suppose that this is not true. Then for some e j l and some other equation e in S, after applying Algorithm H for at most l -1 iterations e j l and e contain the same variables. Thus, there are vectors v j ∈ K and v ∈ M and a pair of nonintersecting subsets K and K of K \ {v, v j } such that v j + u∈K u = v + u∈K u. Thus, v = v j + u∈K ∪K u, contradicting the definition of K.

Thus, by Lemma 3, we are done.

Theorem 3. The problem MaxLin2-AA[k] has a kernel with at most O(k 2 log k) variables.

Proof. Let L be an instance of MaxLin2-AA[k] and let S be the system of L with m equations and n variables. We may assume that S is irreducible. Let the parameter k be an arbitrary positive integer. If m < 2k then n < 2k = O(k 2 log k) and we are done. Otherwise, if 2k ≤ m ≤ 2 n/(2k-1) -2 then, by Theorem 2 and Remark 1, the answer to L is yes and the corresponding assignment can be found in polynomial time. If m ≥ n 2k -1 then, by Theorem 1, we can solve L in polynomial time.

Finally we consider the case

2 n/(2k-1) -2 ≤ m ≤ n 2k -2. Hence, n 2k ≥ 2 n/(2k-1) . Therefore, 4k 2 ≥ 2 + n/ log n ≥ √ n and n ≤ (2k) 4 . Hence, n ≤ 4k 2 log n ≤ 4k 2 log(16k 4 ) = O(k 2 log k).
Since S is irreducible, m < 2 n ≤ 2 O(k 2 log k) and thus we have obtained the desired kernel. 1) ) either we solve L or we obtain a kernel with at most O(k 2 log k) variables. In the second case, we can solve the reduced system (kernel) by the algorithm of Theorem 1) . Thus, the total time is 2 O(k log k) (nm) O (1) .

Corollary 1. The problem MaxLin2-AA[k] can be solved in time 2 O(k log k) (nm) O(1) . Proof. Let L be an instance of MaxLin2-AA[k]. By Theorem 3, in time O((nm) O(
1 in time [O(k 2 log k)] 2k [O(k 2 log k)m] O(1) = 2 O(k log k) m O(

Max-r-Lin2-AA

The following theorem is the main result of this section.

Theorem 4. Let S be an irreducible system and suppose that each equation contains at most r variables. Let n ≥ (k -1)r +1 and let w min be the minimum weight of an equation of S. Then, in time O(m O(1) ), we can find an assignment x 0 to variables of S such that ε S (x 0 ) ≥ k • w min .

We can easily prove Theorem 4 in the same way as we proved Theorem 2, but instead of Lemma 4, we use Lemma 5.

Lemma 5. Let M be a set of vectors in F n 2 such that M contains a basis of F n 2 . Suppose that each vector of M contains at most r non-zero coordinates.

If k ≥ 1 is an integer and n ≥ r(k -1) + 1, then in time O(|M | O(1) ), we can find a subset K of M of k vectors such that K is M -sum-free.
Proof. Since the case of k = 1 is trivial, we may assume that k ≥ 2. Let 1 = (1, . . . , 1) be the vector in F n 2 in which every coordinate is 1. Note that 1 ∈ M. By our assumption M contains a basis B of F n 2 and we may write 1 as a sum of some vectors of B. This implies that 1 can be expressed as follows:

1 = v 1 + v 2 + • • • + v s ,
where {v 1 , . . . , v s } ⊆ B and v 1 , . . . , v s are linearly independent, and we can find such an expression in polynomial time.

For each v ∈ M \{v 1 , . . . , v s }, consider the set S v = {v, v 1 , . . . , v s }. In polynomial time, we may check whether S v is linearly independent. Consider two cases: Case 1: S v is linearly independent for each v ∈ M \{v 1 , . . . , v s }. Then {v 1 , . . . , v s } is M -sum-free (here we also use the fact that {v 1 , . . . , v s } is linearly independent). Since each v i has at most r positive coordinates, we have sr ≥ n > r(k -1). Hence, s > k -1 implying that s ≥ k. Thus, {v 1 , . . . , v k } is the required set K.

Case 2: S v is linearly dependent for some v ∈ M \{v 1 , . . . , v s }. Then we can find (in polynomial time) I ⊆ [s] such that v = i∈I v i . Thus, we have a shorter expression for 1: Since s ≤ n and Case 2 produces a shorter expression for 1, after at most n iterations of Case 2 we will arrive at Case 1.

1 = v 1 + v 2 + • • • + v s ,
Remark 4. To see that the inequality n ≥ r(k -1) + 1 in the theorem is best possible assume that n = r(k -1) and consider a partition of [n] into k -1 subsets N 1 , . . . , N k-1 , each of size r. Let S be the system consisting of subsystems S p , p ∈ [k -1], such that a subsystem S p is comprised of equations i∈I x i = -1 of weight 1 for every I such that ∅ = I ⊆ N p . Now assume without loss of generality that N p = [r]. Observe that the assignment (x 1 , . . . , x r ) = (1, . . . , 1) falsifies all equations of S p but by setting x j = -1 for any j ∈ [r] we satisfy the equation x j = -1 and turn the remaining equations into pairs of the form i∈I x i = -1 and i∈I x i = 1. Thus, the maximum excess of S p is 1 and the maximum excess of S is k -1.

Remark 5. It is easy to check that Theorem 4 holds when the weights of equations in S are real numbers, not necessarily integers, assuming unit cost real arithmetic (as in the model of Blum et al. [START_REF] Blum | Complexity and Real Computation[END_REF]).

Applications of Theorem 4

Theorem 5. The problem Max-r-Lin2-AA[k, r] has a kernel with at most (2k -1)r variables.

Proof. Let T be the system of an instance of Max-r-Lin2-AA[k, r]. After applying Rules 1 and 2 to T as long as possible, we obtain a new system S which is irreducible. Let n be the number of variables in S and observe that the number of variables in an equation in S is bounded by r (as in T ). If n ≥ (2k -1)r + 1, then, by Theorem 4 and Remark 1, S is a Yes-instance of Max-r-Lin2-AA[k, r] and, hence, by Lemma 1, S and T are both Yesinstances of Max-r-Lin2-AA[k, r]. Otherwise n ≤ (2k -1)r and since S is irreducible, for the number m of equations in S, we have m < 2 n ≤ 2 (2k-1)r . Thus, we have the required kernel. Proof. It follows from Theorem 4 and Remark 1 that the answer to Max-r-Lin2-AA, as a decision problem, is Yes as long as 2k ≤ (n + r -1)/r . This implies approximation ratio at most W/(2 (n + r -1)/r ) which is bounded by a constant provided m = O(n) and the weight of each equation is bounded by a constant (then W = O(n)).

The (parameterized) Boolean Max-r-Constraint Satisfaction Problem (Maxr-CSP) generalizes MaxLin2-AA[k, r] as follows: We are given a set Φ of Boolean functions, each involving at most r variables, and a collection F of m Boolean functions, each f ∈ F being a member of Φ, and each acting on some subset of the n Boolean variables x 1 , x 2 , . . . , x n (each x i ∈ {-1, 1}). We are to decide whether there is a truth assignment to the n variables such that the total number of satisfied functions is at least E + k, where E is the average value of the number of satisfied functions. The parameters are k and r.

Using the bikernelization algorithm described in [START_REF] Alon | Solving MAX-r-SAT above a tight lower bound[END_REF][START_REF] Crowston | Systems of linear equations over F 2 and problems parameterized above average[END_REF] and our new kernel result, it easy to see that Max-r-CSP with parameters k and r admits a bikernel with at most (k2 r+1 -1)r variables. This result improves the corresponding result of Kim and Williams [START_REF] Kim | Improved Parameterized Algorithms for above Average Constraint Satisfaction[END_REF] (n ≤ kr(r + 1)2 r ).

The following result is essentially a corollary of Theorem 4 and Remark 5.

Theorem 6. Let f (x) = f (∅) + I∈F f (I) i∈I x i (3)
be a pseudo-boolean function of degree r. Then

max x f (x) ≥ f (∅) + (rank(A) + r -1)/r • min{| f (I)| : I ∈ F}, (4)
where A is a (0, 1)-matrix with entries a ij such that a ij = 1 if and only if term j in (3) contains x i and rank(A) is the rank of A over F 2 . One can find an assignment of values to x satisfying (4) in time O((n|F|) O( 1) ).

Proof. By Remark 2 the function f (x) -f (∅) = I∈F f (I) i∈I x i is the excess over the system i∈I x i = b I , I ∈ F, where b I = +1 if f (I) > 0 and b I = -1 if f (I) < 0, with weights | f (I)|. Clearly, Rule 1 will not change the system. Using Rule 2 we can replace the system by an equivalent one (by Lemma 1) with rank(A) variables. By Lemma 2, the new system is irreducible and we can now apply Theorem 4. By this theorem, Remark 2 and Remark 5, max

x f (x) ≥ f (∅) + k * min{| f (I)| : I ∈ F}, where k * is the maximum value of k satisfying rank(A) ≥ (k -1)r + 1. It remains to observe that k * = (rank(A) + r -1)/r .
We next give a new proof of the Edwards-Erdős bound, we need the following well-known and easy-to-prove lemma [START_REF] Bondy | Graph Theory[END_REF]. For a graph G = (V, E), an incidence matrix is a (0, 1)-matrix with entries m e,v , e ∈ E, v ∈ V such that m e,v = 1 if and only if v is incident to e. systems for which the maximum excess is less than 2k which would be of interest in itself.

Let F be a CNF formula with clauses C 1 , . . . , C m of sizes r 1 , . . . , r m . Since the probability of C i being satisfied by a random assignment is 1 -2 -r i , the expected (average) number of satisfied clauses is E = m i=1 (1 -2 -r i ). It is natural to consider the following parameterized problem MaxSat-AA[k]: decide whether there is a truth assignment that satisfies at least E + k clauses. When there is a constant r such that |C i | ≤ r for each i = 1, . . . , m, MaxSat-AA[k] is denoted by Max-r-Sat-AA[k]. Mahajan et al. [START_REF] Mahajan | Parameterizing above or below guaranteed values[END_REF] asked what is the complexity of Max-r-Sat-AA[k] and Alon et al. [START_REF] Alon | Solving MAX-r-SAT above a tight lower bound[END_REF] proved that it is fixedparameter tractable [START_REF] Alon | Solving MAX-r-SAT above a tight lower bound[END_REF]. Recently, Crowston et al. [START_REF] Crowston | Parameterized Complexity of MaxSat Above Average[END_REF] determined the complexity of MaxSat-AA[k] by showing that MaxSat-AA [START_REF] Alon | Algorithms with large domination ratio[END_REF] is NP-complete. Thus, MaxSat-AA[k] is not fixed-parameter tractable unless P=NP.

In a graph G = (V, E), a bisection (X, Y ) is a partition of V into sets X and Y such that |X| ≤ |Y | ≤ |X| + 1. The size of (X, Y ) is the number of edges between X and Y . In Max Bisection, we are given a graph G with n ≥ 2 vertices and m edges and asked to find a bisection of maximum size. It is not hard to see that m/2 is a tight lower bound on the maximum size of a bisection of G. Gutin and Yeo [START_REF] Gutin | Note on Maximal Bisection above Tight Lower Bound[END_REF] proved that Max Bisection parameterized above m/2 has a kernel with O(k 2 ) vertices. Mnich and Zenklusen [START_REF] Mnich | Bisections above Tight Lower Bounds[END_REF] improved it to O(k) vertices. Gutin and Yeo [START_REF] Gutin | Note on Maximal Bisection above Tight Lower Bound[END_REF] also showed that

Rule 1 .

 1 If we have, for a subset I of [n], an equation i∈I x i = b I with weight w I , and an equation i∈I x i = b I with weight w I , then we replace this pair by one of these equations with weight w I + w I if b I = b I and, otherwise, by the equation whose weight is bigger, setting its new weight to |w I -w I |. If the resulting weight is 0, we delete the equation from the system. Remark 3.

Corollary 2 .

 2 The maximization problem Max-r-Lin2-AA is in APX if restricted to m = O(n) and the weight of each equation is bounded by a fixed constant.

nm 2 ( 1 4

 21 n-1) is another tight lower bound on the maximum size of a bisection of G. Clearly, nm 2(n-1) ≥ m/2 . Gutin and Yeo[START_REF] Gutin | Note on Maximal Bisection above Tight Lower Bound[END_REF] left it as an open problem to determine the complexity of Max Bisection parameterized above nm 2(n-1) . In Theorem 7, we gave another proof that every connected graph G with n vertices and m edges, has a bipartite subgraph with at least = m 2 + n-edges. Recently, Crowston et al.[START_REF] Crowston | Max-Cut Parameterized above the Edwards-Erdős Bound[END_REF] solved an open question by showing that deciding whether G contains a bipartite subgraph with at least + k edges is fixed-parameter tractable and the problem admits a kernel with O(k 5 ) vertices. Crowston et al.[START_REF] Crowston | Maximum Balanced Subgraph Problem Parameterized Above Lower Bound[END_REF] improved this to O(k 3 ) and showed that such a kernel exists for the more general problem of deciding whether a connected graph with edges labelled by = and =, has a balanced subgraph with at least + k edges (for the bound, see Theorem 8). Can O(k 3 ) be further improved? Finally, the entire area of parameterizing above or below tight guaranteed bounds offers many challenging open problems in parameterized complexity. search of Kim and Thomassé was partially supported by the AGAPE project (ANR-09-BLAN-0159).

  where {v 1 , . . . , v s } = {v} ∪ {v i : i / ∈ I}. Note that {v 1 , . . . , v s } is linearly independent.

We provide basic definitions on parameterized algorithms and complexity in Subsection 1.4 below.

While in the preceding literature only MaxLin2-AA[k] was considered, we introduce and study Max-r-Lin2-AA[k, r] in the spirit of Multivariate Algorithmics as outlined by Fellows et al.[START_REF] Fellows | Towards Full Multivariate Algorithmics: Parameter Ecology and the Deconstruction of Computational Complexity[END_REF] and Niedermeier[START_REF] Niedermeier | Reflections on Multivariate Algorithmics and Problem Parameterization[END_REF].

For the reader familiar with vector space terminology: F n 2 is F n 2 modulo span(L), the subspace of F n 2 spanned by L, and M is the image of M in F n 2 .

Acknowledgments The research of Crowston, Gutin, Jones and Yeo was partially supported by an International Joint grant of Royal Society. Fellows was supported by an Australian Research Council Professorial Fellowship. Gutin was also supported in part by the IST Programme of the European Community, under the PASCAL 2 Network of Excellence. The research of Rosamond was supported by an Australian Research Council Discovery Project. The re-

MaxLin2-AA

The following two theorems provide a basis for proving Theorem 3, the main result of this section. Theorem 1. There exists an O(n 2k (nm) O (1) )-time algorithm for MaxLin2-AA[k] that returns an assignment of excess of at least 2k if one exists, and returns no otherwise.

Proof. Suppose we have an instance L of MaxLin2-AA[k] that is reduced by Rules 1 and 2, and that the maximum excess of L is at least 2k. Let A be the matrix introduced in Rule 2. Pick n equations e 1 , . . . , e n such that their rows in A are linearly independent. An assignment of excess at least 2k must either satisfy one of these equations, or falsify them all. If they are all falsified, then the system of equations ē1 , . . . , ēn , where each ēi is e i with the changed right hand side, has a unique solution, an assignment of values to x 1 , . . . , x n . If this assignment does not give excess at least 2k for L, then any assignment that leads to excess at least 2k must satisfy at least one of e 1 , . . . , e n . Thus, by Lemma 3, algorithm H can mark one of these equations and achieve an excess of at least 2k. This gives us the following depth-bounded search tree. At each node N of the tree, reduce the system by Rules 1 and 2, and let n be the number of variables in the reduced system. Then find n equations e 1 , . . . , e n corresponding to linearly independent vectors. Find an assignment of values to x 1 , . . . , x n that falsifies all of e 1 , . . . , e n . Check whether this assignment achieves excess of at least 2k -w * , where w * is total weight of equations marked by H in all predecessors of N . If it does, then return the assignment and stop the algorithm. Otherwise, split into n branches. In the i'th branch, run an iteration of H marking equation e i . Then repeat this algorithm for each new node. Whenever the total weight of marked equations is at least 2k, return the suitable assignment. Clearly, the algorithm will terminate without an assignment if the maximum excess of L is less than 2k.

All the operations at each node take time O((nm) O(1) ), and there are less than n 2k+1 nodes in the search tree. Therefore this algorithm takes time O(n 2k (nm) O( 1) ).

The following lemma is used to prove Theorem 2, but it might be also of independent interest. Let K and M be sets of vectors in F n 2 such that K ⊆ M . We say K is M -sum-free if no sum of two or more distinct vectors in K is equal to a vector in M . Observe that K is M -sum-free if and only if K is linearly independent and no sum of vectors in K is equal to a vector in M \K. Theorem 7. Let G = (V, E) be a connected graph with n vertices and m edges. Then G contains a bipartite subgraph with at least m 2 + n-1 4 edges. Such a subgraph can be found in polynomial time.

Proof. Let V = {v 1 , v 2 , . . . , v n } and let c : V → {-1, 1} be a 2-coloring of G. Observe that the maximum number of edges in a bipartite subgraph of G equals the maximum number of properly colored edges (i.e., edges whose end-vertices received different colors) over all 2-colorings of G. For an edge e = v i v j ∈ E consider the following function f e (x) = 1 2 (1 -x i x j ), where x i = c(v i ) and x j = c(v j ) and observe that f e (x) = 1 if e is properly colored by c and f e (x) = 0, otherwise. Thus, f (x) = e∈E f e (x) is the number of properly colored edges for c. We have f (x) = m 2 -1 2 e∈E x i x j . By Theorem 6, max x f (x) ≥ m/2 + (rank(A) + 2 -1)/2 /2. Observe that matrix A in this bound is an incidence matrix of G and, thus, by Lemma 6

This theorem can be extended to the Balanced Subgraph problem [START_REF] Böcker | A faster fixedparameter approach to drawing binary tanglegrams[END_REF], where we are given a graph G = (V, E) in which each edge is labeled either by = or by = and we are asked to find a 2-coloring of V such that the maximum number of edges is satisfied; an edge labeled by = ( =, resp.) is satisfied if and only if the colors of its end-vertices are the same (different, resp.). Theorem 8. Let G = (V, E) be a connected graph with n vertices and m edges labeled by either = or =. There is a 2-coloring of V that satisfies at least m 2 + n-1 4 edges of G. Such a 2-coloring can be found in polynomial time.

Proof. Let V = {v 1 , v 2 , . . . , v n } and let c :

) counts the number of edges satisfied by c. The rest of the proof is similar to that in the previous theorem.

Discussion and Open Problems

The kernels obtained in Theorems 3 and 5 are not of polynomial size as the number of equations in the kernels is not bounded by a polynomial in the parameter(s). The existence of polynomial-size kernels for MaxLin2-AA[k] and Max-r-Lin2-AA[k, r] remains an open question.

Perhaps the kernel obtained in Theorem 3 or the algorithm of Corollary 1 can be improved if we can find a structural characterization of irreducible