Rémy Le Boennec
email: remy.leboennec@vedecom.fr

Isabelle Nicolaï

Pascal Da Costa

Implementing a two-step decision-aid tool for the assessment of new mobility offers in a spatial framework

Keywords: multicriteria decision analysis, decision-aid tool, mobility offer, mobility usage

In this article we seek to elaborate various sustainable mobility scenarios depending on heterogeneous geographical contexts. We use a multicriteria decision analysis (MCDA) to assess 50 mobility offers, relying on an original two-step assessment method. In a first step, we use the diviz decision-aid tool to obtain a global score for every offer, on the basis of 18 criteria that cover the three domains of sustainable development: economics, environment, society. In a second step, we use the MICMAC decision-aid tool to build relationships of influence and dependency between the 18 criteria. For each type of territory, we state what could be a development scenario for the future of mobility. Ultimately, an innovative hybrid mobility solution relies on the strengths and levers of the offers that were assessed, in response to the mobility scenario. We identify relevant solutions for dense and low-dense areas: in particular, carpooling offers reach particular efficiency in low-dense areas, combined with walking practices. Such combinations should be assisted by reliable multimodal mobility applications.

Introduction

Despite encouraging signs, new sustainable mobility offers still face psychological and sociological obstacles to behavior change (Buhler 2012, Créno 2016[START_REF] Dantan | Enhancing sustainable mobility through a multimodal platform: would travellers pay for it?[END_REF]. For example, car-sharing is developing in large cities but it does not find its model in medium-sized cities (see for the example the defection in 2014 of the carsharing service in the French city of Pau, 160,000 inhabitants). Similarly, while BlaBlaCar is a testament to the success of carpooling on long-distance planned trips, short-distance or real-time carpooling encounters difficulties (even if the two BlaBla lines launched in France in 2017 should be watched). Private-hire companies like Uber or Lyft seem to correspond to a strong expectation from mobility users, but only in very dense areas for the moment. A common feature of new mobility solutions is that they rely on Intelligent Transportation Systems (ITS), which "early adopters" use via mobility applications on their smartphone [START_REF] Dantan | Hurried or risk-adverse travelers: who will pay more for multimodal information?[END_REF], CGDD DGE PIPAME 2016[START_REF] Lab | Vers un transport de MaaS[END_REF].

Historic offers like public transport have to adapt to maintain significant market shares, particularly in low-dense territories where they are currently struggling to provide efficient services (Le [START_REF] Boennec | Nouvelles centralités, choix modal et politiques de déplacements: le cas nantais[END_REF]. As for active modes (cycling and walking), they remain strongly dependent on urban planning designed to favor their attractiveness in the eyes of potential users. Moreover, the emergence of the "inclusive mobility" concept may provide mobility for everyone, independently of your age, physical capacity, gender or income (Deloitte 2017). This will not necessarily lead to the development of a new public transport offer. In this context, new offers need an evolution of the institutional context and will have to be taken into account in decision-making models.

At the core of this evolving pattern, single-occupant cars still ensure significant modal shares, including in central cities where the historic or emerging offers should encourage alternative usages. 73% of French people living in rural areas use their cars daily: it is not surprising given the few alternatives available in these sparsely populated areas. Still 54% living in cities with a population of more than 100,000 use their cars daily as well (Chronos/ L'ObSoCo 2016). Indeed, car is convenient in a number of situations (accompanying children, transporting heavy or bulky objects), and it offers shorter travel times than public transport in a non-congested environment. More generally, if not shared, car remains synonymous with autonomy and flexibility: you do not depend on anyone to travel. In return, car usage generates negative effects: it is an additional source of noise, air pollution, greenhouse gas emissions (GHG), congestion, road accidents... (Verhoef 1996). Public actors seek to limit such externalities in order to preserve a quality of life acceptable to residents (Le Boennec and Salladarré 2017).

The need for car and the lack of public finance since 2009 tend to attenuate the classic opposition between private car and public transit. Not surprisingly, the rehabilitation of cars is suitable for road federations (like Union Routière de France, URF 2016); it is a more unexpected position of the International Union of Public Transport [START_REF] Van Audenhove | The Future of Urban Mobility 2.0[END_REF]. Given the cost of implementing or developing public transit in medium to large cities, "car is the public transportation of tomorrow" may become a trendy slogan for public authorities, either as a complement or a substitute to public transit (see for example the Transdev offer of carpooling lines in several medium French cities, or the Chariot on-demand transport offer in the United States).

In this article we seek to assess existing or emerging mobility offers that could induce autosolists (single-occupant car drivers) to adopt sustainable mobility offers: public transport, active modes, and individual shared mobility: carpooling, car-sharing, private-hire, on-demand transport. We try to understand the features of exclusive singleoccupant car-drivers. On the contrary we analyze the features of the 100% inter or multimodal users. How do these "early adopters" use mobile apps? Are these features transferable to larger groups? From the supply side, we seek to identify an innovative mobility offer (or a set of offers) to be developed on the relevant market, and to draw the conditions of economic durability for this (these) offer(s).

To answer those questions, we use a multicriteria decision analysis (MCDA) to assess a set of mobility offers launched in France, Europe or the US. We implement an original two-step method that we apply to 50 mobility offers. In a first step, we use the diviz decision-aid tool to obtain a global score for every offer, using 18 criteria that cover the three pillars of sustainable development: economics, environment, society. In a second step, we use the MICMAC decision-aid tool to build relationships of influence and dependency between the 18 criteria.

For each type of geographical context, we state what could be a development scenario for the future of mobility. We apply our two-step method to the specific case of the Ile-de-France region, where various types of geographical contexts may be found. We find that walking and carpooling usually constitute under-used mobility offers, and that mobility as a service (mobile apps) presents huge margins of progression in most of the situations.

The paper is organized as follows: in section 2 we focus on the interest of observing new mobility offers. In section 3 the need of geographical contextualization using a typology of territories is examined. A brief overview of the advantages of a multicriteria decision analysis is made in section 4. Our original two-step decision-aid tool is on the scope of section 5. Finally concluding remarks are provided.

The Observatory of New Mobility Solutions of the VEDECOM Institute

The Observatory of New Mobility Solutions that the VEDECOM Institute is developing is a decision-making tool for territorial authorities in order to propose a synthetic and clear presentation of the spatial planning modalities in terms of transport. It supports the development of mobility offers, facilitates animation and dialogue on these issues through the provision of data, statistics, analyzes and indicators. Once these indicators defined, the observatory is populated and maintained by the VEDECOM Institute.

This observatory is oriented on mobility offers in addition to existing observatories focused on users' behavior (eg Cetelem, Transdev or Keolis observatories in France). We propose to identify and analyze the new mobility solutions defined as any offer whose use is shared in time and/or in space. This decision-making tool is targeted on gathering information data related to mobility offers (production of raw data as well as monitoring international best practices), in order to allow the territorial exploitation of these data (treatment and analysis of information on Mobility as a Service, or MaaS offers), to evaluate solutions (indicators and maps) as well as building different scenarios of territorial development in terms of mobility solutions. This observatory is elaborated in a co-construction approach with experts in their field of activity (focus group methodology, Faucheux and Nicolai 2004a). It is composed of a set of indicators evaluating the impacts on a given territory.

The objective of this observatory is to prioritize the mobility solutions on a given territory (see paragraph 5.1. with diviz tool) and, secondly, to identify the variables that will be determinant for this territory in offering new mobility offers (MICMAC methodology application). In this context, we first have to decide what should be a relevant entry for a local authority for such prioritization. We retain the three pillars of sustainable development, as mobility policies are largely assessed on this basis at every level of governance: local, national and European. Then we define a typical user profile, retain a typology of new mobility offers and characterize a typology of territory.

As far as the user profile is concerned, we propose to characterize a user in relation to his behavior with regard to his mobility solution: personal or shared vehicle / individual or collective travel. We highlight two trends in order to justify our choice of this typology, "type of property" and "type of use":

 Socio-economic changes: rising life expectancy, populations with specific mobility needs ("young" retired, disabled, "vulnerable groups"), financial difficulties of households in relation to the weight of transport in the budgets, new consumption practices (freedom, utility, efficiency), the role of public transport, the management of commuting trips that are considered independent from each other...  An evolution of the practices of individual mobility that offer combinations of choices between vehicle and travel: personal car trip/shared car, new consumption criteria (saving time, cross-border loading.

..).

There is no more an average traveler, a typical day.

It is therefore necessary to analyze the needs of travel by taking into account feedback (see the different criteria of decision-making emphasized in Dantan and al 2017), increasingly complex mobility with multi-modality, intermodality, co-mobility, on-demand transport, teleworking... in short, taking account flexible users. Such complexity derived from an evolving user profile is transcribed through several criteria we elaborate for the assessment of the mobility solutions.

For mobility solution profiles, we propose the following typology: mobility avoided (teleworking conditions), assisted mobility and agile mobility which ensures reactivity of solutions. We elaborate categories of mobility offers observing the solutions launched on the market (carpooling, car-sharing, public transport, active modes, private-hire, on-demand transport…). These categories are dynamic: when a new offer is launched, it may question the previous categorization (for example, the OuiHop offer launched in 2015 in the Ile-de-France region yields the creation of the "real-time carpooling" subcategory).

Socio-economic breakdowns appear in the practices of mobility. These changes are accompanying new societal trends: an expansion of the collaborative economy, users' wishes to be associated with the definitions of product or service offerings (a strategic approach on user-centered innovation has to be reinforced), the rising of digital economy and connected objects, new labor organizations, a growing evolution towards a service economy (even if according to observatories of uses, the French people are still very attached to vehicle ownership).

Finally, we note that these new practices are highly dependent of the territories, which are themselves marked by strong inequalities in the provision of mobility services. Urban sprawl, increased multipolarity of territories (with a great diversity of travels), living areas with a wide radiance are as many sources of possible inequalities with regard to the provision of mobility services. This reflection on a necessary typology of the territories concerning the implementation of the mobility services will be addressed in the following paragraph.

The objective of this decision-aid tool is to identify mobility solutions that meet the major expectations of users:

 Simplicity of the mobility solution and guarantee of psychological comfort;  Transparency of information so that experience feedback is as high as possible;  Instant service: the availability of information in real time is a priority for many users;  Door-to-door travel that has to be taken into account in route calculations.

The indicators that constitute the observatory respect main characteristics of a socio-economic dashboard. They were constructed to validate the following characteristics of any indicator (Faucheux and Nicolai, 2004b):

 Measurable: quantifiable (or qualifiable) using available tools and methods, in particular in terms of verifiable data;  Robust: measurable constantly over time and in the same way by different observers in different areas;  Relevant: for a given level of territorial precision, the availability of data in relation to the objective;  Understandable: clear and shared definition of the indicator from an operational point of view;  Sensitive: that needs to add information to decision-making.

We opted for a scorecard with 18 indicators (6 per sustainability pillar), with a comprehensible visualization that can be adapted according to the territory analyzed. The territorial specificities and their consequences in the choice of mobility solutions are the subject of a dedicated analysis which is presented in the following section.

Building a typology of territories

The manner a mobility solution may be deployed on a specific territory depends on its own socio-demographical characteristics. For example a car-sharing solution like Autolib may be efficient in the central city of Paris and the inner suburbs, but not necessarily in low-dense areas. The success of Uber is largely due to the short distances to be traveled that is to say, again, mainly in central cities. Before processing the evaluation, it thus appears to be particularly useful to build a typology of territories of close characteristics so that certain groups of mobility offers may be implemented here and not there, so they have a chance to develop a successful business model. For every criterion guiding the assessment process, the aim is to attribute specific weights for dense and low-dense areas.

To build an adapted typology of territories, we were assisted by five territorial experts: two academic ones (a researcher and an assistant professor in land sciences) and three operational experts in mobility policies working in public authorities (two medium-cities of the Paris conurbation). The result in the Ile-de-France region leads to five different types of territories that are specified regarding three variables: housing densities, employment densities and commuting flows between these two kinds of geographical spaces (Fig. 1). This original approach combines the institutional typology giving the physical frontiers between public authorities, and a morphological analysis built by the institute of land-use and urbanism of the Paris region (IAU IDF). Paris" (see level (2) below). However, the deployment of new offers starts in certain districts of the central city of Paris. As a corollary, even existing offers like taxis continue to be largely used in central cities, given the less distances to be traveled, compared with the rest of the suburb (Population: 2,200,000).  Paris suburb inner area or Métropole du Grand Paris (MGP) or "Greater Paris". In these completely urbanized areas for long, bike or car-sharing networks are implemented to complete a historic mobility system along public transportation lines (Pop. 4,800,000).  The Paris conurbation. In these multipolarized but still urbanized areas, the public transport network remains dense. It allows travel easily to the central city or the inner area. Yet it appears to be difficult, given the larger area to be covered, to find shared mobility services without discontinuity (Pop. 3,700,000).  The central cities of the Paris region outer area. Several small or medium cities are served at least by one major transport network (mostly railway), whereas the rest of the mobility system is organized to switch users towards the train station in a radial manner.  The other communes of the Paris region outer area. In these low-dense areas, it must be noticed a lack of governance of mobility. They may benefit from a service organized by larger mobility authorities and be the subject of local experiments (e.g. car-sharing offer in the Haute Vallée de Chevreuse, South West of Paris). However the implementation of a structured mobility policy remains problematic (Pop. 1,300,000 including the last two categories).

Assessing new mobility offers to assist decision-makers

Every transport or mobility policy need to be assessed because of their costs and irreversible effects on a specific territory. Implementing a policy requires from the decision-maker to trade off between alternative projects on the basis of a number of considerations (International Transport Forum 2011). Will the project achieve its environmental objectives (air quality, GHG emissions, road safety, etc.)? Will it cost too much in relation to the expected benefits? Is it assessed on the right criteria? Is it preferable to another project? Formulated in economic terms, it is a matter of estimating the opportunity cost of a project.

To answer these questions, we mobilize a multicriteria decision analysis (MCDA), so that several criteria may be taken into account simultaneously [START_REF] Munda | Qualitative multicriteria methods for fuzzy evaluation problems: An illustration of economicecological evaluation[END_REF][START_REF] Salling | Sustainable transport project evaluation and decision support: indicators and planning criteria for sustainable development[END_REF], Barbosa et al 2017). Cost-Benefit Analysis (CBA) makes it possible to take a decision in a context where the impacts of a transport project can be monetized [START_REF] Quinet | La pratique de l'analyse coût-bénéfice dans les transports : le cas de la France[END_REF]. However there is a wide range of situations where the monetary value of a criterion may not be easily attributed, broadly speaking, the social or environmental dimensions [START_REF] Joubert | Fynbos (fine bush) vegetation and the supply of water: a comparison of multi-criteria decision analysis and cost-benefit analysis[END_REF][START_REF] Tudela | Comparing the output of cost benefit and multi-criteria analysis: An application to urban transport investments[END_REF]. As a result, as soon as the evaluator refuses to put forward an (even imprecise) quantification of an impact, this impact cannot be taken into account in the assessment. Such an absence risks skewing the selection of the "good" project (International Transport Forum 2011). A multi-criteria decision analysis may thus be preferred by the decision maker (Beria et al. 2012[START_REF] Hüging | Need for a holistic assessment of urban mobility measures-Review of existing methods and design of a simplified approach[END_REF], Bueno et al. 2015). This type of analysis may prove relevant when considering the behavior of users and when favoring a broader approach than the calculation of social costs. A shared view is that a MCDA takes on more impacts into account, responds more directly to the concerns of decision makers and is open to various weighting strategies applied to the assessment criteria (International Transport Forum 2011).

Application: the two-step decision-aid tool for the Paris region

The two-step decision-aid tool

Our methodological strategy pursues two complementary objectives: on the one hand, assessing mobility solutions one by one; on the other hand, developing a hybrid solution according to the type of territory.

The first step of the method is based on the comparison of various mobility offers in order to establish a ranking. For this first step, the diviz software is required [START_REF] Meyer | Diviz: A software for modeling, processing and sharing algorithmic workflows in MCDA[END_REF]Bigaret 2012, Cailloux et al 2013). A typology of new mobility offers is first established (see Section 2). We then retain the most representative offer(s) of each category, namely: first, the offer that regionally benefits from the highest number of users (e.g. BlaBlaCar for carpooling, Uber for private-hire or Google Maps for multimodal information app); and second, if relevant, an offer that presents some differentiation features compared to the leader, so that potential users in territories where the offer is not launched yet could benefit from it (OuiHop for carpooling, G7 taxis using a reservation app or the Finnish project tuup for multimodal information). 50 mobility offers are thus ready to be assessed. (Fig. 2a). The assessment process was based on a list of 18 criteria and measurement indicators (see Section 2). Six criteria are related to economic issues (both demand and supply), six other ones to environmental and health, and the last six to social or societal issues (incentives for use and effective usage, see Appendix A). To ensure the robustness of our proposal, it was planned by bringing the criteria and indicators to the validation of an expert group in mobility solutions: Nine qualified persons were invited in order to discuss the best criteria and indicators. Seven of these nine experts were external to the VEDECOM Institute. For each of the 18 validated indicators, the mobility offer was compared to single-occupant car usage (without definition of length or motive for travel).

The second step of the method consists in the production of mobility scenarios. We seek to build relationships of influence and dependence between our predefined variables (the 18 criteria). These relationships serve to state scenarios, which ultimately condition the design of hybrid mobility solutions. Thus, for each type of territory, a matrix of relationships between all the criteria taken in pairs is developed. The rating system ranges from "(0) no influence/dependence of variable 1 on variable 2 " to "(3) very strong influence/dependence of variable 1 on variable 2 ". A mapping of influential and dependent variables is proposed (example provided in Fig. 2b). The choice of the MICMAC software appears appropriate (Godet 2000, Shoai Tehrani and[START_REF] Shoai Tehrani | Three Investments Scenarios for Future Nuclear Reactors in Europe[END_REF].

The y-axis in Fig. 2b shows an increasing degree of influence of variables as one moves from the bottom to the top of the graph (for example, the variable "Satisfaction"). Conversely, when one moves along the x-axis from left to right, one discovers variables more strongly influenced by the others (for example, the variable "Usage intention"). At the center of the graph is an area where the variables are neither significantly influential nor dependent on others ("Business model" here). Finally, in the northeast quarter of the graph are found the variables whose interactions between them appear significant and crossed. From this mapping, one or two prospective scenarios can be developed, based on variables that exert a strong influence (Shoai Tehrani and Da Costa 2017).

An illustration: the results of the first assessment step for the Ile-de-France region

The results obtained for the 50 mobility offers after the first-step of the method are the following (Fig. 3). The negative scores are the result of the weighting processes possibly giving scores below the average. We consider the sixth level of the typology of territories ("Rural", out of the Paris region) so that the graph is more relevant. We retain the mobility offers with the highest scores before applying territorial weights, in comparison with the reference offer, namely single-occupant car with thermal power. We thus compare two active modes (walking and bike-sharing), two electric modes (one being experimental, the autonomous shuttle in Lyon, France), and one original carpooling offer (the IDVROOM carpooling line in the area of Lyon).

In dense areas, the thermal single-occupant car obtains very low results because of poor environmental results (air quality, noise emission). On the contrary in low-dense areas, the economic demand factors are massive and favor a high score (saved travel times, cars deployed everywhere independently from income). For comparable reasons carpooling offers follow the same pattern. These are good news for the enhancement of sustainable uses of cars.

Walking is the offer that obtains the highest score, every type of territory combined. This surprising result is due to economic factors (walking is costless for users), to the high scores obtained for environmental indicators (GHG emissions, air quality, noise emission, health), and to social or societal benefits (a universal mobility offer, convenient and inspiring security). The increasing tendency while the density decreases is due to the demand factor (economics issues) and the incentives to use (social and societal issues), whose weights increase while building density decreases. The tendency is opposite for the other active mode (Velib, the Paris bike-sharing offer), because of demand factors that obtain moderate scores: the offer is only available in rich dense areas.

We should notice a comparable pattern for autonomous shuttle: for this moment, travel times are still not competitive towards private car in low-dense territories (demand factor). Finally, electric car suffers from the lesser importance of environmental factors in low-dense areas, the other five scores obtained being quite homogeneous.

Concluding remarks

The overall results of our study are threefold:

 Carpooling offers present comparable patterns as single-occupant car use in various types of areas;  Certain active modes, namely walking, should be promoted everywhere by public authorities. For example, the city of Montreal adopted the Charter of the pedestrian in 2006 which follows certain rules for future facilities: guaranteeing short travel times, comfort and security; ensuring easy access to commercial areas, ensuring safety for walking trips...  In low-dense areas, walking should obviously be combined with other transportation modes. This would be enabled by the parallel high scores obtained by multimodal information apps (which are not represented here) that can help to fluid intermodal trips.

The way we processed to the assessment of the 50 mobility offers may be discussed; yet for every offer or group of offers we used reports that were published since 2012. The latter are not so numerous. They largely derived from ministerial sources, the French national institute for statistics and economic studies (INSEE), the French agency for environment and energy management (ADEME), or a few consulting companies (6-T, Chronos). That is to say it would be unlikely for different evaluators to obtain highly contrasted scores. Moreover we verified that our results were weakly dependent on the weighting strategies retained for the different types of territories.

Our two-step process is original. But even the first step of our study is not directly comparable to existing works. For example, ADEME frequently works on the evolving of groups of offers (carpooling, car-sharing, active modes, private-hire), but it does not compare these offers in the perspective of enabling a trade-off by a public authority. Mobility labs such as "La Fabrique des Mobilités" or "Le Lab OuiShare Chronos" are more like think tanks and/or incubators for mobility offers. They also facilitate professional relationships between new incomers and public authorities in an operational perspective.

The final stage of the project is the transformation of the mobility scenarios resulting from the second step of the method (the MICMAC process) into an innovative offer or set of offers. This or these offer(s) are expected to capitalize the strengths and levers of the offers assessed in the first step (the diviz process). A test of concept will ultimately aim at gathering the reactions of potential mobility users, the objective being to launch the offer by backing it to a durable business model.

The Observatory of New Mobility Solutions should be designed in a decision-making outlook for local authorities. Decision-makers should enter fine geographical and socioeconomic features of their territories, select the relevant criteria and apply adequate weights; this in order to assess various mobility offers which could be potentially beneficial for local needs. In the end, experiments could be conducted with voluntarist French urban communities, as far as they are concerned with coherent mobility management on their territory.

Fig. 1

 1 Fig. 1 Typology of territories in the Ile-de-France region  The central city of Paris. Mobility policies should be designed at minimum on the scale of the "GreaterParis" (see level (2) below). However, the deployment of new offers starts in certain districts of the central city of Paris. As a corollary, even existing offers like taxis continue to be largely used in central cities, given the less distances to be traveled, compared with the rest of the suburb (Population: 2,200,000).  Paris suburb inner area or Métropole du Grand Paris (MGP) or "Greater Paris". In these completely urbanized areas for long, bike or car-sharing networks are implemented to complete a historic mobility system along public transportation lines (Pop. 4,800,000).  The Paris conurbation. In these multipolarized but still urbanized areas, the public transport network remains dense. It allows travel easily to the central city or the inner area. Yet it appears to be difficult, given the larger area to be covered, to find shared mobility services without discontinuity(Pop. 3,700,000).  The central cities of the Paris region outer area. Several small or medium cities are served at least by one major transport network (mostly railway), whereas the rest of the mobility system is organized to switch users towards the train station in a radial manner.  The other communes of the Paris region outer area. In these low-dense areas, it must be noticed a lack of governance of mobility. They may benefit from a service organized by larger mobility authorities and be the subject of local experiments (e.g. car-sharing offer in the Haute Vallée de Chevreuse, South West of Paris). However the implementation of a structured mobility policy remains problematic (Pop. 1,300,000 including the last two categories).

  Fig. 2 (a) The diviz process for the assessment of 50 mobility offers (step 1); (b) Graph of direct influences and dependencies among criteria (step 2, example of the MICMAC use in this article)

Fig. 3

 3 Fig. 3 Compared spatial performances of various mobility offers

Acknowledgements

We would like to thank every expert who helped us to build the list of criteria and measurement indicators: Mireille Apel-Muller (IVM), Julie Bulteau (University of Versailles Saint-Quentin-en-Yvelines), Priscilla Chai (CentraleSupelec), Mioara Cristea (Heriot-Watt University), Anne Guillaume (LAB), Annie Jaecker (IFPEN), Yannick Pérez (University of Paris Sud and CentraleSupélec), Julien Pillot (Xerfi), Flore Vallet (SystemX Institute and CentraleSupélec).

We are grateful as well to the experts that helped us to build the typology of territories: Dehlia Copel and Guillaume Vallier (CAVGP/Versailles conurbation), Thierry Feuillet (University of Paris 8), Guilhem Sanmarty (VEDECOM Institute), Emmanuel Veiga (CASQY/Saint-Quentin-en-Yvelines conurbation).


Marin Bougeret

Guillerme Duvillié

Rodolphe Giroudeau

Rémi Watrigant

Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations

Keywords: parameterized complexity, kernel, above guarantee parameterization, AND-cross composition, multidimensional binary vector assignment, wafer-to-wafer integration, locally encoded multidimensional matching

In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called BMVA). An input of this problem is defined by m disjoint sets V 1 , V 2 , . . . , V m , each composed of n binary vectors of size p. An output is a set of n disjoint m-tuples of vectors, where each m-tuple is obtained by picking one vector from each set V i . To each m-tuple we associate a p dimensional vector by applying the bit-wise AND operation on the m vectors of the tuple. The objective is to minimize the total number of zeros in these n vectors. BMVA can be seen as a variant of multidimensional matching where hyperedges are implicitly locally encoded via labels attached to vertices, but was originally introduced in the context of integrated circuit manufacturing.

We provide for this problem FPT algorithms and negative results (ET H-based results, W2-hardness and a kernel lower bound) according to several parameters: the standard parameter k (i.e. the total number of zeros), as well as two parameters above some guaranteed values.

Introduction

Definition of the problem

In this paper, we consider the parameterized version of the MULTIDIMENSIONAL BINARY VECTOR AS-SIGNMENT problem (BMVA). An input of this problem is described by m sets V 1 , V 2 , . . . , V m , each of these sets containing n p-dimensional binary vectors. We note V i = {v i 1 , . . . , v i n } for all i ∈ [m] (i) , and for all j ∈ [n] and r ∈ [p], we denote by v i j [r] ∈ {0, 1} the r th component of v i j . In order to define the output of the problem, we need to introduce the notion of stack. A stack s = (v s 1 , v s 2 , . . . , v s m ) is an m-tuple of vectors such that ∀i ∈ [m], v s i ∈ V i . The output of BMVA is a set S of n stacks such that for all i, j ∈ [m] × [n], v i j belongs to only one stack (in that case, the stacks are said disjoint). An example of an instance together with a solution is depicted in Figure 1.

We are now ready to define the objective function. We define the operator ∧ that, given two pdimensional vectors u and v, computes the vector w =

(u[1] ∧ v[1], u[2] ∧ v[2], . . . , u[p] ∧ v[p]
). We associate to any stack s a unique vector v s = i∈[m] v s i . We define the cost of a binary vector v as the number of zeros in it. More formally, if v is p-dimensional, c(v) = p -r∈[p] v [r]. We extend this definition to a set of stacks S = {s 1 , . . . , s n } as follows: c(S) = j∈[n] c(v sj ). Finally, the objective of BMVA is to obtain a set S of n disjoint stacks while minimizing c(S). In the decision version of the problem, we are given an integer k, and we ask whether there exists a solution S of cost at most k. The problem is thus defined formally as follows:

Problem 1 MULTIDIMENSIONAL BINARY VECTOR ASSIGNMENT (BMVA) Input: m sets of n binary p-dimensional vectors, an integer k Question:

Is there a set S of n disjoint stacks such that c(S) ≤ k ?

In order to avoid heavy notations throughout the paper, we will denote an instance of BMVA only by I[m, n, p, k], the notations of the sets and vectors being implicitly given as previously.

Application and related work

BMVA can be seen as a variant of multidimensional matching where hyperedges are implicitly locally encoded via labels attached to vertices. However, this kind of problem was originally introduced by [START_REF] Reda | Maximizing the functional yield of wafer-to-wafer 3-d integration[END_REF] in the context of semiconductor industry as the "yield maximization problem in wafer-towafer 3-D integration technology". In this context, each vector v i j represents a wafer, which is seen as a string of bad dies (0) and good dies (1). Integrating two wafers corresponds to superimposing the two corresponding strings. In this operation, a position in the merged string is "good" when the two corresponding dies are good, and is "bad" otherwise. The objective of Wafer-to-Wafer Integration is to form n stacks, while maximizing their overall quality, or equivalently, minimizing the number of errors (depending on the objective function). In the following, we will denote by max 1-BMVA the dual version of BMVA where given the same input and ouput, the objective is to maximize npc(S), the total number of ones.

The results obtained so far concerning these problems mainly concern their approximability. It is proved in [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF] that when m = 3, BMVA is NP-hard but admits a 4 3 -approximation. We can also mention [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] which provides a f (m)-approximation for general m, and an APX-hardness for m = 3. The main related article is [START_REF] Bougeret | On the complexity of wafer-to-wafer integration[END_REF] where it is proved that max 1-BMVA has no O(p 1-ǫ ) nor O(m 1-ǫ )-approximation for any ǫ > 0 unless P = NP (even when n = 2), but admits a p c -approximation algorithm for any constant c ∈ N, and is FPT when parameterized by p (which also holds for BMVA). Notice that one of the reductions provided by [START_REF] Bougeret | On the complexity of wafer-to-wafer integration[END_REF] is a parameterpreserving reduction from the CLIQUE problem to max 1-BMVA, immediately proving W1-hardness for max 1-BMVA when parameterized by the objective function. This is why our motivation in this paper is to consider the parameterized complexity of BMVA. As we will see in the next section, we provide an analysis for several parameters related to this problem.

For formal definitions and detailed concepts on Fixed-Parameter Tractability, we refer to the monograph of [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF]. Moreover, in order to define lower bounds on the running time of parameterized algorithms, we will rely on the Exponential Time Hypothesis (ET H) of [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF], stating that 3-SAT cannot be solved in O * (2 o(n) ) where n is the number of variables (O * (.) hides polynomial terms). For more results about lower bounds obtained under ET H, we refer the reader to the survey of [START_REF] Lokshtanov | Lower bounds based on the exponential time hypothesis[END_REF].

Parameterizations

One of the main purposes of Fixed-Parameter Tractability is to obtain efficient algorithms when the considered parameter is small in practice. When dealing with the decision version of an optimization problem, the most natural parameter is perhaps the value of the desired solution (e.g. k for BMVA). Such a parameter is often referred to in the literature as the "standard parameter" of the problem. In some cases, this parameter might not be very interesting, either because it usually takes high values in practice, or because FPT algorithms with respect to this parameterization are trivial to find. When this happens, it is possible to obtain more interesting results by subtracting to the objective function a known lower bound of it. For instance, if one can prove that any solution of a given minimization problem is of cost at least B, then one can ask for a solution of cost B + c and parameterize by c. This idea, called "above guarantee parameterization" was introduced by [START_REF] Mahajan | Parameterizing above or below guaranteed values[END_REF] and first applied to MAX SAT and MAX CUT problems. It then became a fruitful line of research with similar results obtained for many other problems (among others, see [START_REF] Cygan | On multiway cut parameterized above lower bounds[END_REF]; [START_REF] Gutin | The linear arrangement problem parameterized above guaranteed value[END_REF]; [START_REF] Gutin | The multivariate algorithmic revolution and beyond. chapter Constraint Satisfaction Problems Parameterized Above or Below Tight Bounds: A Survey[END_REF]; [START_REF] Mahajan | Parameterizing above or below guaranteed values[END_REF]).

In this paper, we analyze the parameterized complexity of BMVA using three types of parameters. The first one is the standard parameter k: the number of zeros to minimize in the optimization version of the problem. Then, three natural structural parameters: m, the number of sets of the input, n, the number of vectors in each set, and p, the size of each vector. The last two parameters are above guarantee parameters.

As we said previously, we already proved in [START_REF] Bougeret | On the complexity of wafer-to-wafer integration[END_REF] that BMVA is FPT parameterized by p. As we will notice in Lemma 2 that we can obtain p ≤ k after a polynomial pre-processing step, this implies that BMVA is also FPT with its standard parameter. Our idea here is to use this previous inequality in order to obtain smaller parameters. Thus, we define our first above guarantee parameter

ζ p = k -p.
Finally, in order to define our last parameter, we first need to describe the corresponding lower bound B, that will represent the maximum, over all sets of vectors, of the total number of zeros for each set. More formally, we define

B = max i∈[m] c(V i ) where c(V i ) = n j=1 c(v i j ).
Since we perform a bit-wise AND over each m-tuple, it is easily seen that any solution will be of cost at least B. Thus, we define our last parameter ζ B = k -B.

Our results

In the next section, we present some pre-processing rules leading to a kernel of size O(k 2 m), and prove that even when m = 3 we cannot improve it to p O(1) unless NP ⊆ coNP/poly (remember that BMVA is known to be FPT when parameterized by p). Section 3 is mainly focused on results associated with parameter ζ B : we prove that BMVA can be solved in O * (4 ζB log(n) ), while it is W2-hard when parameterized by ζ B only, and cannot be solved in O * (2 o(ζB) log(n) ) nor in O * (2 ζBo(log(n)) ) assuming ET H. In Section 4, we focus on the parameterization by ζ p : we show that when n = 2, the problem can be solved in single exponential time with this parameter, but is not in XP for any fixed n ≥ 3 (unless P = NP). The reduction we use also shows that for fixed n ∈ N, the problem cannot be solved in 2 o(k) (and thus in 2 o(ζB) ) unless ET H fails, which matches the upper bound obtained in Section 3. A summary of our results is depicted in the following table.

Positive results

Negative This article is the complete version of [START_REF] Bougeret | Multidimensional binary vector assignment problem: Standard, structural and above guarantee parameterizations[END_REF] where some proofs were omitted due to space limitations.

First remarks and kernels

Let us start with two simple lemmas allowing us to bound the size of the input. Notice first that it is not always safe to create a 1-stack (i.e. a stack with ones on every component) when possible. Indeed, in instance V 1 = { 111 , 101 , 011 }, V 2 = { 111 , 101 , 110 }, V 3 = { 111 , 011 , 110 }, depicted in Figure 2, no optimal solution creates a 1-stack. However, as we will see in Lemma 1, creating 1-stacks becomes safe if n > k.

v s1 v s2 v s3 c(v s1 ) = 1 c(v s2 ) = 1 c(v s3 ) = 1
Figure 2: Example of BMVA instance such that no optimal solution creates a 1-stack.

Lemma 1. There exists a polynomial algorithm which, given any instance I[m, n, p, k] of BMVA, either detects that I is a negative instance, or outputs an equivalent instance

I ′ [m, n ′ , p, k] such that n ′ ≤ k.
Proof: Let I[m, n, p, k] be an instance of BMVA, and suppose that n > k. Let us write a polynomial preprocessing rule that either detects that I is a no instance, or compute an equivalent instance I ′′ [m, n ′′ , p, k] with n ′′ = n -1. Notice first that there exists at least a 1-vector in every set V i . If not, I is a no instance as any solution would be of cost at least n > k. It is now safe to create a 1-stack, obtaining a remaining instance I ′′ with n ′′ = n -1. Indeed, if I is a yes instance, then there must exist at least one 1-stack in the solution (otherwise the cost would be at least n > k), and thus the remaining instance is also a yes instance. As the converse is trivially true, the rule is safe. Applying it at most nk times finally leads to the desired upper bound.

Lemma 2. There exists a polynomial algorithm which, given any instance I[m, n, p, k] of BMVA, either detects that I is a negative instance, or outputs an equivalent instance

I ′ [m, n, p ′ , k] such that p ′ ≤ k.
Proof: Let I[m, n, p, k] be an instance of the problem, and suppose that there exists r ∈

[p] such that for all (i, j) ∈ [m] × [n] we have v i j [r] = 1.
In other words, the r th component of all vectors of all sets is a 1. In this case, it is clear that all vectors of any set of n stacks obtained from I will also contain a 1 at the r th component. Hence, we can modify I[m, n, p, k] into I ′ [m, n, p ′ , k] with p ′ < p by dropping all such components for all vectors. It is clear that this rule is safe since the cost of any solution remains unchanged, and it can be applied in polynomial time. After applying this rule, for all r ∈ [p ′ ] there exists

(i, j) ∈ [m] × [n] such that v i j [r] = 0.
This immediately implies that the cost of any solution is at least p ′ , and thus if p ′ > k the algorithm detected a no instance.

Given the two previous lemmas, we can suppose from now on that for any instance of BMVA we have n ≤ k and p ≤ k. This immediately implies a polynomial kernel parameterized by k and m.

Theorem 1. BMVA admits a kernel with O(k 2 m) bits.

Let us now turn to the main result of this section. To complement Theorem 1, we show that even when m = 3, we cannot obtain a polynomial kernel with the smaller parameter p under some classical complexity assumptions (notice however that the existence of a polynomial kernel in k only is still open when m is not fixed). Notice also that as BMVA was known to be FPT when parameterized by p, proved in [START_REF] Bougeret | On the complexity of wafer-to-wafer integration[END_REF], it was a natural question to ask for a polynomial kernel.

In order to establish kernel lower bounds, we use the concept of AND-cross-composition of [START_REF] Bodlaender | Kernelization lower bounds by crosscomposition[END_REF], together with the recently proved AND-conjecture of [START_REF] Drucker | New limits to classical and quantum instance compression[END_REF]. In the following, a parameterized problem is a subset of Σ * × N, where Σ * is the set of words over some finite alphabet Σ. Definition 1 (Polynomial equivalence relation according to [START_REF] Bodlaender | Kernelization lower bounds by crosscomposition[END_REF]). An equivalence relation R on Σ * is called a polynomial equivalence relation if the two following conditions hold:

• There is an algorithm that given two strings x, y ∈ Σ * , decides whether x and y belong to the same equivalence class in (|x| + |y|) O(1) time.

• For any finite set S ⊆ Σ * , the equivalence relation R partitions the elements of S into at most

(max x∈S |x|) O(1) classes.
Definition 2 (AND-cross-composition according to [START_REF] Bodlaender | Kernelization lower bounds by crosscomposition[END_REF]). Let L ⊆ Σ * be a set and let Q ⊆ Σ * × N be a parameterized problem. We say that L AND-cross-composes into Q if there is a polynomial equivalence relation R and an algorithm which, given t strings belonging to the same equivalence class of R, computes an instance

(x * , k * ) ∈ Σ * × N in time polynomial in t i=1 |x i | such that: • (x * , k * ) ∈ Q ⇔ x i ∈ L for all i ∈ {1, . . . , t} • k * is bounded by a polynomial in max t i=1 |x i | + log t
Theorem 2 (Drucker ( 2015)). If some set L ⊆ Σ * is NP-hard and L AND-cross-composes into a parameterized problem Q, then there is no polynomial kernel for Q unless NP ⊆ coNP/poly.

Theorem 3. Even for m = 3, BMVA parameterized by p does not admit a polynomial kernel unless NP ⊆ coNP/poly.

Proof:

The proof is an AND-cross-composition inspired by the NP-hardness reduction for BMVA provided by [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF]. More precisely, we cross-compose from a sequence of instances of 3-DIMENSIONAL PERFECT MATCHING. According to Definition 2 and Theorem 2, this will imply the desired result. 3-DIMENSIONAL PERFECT MATCHING is formally defined as follows:

Problem 2 3-Dimensional Perfect Matching

Input:

Three sets X, Y and Z of size n, a set of hyperedges S ⊆ X × Y × Z Question: Does there exist a subset S ′ ⊆ S such that:

• for all e, e ′ ∈ S ′ with e = (x, y, z) and e ′ = (x ′ , y ′ , z ′ ), we have x = x ′ , y = y ′ and z = z ′ (that is, S ′ is a matching)

• |S ′ | = n (that is, S ′ is perfect) Let (X 1 , Y 1 , Z 1 , S 1 ), . . . , (X t , Y t , Z t , S t
) be a sequence of t equivalent instances of 3-DPM, with respect to the following polynomial equivalence relation: (X, Y, Z, S) and

(X ′ , Y ′ , Z ′ , S ′ ) are equivalent if |X| = |X ′ | (and thus |Y | = |Y ′ | = |Z| = |Z ′ | = |X|), and |S| = |S ′ |.
In the following we denote by n the cardinality of the sets X i (and equivalently the sets Y i and Z i ), and by m the cardinality of the sets S i . Moreover, for all i ∈ {1, . . . , t} we define X i = {x i,1 , . . . , x i,n }, Y i = {y i,1 , . . . , y i,n }, Z i = {z i,1 , . . . , z i,n }, and S i = {s i,1 , . . . , s i,m }. We also assume that t = 2 q for some q ∈ N (if it is not the case, we add a sufficiently number of dummy yes-instances).

In the following we construct three sets (X * , Y * , Z * ) of nt vectors each: X * = {x * i,j } j=1,...,n i=1,...,t , Y * = {y * i,j } j=1,...,n i=1,...,t and Z * = {z * i,j } j=1,...,n i=1,...,t , where each vector is composed of p * = m + 2mq components. Let us first describe the first m components of each vector. For all i ∈ {1, . . . , t}, j ∈ {1, . . . , n} and k ∈ {1, . . . , m} we set:

x * i,j [k] = 1 if the hyperedge s i,k contains x i,j 0 otherwise y * i,j [k] = 1 if the hyperedge s i,k contains y i,j 0 otherwise z * i,j [k] = 1 if the hyperedge s i,k contains z i,j 0 otherwise
Then, for all i ∈ {1, . . . , t}, we append two vectors b i and bi to all vectors {x * i,j } j=1,...,n , {y * i,j } j=1,...,n and {z * i,j } j=1,...,n . The vector b i is composed of mq coordinates, and is defined as the binary representation of the integer i, where each bit is duplicated m times. Finally, bi is obtained by taking the complement of b i (i.e. replacing all zeros by ones, and conversely) as depicted in Figure 3. It is now clear that each vector x * i,j (resp. y * i,j , z * i,j ) is composed of p * = m + 2mq coordinates. Thus, the parameter of the input instance is a polynomial in n, m and log t whereas the total size of the instance is a polynomial in the size of the sequence of inputs, as required in cross-compositions. It now remains to prove that (X * , Y * , Z * ) contains an assignment of cost k * = nt(mq + m -1) if and only if for all i ∈ {1, . . . , t}, S i contains a perfect matching S ′ i .

• Suppose that for all i ∈ {1, . . . , t} we have a perfect matching S ′ i ⊆ S i . W.l.o.g. suppose that S ′ i = {s i,1 , . . . , s i,n }. Then, for each j ∈ {1, . . . , n}, we have s i,j = (x i,j1 , y i,j2 , z i,j3 ) for some j 1 , j 2 , j 3 ∈ {1, . . . , n}. We assign x * i,j1 with y * i,j2 and z * i,j3 . It is easy to see that the cost of this triple is m -1 + mq. Indeed, they all have a one at the j th coordinate, corresponding to the j th hyperedge of S i (and this is the only shared one, since we can suppose that all hyperedges are pairwise distinct), and they all contain the same vectors b i and bi . Summing up for all instances, we get the desired solution value.

• Conversely, first remark that in any assignment, the cost of every triple

(x * i1,j1 , y * i2,j2 , z * i3,j3
) is at least m -1 + mq, and let us prove that this bound is tight when (1) all elements are chosen within the same instance, i.e. i 1 = i 2 = i 3 = i, and (2) this triple corresponds to an element of S i , i.e. (x i,j1 , y i,j2 , z i,j3 ) ∈ S i . Indeed, suppose first that i 1 = i 2 . Then, since the binary representation of i 1 and i 2 differs on at least one bit, it is clear that the resulting vector is of cost at least m(q + 1) > mq + m -1. Now if i 1 = i 2 = i 3 = i, then the result is straightforward, since at most one hyperedge of S i can contain x * i1,j1 , y * i2,j2 and z * i3,j3 . Finally, using the same arguments as previously, we can easily deduce a perfect matching S ′ i ⊆ S i for each i ∈ {1, . . . , t}, and the result follows.

Parameterizing according to ζ B

In this section, we present an FPT algorithm when parameterized by ζ B and n (recall that both ζ B and n are smaller parameters than the standard one k, since k = B + ζ B and n ≤ k in any reduced instance). Notice first that it is easy to get an O * (2 ζB(log(n)+log(p)) ) algorithm. Indeed, by considering a set i ∈ [m] where c(V i ) = B, and guessing the positions of the ζ B new zeros (among np possible positions) that will appear in an optimal solution, we can actually guess in O * ((np) ζB ) the vectors {v s * j } of an optimal solution, and it remains to check in polynomial time that every V j can be "matched" to {v s * j }. Now we show how to get rid of the log(p) term in the exponent. ,3), (x1,1, y1,2, z1,2), (x1,2, y1,3, z1,3), (x1,3, y1,3, z1,3)}), (X2, Y2, Z2, {(x2,1, y2,1, z2,1), (x2,2, y2,2, z2,2), (x2,3, y2,3, z2,3), (x2,3, y2,2, z2,1)}), (X3, Y3, Z3, {(x3,1, y3,1, z3,1), (x3,2, y3,1, z3,1), (x3,3, y3,2, z3,2), (x3,3, y3,3, z3,3)}), (X4, Y4, Z4, {(x4,1, y4,2, z4,2), (x4,2, y4,1, z4,1), (x4,2, y4,2, z4,2), (x4,3, y4,3, z4,3)}) into an instance of bMVA with m = 3, n = 12 and p = 20.

Theorem 4. BMVA can be solved in O * (4 ζB log(n) ). x1,1 x1,2 x1,3 y1,1 y1,2 y1,3 z1,1 z1,2 z1,3 X1 Y1 Z1 x2,1 x2,2 x2,3 y2,1 y2,2 y2,3 z2,1 z2,2 z2,3 X2 Y2 Z2 x3,1 x3,2 x3,3 y3,1 y3,2 y3,3 z3,1 z3,2 z3,3 X3 Y3 Z3 x4,1 x4
Proof: Let I[m, n, p, k] be an instance of our problem and, w.l.o.g., suppose that V 1 is a set whose number of zeros reaches the upper bound B, i.e. c(V 1 ) = B. The algorithm consists in constructing a solution by finding an optimal assignment between V 1 and V 2 , . . . , V m , successively.

We first claim that we can decide in polynomial time whether there is an assignment between V 1 and V 2 which does not create any additional zero.

To that end, we create a bipartite graph G with bipartization (A, B), A = {a 1 , . . . , a n }, B = {b 1 , . . . , b n }, and link a j1 and b j2 for all (j 1 , j 2 )

∈ [n] × [n] iff assigning vector v 1 j1 from V 1 and vector v 2 j2 from V 2 does not create any additional zero in V 1 (v 1 j1 ∧ v 2 j2 = v 1 j1
). If a perfect maching can be found in G, then we can safely delete the set V 2 and continue. In order to avoid heavy notations, we consider this first step as a polynomial pre-processing, and we re-label V i into V i-1 for all i ∈ {3, . . . , m} (and m is implicitly decreased by one).

In the following, we suppose that the previous pre-processing step cannot apply (i.e. there is no perfect matching in G). Intuitively, in this case any assignment (including an optimal one) between V 1 and V 2 must lead to at least one additional zero in V 1 . In this case, we perform a branching to guess one couple of vectors from V 1 × V 2 which will induce such an additional zero. More formally, we branch on every couple (j 1 , j 2 ) ∈ [n] × [n], and create a new instance as a copy of I in which v 1 j1 is replaced by v 1 j1 ∧ v 2 j2 . This operation increases c(V 1 ) by at least one, and thus B by at least one as well. If we denote by I ′ this new instance, we can check that a solution of cost at most k for I ′ will immediately imply a solution of cost at most k for I, as I ′ is constructed from I by adding some zeros. The converse is also true as one assignment we enumerate corresponds to one from an optimal solution.

As the value of B in this branching increases by at least one while we still look for a solution of cost k, this implies that this branching will be applied at most ζ B times. Summing up, we have one polynomial pre-processing and one branching of size n 2 which will be applied at most ζ B times. The total running time of this algorithm is thus bounded by O * (4 ζB log(n) ).

Despite its simplicity, we now show that, when considering each parameter (n and ζ B ) separately, this algorithm is the best we can hope for (whereas the existence of an O * (2 k ) algorithm is still open). Indeed, we first show in Theorem 6 that the linear dependence in ζ B and log(n) in the exponent is necessary (unless ETH fails), and also that we cannot hope for an FPT algorithm parameterized by ζ B only unless FPT = W2 (Theorem 5). Finally, as we will see in the next section (Theorem 8), this result is matched by a 2 o(ζB) lower bound when n ∈ N is fixed. We now present a reduction from the HITTING SET problem which produces an instance of BMVA.

Problem 3 Hitting Set

Input:

m subsets R 1 , ..., R m of [n]
, and an integer k

Question: Is there a set R of k elements of [n] such that R ∩ R i = ∅ for any i ∈ [m]?
Lemma 3. There is a polynomial reduction from HITTING SET to BMVA that given an instance composed of m subsets of [n] and an integer k, constructs an instance of BMVA I[m ′ , n ′ , p ′ , k ′ ] such that n ′ = n and ζ B = k.

Proof: Let R 1 , ..., R m be subsets of [n], and k ∈ N. We construct m sets V 1 , ..., V m of n vectors each, where, for all i ∈ [m] we have V i = {v i 1 , ..., v i n }, each vector being composed of n components. For all i ∈ [m] and all j ∈ [n], if j ∈ R i , then the vector v i j is composed of ones everywhere except at the j th component. If j / ∈ R i , then v i j is a 0-vector (i.e. a vector with zero in every component). We also add a set V * composed of (n -1) 0-vectors and one 1-vector as depicted in Figure 4.

V 1 V 2 V 3 V 4 V 5
For this constructed instance, it is clear that B = n(n -1) because of the set V * . In other words, any assignment will lead to a solution with (n -1) 0-vectors, and thus with at least n(n -1) zeros. We will actually show that this instance has a solution with n(n -1) + k zeros if and only if R 1 , ..., R m has a hitting set of size k. By the foregoing, we only need to focus on the only vector of each set which is assigned to the 1-vector of V * . ⇒ Let J ⊆ [n] be a hitting set of size k. By the definition of a hitting set, for all i ∈ [m], there exists j i ∈ J ∩ R i . Thus, for all i ∈ [m], we select the vector v i ji from the set V i to be assigned to the 1vector of V * . By construction, this vector has only one zero at the j th i component, which implies that the conjunction of all such vectors m i=1 v j ji will have a 1 everywhere except at the components corresponding to J. We thus have the desired number of zeros in our solution. ⇐ Conversely, for each i ∈ [m], let j i ∈ [n] be the vector from V i which is assigned to the 1-vector of V * . Since the resulting conjunction of all these vectors has only k zeros, v i ji cannot be a 0-vector, and we thus have j i ∈ R i . Using the same arguments as previously, {u ji } i∈[m] corresponds to a hitting set of R 1 , ..., R m of size k. As we seen previously, B = n(n -1) for the obtained instance, k ′ = n(n -1) + k, (which implies ζ B = k), and the size of all sets is n, as desired.

As we can see, the reduction is parameter-preserving for ζ B . From the W2-hardness of HITTING SET provided by [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF], we have the following:

Theorem 5. BMVA is W2-hard when parameterized by ζ B .
As said previously, we also use this reduction to show the following result:

Theorem 6. BMVA cannot be solved in O * (2 o(ζB) log(n) ) nor O * (2 ζBo(log(n)) ), unless ETH fails.
Proof: To show this, we use a the previous hardness result, but using a constrained version of the HITTING SET problem obtained by [START_REF] Lokshtanov | Slightly superexponential parameterized problems[END_REF], where the element set is [k] × [k] and can thus be seen as a table with k rows and k columns:

Problem 4 k × k Hitting Set Input: An integer k, and R 1 , ..., R t ⊆ [k] × [k]
Question:

Is there a set R containing exactly one element from each row such that R ∩ R i = ∅ for any i ∈ [t]? [START_REF] Lokshtanov | Slightly superexponential parameterized problems[END_REF] show that assuming ET H this problem cannot be solved in 2 o(k log(k)) n O(1) (whereas a simple brute force solves it in O * (2 k log(k) )). Notice that we can modify the question of this problem by dropping the constraint that S contains at least one element from each row. Indeed, let us add to the instance a set of k sets {R ′ 1 , . . . , R ′ k }, where R ′ i contains all elements of row i for i ∈ [k]. Now, finding a (classical) hitting set of size k on this modified instance is equivalent to finding a solution of size k for the original instance of k × k-HITTING SET. Moreover, it is easy to check that a 2 o(k log(k)) n O(1) algorithm for this relaxed problem would also contradict ET H. To summarize, we know that unless ET H fails, there is no 2 o(k log(k)) n O(1) algorithm for the classical HITTING SET problem, even when the ground set has size k 2 . This allows us to perform the reduction of Lemma 3 on these special instances, leading to an instance

I[m ′ , n ′ , p ′ , k ′ ] with associated parameter ζ B such that ζ B = k and n ′ = k 2 .
Suppose now that there exists an algorithm for BMVA running in 2 o(ζB) log(n) (k + m + n + p) O(1) . Using the reduction above, we would be able to solve the instance of k × k-HITTING SET in 2 o(k) log(k 2 ) n O(1) , and thus in 2 o(k log(k)) n O(1) , which would violate ET H. A similar idea also rules out any algorithm running in 2 ζBo(log(n)) under ET H.

Parameterizing according to ζ p

We now consider the problem parameterized by ζ p = kp (recall that p ≤ k). Notice that one motivation of this parameterization is the previous reduction of Lemma 3 from HITTING SET. Indeed, when applied for n = 2, it reduces an instance of VERTEX COVER to an instance of BMVA with k = p + ζ p where ζ p is equal to the size of the vertex cover. Our intuition is confirmed by the following result: we show that when parameterized by ζ p , the problem is indeed FPT when n = 2 (Theorem 7). We complement this by showing that for any n ≥ 3, it becomes NP-hard when ζ p = 0 (Theorem 8), and is thus even not in XP. The reduction we use even proves that for any fixed n ≥ 3, the problem cannot be solved in 2 o(k) (and thus in 2 o(ζB) ) unless ET H fails, while the algorithm of Theorem 4 runs in O * (2 O(ζB) ). In the following, n-BMVA denotes the problem BMVA where the size of all sets is fixed to some constant n ∈ N.

Positive result for n = 2

In this subsection, we prove that 2-BMVA is FPT parameterized by ζ p . To do so, we reduce to the ODD CYCLE TRANSVERSAL problem (OCT for short). In this problem, given a graph G = (V, E) and an integer c ∈ N, the objective is to decide whether there exists a partition (X, S 1 , S 2 ) of V with |X| ≤ c such that S 1 and S 2 are independent sets.

We first introduce a generalized version of OCT, called BIP-OCT. In this problem, we are given a set of vertices V , an integer c, and a set of m pairs (A 1 , B 1 ), ..., (A m , B m ) with A i , B i ⊆ V for all i ∈ [m] and A i ∩ B i = ∅. Informally, each pair (A i , B i ) can be seen as a complete bipartite subgraph. The output of BIP-OCT is described by a partition (X, S 1 , S 2 ) of V such that for any i ∈ [m], either (A i \ X ⊆ S 1 and

B i \ X ⊆ S 2 ) or (A i \ X ⊆ S 2 and B i \ X ⊆ S 1
). The question is whether there exists such a partition with |X| ≤ c. As we can see, if all A i and B i are singletons (and thus form edges), then BIP-OCT corresponds to OCT. Notice that in the following, the considered parameter of OCT and BIP-OCT will always be the standard parameter, i.e. c. We first show that there is a linear parameter-preserving reduction from 2-BMVA parameterized by ζ p to BIP-OCT, and then that there is also a linear parameter-preserving transformation from BIP-OCT to OCT. 1 has been added to s 1 and v i 2 has been added to s 2 . Let r ∈ A i \ X. Since r ∈ A i , we have v i 1 [r] = 0, and thus v s1 [r] = 0. Since r / ∈ X, we have v s2 [r] = 1. Thus, r ∈ S 1 , which proves A i \ X ⊆ S 1 . Similarly, we can prove that B i \ X ⊆ S 2 . ⇐ Let (X, S 1 , S 2 ) be a solution of I ′ with |X| ≤ ζ p . Let s 1 be such that v s1 [r] = 0 iff r ∈ X or r ∈ S 1 , and let s 2 be such that v s2 [r] = 0 iff r ∈ X or r ∈ S 2 . It remains to prove that the solution S = {s 1 , s 2 } is feasible, which immediately implies that its cost is p + ζ p . Let i ∈ [m]. Without loss of generality, let us suppose that A i \ X ⊆ S 1 and B i \ X ⊆ S 2 . We now claim that v i 1 can be assigned to s 1 and v i 2 can be assigned to s 2 without creating any new zero. To do so, let us show that for all r ∈ [p], we have v

i 1 [r] = 0 =⇒ v s1 [p] = 0 (resp. v i 2 [r] = 0 =⇒ v s2 [p] = 0). Indeed, let r ∈ [p] such that v i 1 [r] = 0.
Then by construction, it means that r ∈ A i . Thus, by definition of the solution (X, S 1 , S 2 ), it means that either r ∈ X or r ∈ S 1 , which implies v s1 [r] = 0 as desired. Similar arguments show that

v i 2 [r] = 0 =⇒ v s2 [p] = 0 for all r ∈ [p].
Lemma 5. There is a linear parameterized reduction from BIP-OCT to OCT.

Proof: Let I = (V, {A i , B i } i∈[m] , c) be an instance of BIP-OCT. Let us construct a graph G ′ = (V ′ , E ′ )
which contains an odd cycle transversal of size c if and only if I has a solution of size c for BIP-OCT.

Observe first that we cannot simply set V ′ = V and E ′ = i∈[m],a∈Ai,b∈Bi {a, b}. Indeed, if for example A 1 = {2, . . . , n}, B 1 = {1}, A 2 = {2, . . . , n 2 } and B 2 = { n 2 + 1, . . . , n}, defining G ′ as above would lead to an odd cycle transversal of size one, as removing only vertex {1} makes the graph bipartite with bipartization (A 2 , B 2 ). However, this solution is not feasible for BIP-OCT as A 1 \X = A 1 , and and A 1 ⊆ B 2 . Intuitively, we have to prevent solutions of G ′ from splitting sets A i \ X (and B i \ X) between the two parts of the bipartization. To do so, we will construct G ′ as described above, and then we "augment" each bipartite graph by adding c + 1 new vertices on each side. More formally, we start by setting V ′ = V as said before, and for all i ∈ [m], we create two sets of c + 1 new vertices

A 1 ⊆ A 2 011101111 110110111 110101110 001111011 111111000 111010111 001001000 110100110 V 1 V 2 V 3 S 4 6 3 5 1 2 7 8 9 A 1 B 1 A 2 B 2 A 3 B 3
A ′ i , B ′ i . We then set E ′ = i∈[m],a∈Ai∪A ′ i ,b∈Bi∪B ′ i {a, b}.
Let us now prove that I contains a solution of size c for BIP-OCT if and only if G ′ contains an odd cycle transversal of size c. ⇒ Let (X, S 1 , S 2 ) be an optimal solution of I. We define a partial solution X ′ , S ′ 1 , S ′ 2 of G ′ by setting X ′ = X and S ′ l = S l for l ∈ {1, 2} (the solution is partial in the sense that it remains to assign vertices of

A ′ i ∪ B ′ i , for all i ∈ [m]). Let i ∈ [m]. If A i \ X = ∅ and B i \ X = ∅, then we add (arbitrarily) A ′ i to S ′ 1 and B ′ i to S ′ 2 . Otherwise, if A i \ X = ∅ and is added to S l , we add A ′ i to S ′ l and B ′ i to S ′ l ′
with l, l ′ ∈ {1, 2}, l ′ = l, and if B i \ X = ∅ and is added to S l , we add

B ′ i to S ′ l and A ′ i to S ′ l ′ with l, l ′ ∈ {1, 2}, l ′ = l.
This new solution has the same size (|X ′ | = |X|) and we claim that it is an odd cycle transversal of G ′ . Indeed, let us check that any edge {u, v} ∈ E ′ such that {u, v} ∩ X ′ = ∅ is not entirely contained in a S ′ l . If {u, v} is an edge of a complete bipartite of I, i.e. if there exists i such that u ∈ A i and v ∈ B i , then by definition of the solution (X, S 1 , S 2 ) it is straightforward that u and v are not both in S ′ 1 nor in S ′ 2 . Otherwise, if {u, v} is adjacent to one or two of the new vertices, let i be such that u ∈ A ′ i . If v ∈ B ′ i , then the solution is valid as A ′ i and B ′ i are never added to the same set S ′ l , l ∈ {1, 2}. Otherwise, we necessarily have v ∈ B i . Let l ∈ {1, 2} be such that B i \ X (which is not empty) has been added to S ′ l . In this case A i (and thus u) has been added to

S ′ l ′ , with l ′ = l. ⇐ Let (X ′ , S ′ 1 , S ′ 2 ) be an optimal solution of G ′ . For any i ∈ [m], let Ãi = (A i ∪ A ′ i ) \ X ′ and Bi = (B i ∪ B ′ i ) \ X ′ . A first observation is that Ãi = ∅ and Bi = ∅ as |A i ∪ A ′ i | = |B i ∪ B ′ i | > c and |X ′ | ≤ c.
A second observation is that for any u and v ∈ Ãi , u and v are in the same set S ′ l for some l ∈ {1, 2}. Indeed, suppose by contradiction that u ∈ S ′ 1 and v ∈ S ′ 2 . As Bi = ∅, there exists b ∈ Bi and l ∈ {1, 2} such that b ∈ S ′ l . As all the edges of the complete bipartite subgraph on

(A i ∪ A ′ i , B i ∪ B ′ i )
belong to E ′ , we have {u, b} ∈ E ′ and {v, b} ∈ E ′ , and thus S ′ l contains both endpoints of an edge of E ′ , which is a contradiction. In the same way, we can prove that for any i ∈ [m], and any u and v ∈ Bi , u and v are in the same set S ′ l for some l ∈ {1, 2}. Thus, according to the two previous observations, for any i ∈ [m] we can define λ Ãi ∈ {1, 2} and

λ Bi ∈ {1, 2} such that Ãi ⊆ S ′ λ Ãi and Bi ⊆ S ′ λ Bi , with λ Ãi = λ Bi . Let us now define X = X ′ ∩ V , S 1 = S ′ 1 ∩ V , and S 2 = S ′ 2 ∩ V , and check that this is a valid solution of I. Let i ∈ [m]. Observe first that A i \ X ⊆ Ãi , and thus either A i \ X = ∅, or A i \ X ⊆ S λ Ãi
. As the same fact also holds for B i \ X, and as λ Ãi = λ Bi , the constraint (A i \ X ⊆ S 1 and B i \ X ⊆ S 2 ) or (A i \ X ⊆ S 2 and B i \ X ⊆ S 1 ) is respected, and the solution is feasible, which concludes the proof.

As ODD CYCLE TRANSVERSAL can be solved in O * (2.3146 c ), proved by [START_REF] Lokshtanov | Faster parameterized algorithms using linear programming[END_REF], and since our parameters are exactly preserved in our two reductions, we obtain the following result:

Theorem 7. 2-BMVA can be solved in O * (d ζp ) where d ≤ 2.3146 is such that OCT can be solved in O * (d c ).

Negative results for n ≥ 3

We now complement the previous result by proving that the problem is intractable with respect to the parameter ζ p for larger values of n.

Theorem 8. For any fixed n ≥ 3, n-BMVA is not in XP when parameterized by ζ p (unless P = NP), and cannot be solved in 2 o(k) (unless ET H fails).

Proof: Let χ ≥ 3. We present a reduction from χ-COLORING. Given a graph G = (V, E), this problem consists to ask for a mapping f : V -→ [χ] such that for all {u, v} ∈ E we have f (u) = f (v). • for all j ∈ {3, . . . , χ}, v i j is a 1-vector, i.e. it has a 1 at every component. An example of this construcion is depicted in Figure 6. Let us now prove that G admits a χ-coloring iff I has a solution of cost p = n G . ⇒ Let S j ⊆ V , j ∈ [χ] be the χ color classes (notice that the S j are pairwise disjoint, some of them may be empty, and j∈[χ] S j = V ). To each S j we associate a stack s j such that v sj [r] = 0 iff r ∈ S j . It remains to prove that the solution S = {s 1 , . . . , s χ } is feasible, as its cost is exactly p by construction. Let us consider a set V i where v i 1 (resp. v i 2 ) represents a vertex u (resp. v). As {u, v} is an edge of G, we know that u and v have two different colors, i.e. that u ∈ S j and v ∈ S j ′ , for some j, j ′ ∈ [χ] with j = j ′ . Thus, we can add v i 1 to stack s j , v i 2 to stack s j ′ , and the χ -2 other v i j (j ≥ 3) in an arbitrary way. Since the only 0 in v i 1 (resp. v i 2 ) is at the u th (resp. v th ) component, we have v i 1 ∧ v sj = v sj (resp. v i 2 ∧ v s j ′ = v s j ′ ), which proves that S is feasible. ⇐ Let S = {s 1 , . . . , s χ } be the stacks of an optimal solution. For j ∈ [χ], let S j = {r ∈ [p]|v sj [r] = 0}. Notice that χ j=1 S j = V , and as I is of cost p, all the S j are pairwise disjoints and form a partition of V . Moreover, as for any i ∈ [m], v i 1 and v i 2 have been assigned to different stacks, the corresponding vertices have been assigned to different colors, and thus each S j induces an independent set, which completes the reduction.

V 1,2 V 1,3 V 1,4 V 2,3 V 3,4 V 2,5 V 4,5 S
It is known, thanks to [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] that there is no 2 o(|V |) algorithm for deciding whether a graph G = (V, E) admits a χ-COLORING, for any χ ≥ 3 (under ET H). As we can see, the value of the optimal solution for n-BMVA in the previous reduction equals the number of vertices in the instance of χ-COLORING, which proves that n-BMVA cannot be solved in 2 o(k) for any n ≥ 3.

Finally, remark that as for the parameterization by p, one could ask if BMVA is FPT when parameterized by the first lower bound B. However, we can see in the previous reduction that we obtain a graph with B = 2, and thus the problem is even not in XP unless P = NP.

Conclusion

In this article, we presented some negative and positive results for a multidimensional binary vector assignment problem in the framework of parameterized complexity. Notice that neither lower bounds of Theorem 6 nor Theorem 8 are able to rule out an algorithm running in O * (2 k ) (when n is part of the input), hence the existence of such an algorithm seems a challenging open problem. Another interesting question concerns the improvement of the O(k 2 m) kernel of Theorem 1 by getting rid of the parameter m: does BMVA admit a polynomial kernel when parameterized by k only?

Figure 1 :

 1 Figure 1: Example of BMVA instance with m = 3, n = 4, p = 6 and of a feasible solution S of cost c(S) = 17.

Figure 3 :

 3 Figure 3: Example of Cross Composition construction from four equivalent instances of 3-Dimensional PerfectMatching (X1, Y1, Z1, {(x1,1, y1,1, z1,3), (x1,1, y1,2, z1,2), (x1,2, y1,3, z1,3), (x1,3, y1,3, z1,3)}), (X2, Y2, Z2, {(x2,1, y2,1, z2,1), (x2,2, y2,2, z2,2), (x2,3, y2,3, z2,3), (x2,3, y2,2, z2,1)}), (X3, Y3, Z3, {(x3,1, y3,1, z3,1), (x3,2, y3,1, z3,1), (x3,3, y3,2, z3,2), (x3,3, y3,3, z3,3)}), (X4, Y4, Z4, {(x4,1, y4,2, z4,2), (x4,2, y4,1, z4,1), (x4,2, y4,2, z4,2), (x4,3, y4,3, z4,3)}) into an instance of bMVA with m = 3, n = 12 and p = 20.

Figure 4 :

 4 Figure 4: Example of reduction from an instance of Hitting Set consisting of four subsets of [n = 7] : R1 = {1, 2, 7} , R2 = {1, 3, 4, 5} , R3 = {2, 4, 5} , R4 = {5, 6, 7}, and an integer k = 2, to an instance of BMVA with m ′ = 5, n ′ = n, p = n.

Lemma 4 .

 4 There is a linear parameter-preserving reduction from 2-BMVA parameterized by ζ p to BIP-OCT. Proof: Let I[m, 2, p, p + ζ p ] be an instance of 2-BMVA (i.e. in which every set contains only two vectors), and let us construct an instance I ′ of BIP-OCT, such that I has a solution of cost p + ζ p iff I ′ has a solution of size ζ p . Notice first that we can suppose that for any i ∈ [m] and any r ∈ [p], we cannot have both v i 1 [r] = 0 and v i 2 [r] = 0 as otherwise any stack s from any solution would have v s [r] = 0, and thus we could safely remove such a component r from the instance (and decrease k and p by one). Let the vertex set of I ′ be [p]. Then, for all i ∈ [m], let us define A i = {r|v i 1 [r] = 0}, and B i = {r|v i 2 [r] = 0} as depicted in Figure 5. By the foregoing, and as required in an instance of bip-OCT, we have A i ∩ B i = ∅. Let us prove that I has a solution of cost p+ ζ p iff I ′ has a solution (X, S 1 , S 2 ) with |X| ≤ ζ p . ⇒ Let S = {s 1 , s 2 } be a solution of I of cost p + ζ p . Let X = {r|v s1 [r] = v s2 [r] = 0}, S 1 = {r|v s1 [r] = 0 and v s2 [r] = 1}, and S 2 = {r|v s1 [r] = 1 and v s2 [r] = 0}. Notice that (X, S 1 , S 2) forms a partition of [p] (as we cannot have a r 0 with v s1 [r 0 ] = v s2 [r 0 ] = 1, as this would imply that all the nm vectors have v[r 0 ] = 1, and such cooordinates have been removed from the instance in Lemma 2), and |X| = ζ p . It remains to prove that (X, S 1 , S 2 ) is a feasible solution of I ′ . Let i ∈ [m]. Without loss of generality, let us suppose that v i

Figure 5 :

 5 Figure 5: Example of reduction from an instance of 2-BMVA, with n = 2, m = 3, p = 9, admitting a solution of cost p + 2, to an instance of BIP-OCT, with |V | = p, A1 = {3, 6} , B1 = {1, 5} , A2 = {2, 3, 7} , B2 = {3, 5, 9} , A3 = {4, 6} , B3 = {7, 8, 9}, admitting the partition ({5, 9} , {3, 4, 6} , {1, 2, 7, 8}) as solution of cost 2.

  Let E = {e 1 , ..., e mG } and V = [n G ]. Let us construct an instance I of n-BMVA with n = χ, p = n G , m = m G and such that G admits a χ-coloring iff I has a solution of cost p (i.e. ζ p = 0). To each edge e i = {u, v} ∈ E, i ∈ [m G ], we associate a set V i with |V i | = χ, where:• v i 1 represents the vertex u, that is v i 1 [u] = 0 and v i 1 [r] = 1 for any r ∈ [n G ], r = u, • v i 2 represents the vertex v, that is v i 2 [v] = 0 and v i 2 [r] = 1 for any r ∈ [n G ], r = v,

Figure 6 :

 6 Figure 6: Example of reduction from a positive instance of χ-COLORING, with χ = 3, V = [5], E = {{1, 2} , {1, 3} , {1, 4} , {2, 3} , {3, 4} , {2, 5} , {4, 5}}, to an instance of BMVA with m = |E| = 6, n = χ = 3, p = |V | = 5 admitting a solution of cost p.