Xuan Wu
email: xuan.wu@ensam.eu

Virginie Goepp
email: virginie.goepp@insa-strasbourg.fr

Ali Siadat
email: ali.siadat@ensam.eu

A method for supporting the transformation of an existing production system with its integrated Enterprise Information Systems (EISs) into a Cyber Physical Production System (CPPS)

Cyber-Physical Systems (CPSs) combine the use of components from the physical and the digital worlds in a synergistic way. Cyber-Physical Production Systems (CPPSs), essential in Industry 4.0, result from the application of CPS principles to production environments. To promote the widespread implementation of CPPSs, it is necessary to study how to transform an existing production system with its integrated Enterprise Information Systems (EISs) into a CPPS. This is a very broad question and the scope of this work is limited to the concept development stage. The purpose of the paper is twofold: (1) to elaborate a metamodel for formalizing the elements that constitute CPPSs, with a particular emphasis on the involved EISs, and (2) to propose a method for supporting the transformation of an existing production system with its integrated EISs into a CPPS. Firstly, a literature review on the transformation methods towards CPPSs is carried out. It concludes that existing studies do not consider all aspects of CPPSs, especially its EISs, and that there is a lack of a method that analyzes the gap between the As-Is system and the To-Be system. As a result, a meta-model describing the main object classes that constitute CPPSs and the interrelationships among these classes, is proposed. Next, a method based on the meta-model is proposed to support the transformation into a CPPS. It provides a checking matrix to immediately visualize which improvement actions in the As-Is system are required. Furthermore, a case study illustrating the use of the method is presented. Finally, the contributions of the study are summarized and future work is highlighted.

Introduction

The manufacturing industry is facing challenging trends, such as highly customized products, increasing product complexity and shorter product lifecycles. Cyber Physical Systems (CPSs), which are characterized by a tight interaction of computational and physical elements to provide intelligence, responsiveness and adaptation [START_REF] Leitão | Industrial automation based on cyber-physical systems technologies: prototype implementations and challenges[END_REF], are part of the solution for tackling the growing challenges that manufacturing industries are facing. The specific application of CPSs to production environments results in Cyber-Physical Production Systems (CPPSs).

transformation from legacy systems to CPPSs have been proposed so far.

Consequently, transformation of legacy systems into CPPSs is an emerging topic that is growing rapidly and deserves more attention. However, this is a very broad topic and includes overwhelming and complex tasks that cannot be simply handled by this paper. While the ultimate goal is to develop a comprehensive methodology for transforming legacy systems into CPPSs, at the moment the paper is a preliminary study positioned at the concept development stage which attempts to provide a partial contribution to this broad topic. The contribution of the paper consists of a meta-model defining all necessary elements of a CPPS, with a particular emphasis on involved EISs, and a method for transforming an existing production system with its integrated EISs into a CPPS to guide industry practitioners in visualizing which elements need to be added and modified to become a real CPPS.

The rest of the paper is organized as follows: In Section 2, we propose the definition of CPPSs and further elaborate the research problem, scope and objective. Section 3 presents the related works of the transformation methods into CPPSs. Section 4 presents the meta-model of CPPSs and Section 5 presents the method for the transformation into a CPPS. Section 6 illustrates the use of this method with a case study. Section 7 concludes the paper by synthesizing the contribution and indicating future research directions.

Research context

The definition of CPPSs

There are many definitions of CPPSs, but there is no consensus on a formal definition. There are two distinct categories of research streams on the definition of CPPSs. As for CPSs in general, the first research stream advocates that a CPPS is the glue (i.e. a middleware layer) that connects the cyber world with the physical world, as in [START_REF] Wang | Current status and advancement of cyberphysical systems in manufacturing[END_REF]. The second research stream advocates that a CPPS is a system of systems in which cyber components work seamlessly and in synergy together with physical systems to form a whole to fulfill a common mission, as in [START_REF] Lee | Cyber physical systems: design challenges[END_REF]. We adhere to the second stream. However, the existing definitions are unclear on what a CPPS really is and what it should include, even the widely cited one proposed by [START_REF] Monostori | Cyber-physical systems in manufacturing[END_REF]. We therefore propose the following, more concise definition:

A CPPS is a combination of technological agents (including smart products and smart devices), IT agents and humans, collaborating within a synergistic production environment to carry out technical, decision-making or cognitive tasks autonomously, using the best capabilities of each kind of agent involved.

In this definition, technological agents include all physical devices (such as robots and Computer Numeric Control (CNC) machines) as well as products with sensing, computation and control units, therefore being able to receive and send messages and make local decisions. IT agents include hardware (such as computers) and software (such as computer programs and software packages). Humans refer to all kinds of human agents involved in the system.

Problem statement

According to the definition of CPPSs, EISs, which are made of computers, software, people, processes and data [START_REF] Romero | Enterprise information systems state of the art: past, present and future trends[END_REF], can be considered to be included in CPPSs. EISs are defined as "software systems for business management, encompassing modules supporting organizational functional areas such as planning, manufacturing, sales, marketing, distribution, accounting, financial, human resources management, project man-agement, inventory management, maintenance, transportation and e-business" [START_REF] Rashid | The evolution of ERP systems: a historical perspective, enterprise resource planning: solutions and management[END_REF]. Nowadays, operations of production systems are realized through various EISs, including customer relationship management (CRM) systems, enterprise resource planning (ERP) systems, manufacturing execution systems (MES), etc. Therefore, when transforming a legacy system into a CPPS, not only its production system needs to be considered, but its involved EIS as well. In this regard, the research problem addressed herein is: "How to transform an existing production system with its integrated EIS into a CPPS in the context of Industry 4.0 or Smart Manufacturing?".

Research scope and objective

According to systems engineering principles [START_REF] Kossiakoff | Systems Engineering Principles and Practice[END_REF][START_REF] Shortell | INCOSE Systems Engineering Handbook: a Guide for System Life Cycle Processes and Activities, Version 4.0[END_REF]International Organization for Standardization, 2015), a system life cycle development can be divided into three main stages: (1) the concept development stage, which is the initial stage of the formulation and definition of a system concept perceived to best satisfy a valid need; (2) the engineering development stage, which covers the translation of the system concept into hardware, control and software designs; and

(3) the post development stage, which includes the production, deployment, operation, and support of the system throughout its useful life. When applying systems engineering principles to CPPSs, a generic transformation process towards a CPPS can be considered as a stepwise process which consists of these three stages. This paper is a preliminary study positioned at the concept development stage.

The objective of this work is to propose, for the concept development stage, a method to support the transformation of an existing production system with its integrated EIS into a CPPS. First of all, due to the complexity and structural opacity of CPPSs, a model needs to be set up for a common understanding of CPPSs, especially the elements of involved EISs. Therefore, in this work, a meta-model of CPPSs has been elaborated by defining the necessary elements that constitute a CPPS and their interrelationships. Then, by instantiating the meta-model, a method for the transformation of an existing production system with its integrated EISs into a CPPS is proposed. This method provides a detailed process to guide people in analyzing the gap between As-Is systems and To-Be systems and, therefore, to identify which elements need to be added or modified for future implementation. The proposed method gives a transformation matrix to help industry practitioners to understand the current status of existing production systems and visualize what should be improved to move towards CPPSs.

Related works on transformation methods

As stated in Section 2.3, the research scope of the paper is concept development. Therefore, this section presents an overview of transformation methods relevant for the concept development stage and identifies the research gap. [START_REF] Wu | Concept and engineering development of cyber physical production systems: a systematic literature review[END_REF] have already proposed a systematic literature review of existing approaches used in the concept development stage of CPPSs. We refer to some of the articles they reviewed but reanalyze them from the perspective of transformation. According to this review, there are many architectures for CPPSs, including standard architectures (such as the widely recognized RAMI 4.0 [START_REF] Adolphs | Status report-reference architecture model Industrie 4.0 (RAMI 4. 0[END_REF] and IIRA [START_REF] Lin | Industrial internet reference architecture[END_REF]), multilayer architectures (such as the most popular 5C Architecture [START_REF] Lee | A cyber-physical systems architecture for Industry 4.0-based manufacturing systems[END_REF]), and architectures with specific design concerns (such as a human-centered architecture [START_REF] Francalanza | A knowledge-based tool for designing cyber physical production systems[END_REF]). Although these architectures provide generic structuring guidelines for implementing CPPSs, they do not deal with brownfield [START_REF] Lee | A cyber-physical systems architecture for Industry 4.0-based manufacturing systems[END_REF].

implementations that is to say created on top of legacy systems rather than starting from scratch [START_REF] Etz | Smart manufacturing retrofit for brownfield systems[END_REF]. For example, although the RAMI 4.0 includes concepts and standards for an Industry 4.0 implementation, it does not suggest a way to transform old equipment into modern CPSs.

There are some methods dedicated to the transformation into CPPSs. [START_REF] Lass | A factory operating system for extending existing factories to Industry 4[END_REF] propose a CPS component concept including architecture model and hardware proposal, which allows the combination of classic PLC programming and implementation of complex algorithms to successfully transform existing, non-CPS plants, into a CPPS. [START_REF] Etz | Smart manufacturing retrofit for brownfield systems[END_REF] propose an architecture detailing how to design and implement an OPC UA gateway for a legacy robot system in order to allow seamless communication across machines within a smart manufacturing environment. [START_REF] Lins | A novel methodology for retrofitting CNC machines based on the context of industry 4[END_REF] propose a method for retrofitting existing CNC machines, which depicts in detail the functional requirements, the design parameters, data model and the system architecture. [START_REF] Khan | A seamless cloud migration approach to secure distributed legacy industrial SCADA systems[END_REF] propose an architecture for the cloud migration that can be applied to legacy industrial SCADA systems. These transformation methods are specific to certain devices and do not consider all the aspects of CPPSs but only part of its technological agents and IT agents. To be more precise, existing studies concerning technological agents of CPPSs aim at adding new technologies (such as communication gateways) to existing devices and ingesting data and information of control functions to the cloud for storage and processing. The existing studies concerning IT agents of CPPSs focus on transforming enterprise applications into cloud-based services. The ignored aspects, such as human and business processes, are mainly those covered by Enterprise Information Systems (EISs) in CPPSs. Therefore, in this study, a meta-model is proposed to define all necessary elements in CPPSs, including its integrated EIS at a detailed level.

There are some studies that are not restricted to specific types of devices. For example, (Lins et al., 2018;[START_REF] Lins | Cyber-physical production systems retrofitting in context of industry 4.0[END_REF] define three components of the transition to CPPSs: infrastructure, communication and application and propose the retrofitting process according to these components. However, they do not consider the status of the existing system and do not analyze the gap between the target system and the legacy one. The transformation can be implemented by ( 1) either adding new functionality that was not available when it was originally designed, such as adding new communication protocols; or (2) modifying existing components, such as exchange of old computers by faster processing units. They all aim to enhance specific elements of legacy systems in order to increase new functionalities. However, due to the complexity and structural opacity of CPPSs, it is difficult to figure out which new elements are added and which old elements are affected. Therefore, in this paper, a method is proposed to support manufacturing industries to visualize which elements need to be added and modified to move towards CPPSs.

Meta-model of CPPSs

This section presents a meta-model that specifies the main object classes of CPPSs and their interrelationships. The following sub-sections present how to extract classes and how to establish their interrelationships for setting up the meta-model.

Object classes in a CPPS

The object classes in a CPPS are extracted from two parts: the 5C Architecture [START_REF] Lee | A cyber-physical systems architecture for Industry 4.0-based manufacturing systems[END_REF] and enterprise modelling standards (ISO 19439, 2006ISO 19439, 2006;ISO 19440, 2020ISO 19440, 2020).

(1) Object classes extracted from the 5C Architecture [START_REF] Lee | A cyber-physical systems architecture for Industry 4.0-based manufacturing systems[END_REF] proposed the 5C Architecture for implementing CPSs, as shown in Fig. 1. It can equally be extended to CPPSs. Because the 5C Architecture is the most popular and broadly accepted architecture, it is proposed to use it as a reference to specify the object classes in a CPPS.

At the smart connection level (C1 level), all the physical devices, such as machines and robots, are connected and communicate to one another through communication protocols and standards, so that data can be acquired from a variety of sources and stored in the data center. At the data-to-information conversion level (C2 level), meaningful data can be inferred from a large volume of raw data by data preprocessing technologies. At the cyber level (C3 level), data is transformed into useful information by data analysis technologies and a Digital Twin (DT) of the physical world is created. At the cognition level (C4 level), the extracted information is delivered to end-users for decision making through presentation interfaces. At the configuration level (C5 level), a series of decisions about actions are applied to the physical system and achieve self-configuration and self-adaptiveness in response to external environmental changes.

Based on the description of each level of the 5C Architecture obtained from [START_REF] Lee | A cyber-physical systems architecture for Industry 4.0-based manufacturing systems[END_REF], a set of key-nouns (in bold) have been extracted to become the object classes. For example, part of the description of the connection level is "acquiring data from machines and their components is the first step and the data might be directly measured by sensors or obtained from controllers or EIS software" [START_REF] Lee | A cyber-physical systems architecture for Industry 4.0-based manufacturing systems[END_REF]. From this sentence, the following classes are identified: data, machine, component, sensor, controller and EIS software package. The process for extracting the object classes at the other levels is the same, therefore we do not detail them anymore. One thing worth mentioning is that C1 to C4 levels already include all the classes and there are no new classes at the C5 level because it only applies the decisions made at the C4 level to the C1 level. Smart products, which are important objects in the definition of CPPSs, are not emphasized in the 5C Architecture. Therefore, a new object class "Product" is added at the connection level. The results of all the extracted object classes for the five levels are shown in Table 1.

To reach a consensus on the meaning of these classes, "Communication Protocol" and "Presentation Interface" are specifically explained in detail because these two classes are prone to be misunderstood due to their names. The communication protocols are defined as the entirety of communication hardware and software. "Presentation interface" is used as an umbrella class that enables the human-system interaction. It includes cognitive assistance software that supports information and knowledge management, and devices that translate human input into electronic signals and vice versa. A cognitive assistance software is able to observe and analyze information and recommend appropriate actions in real-time.

(2) Object classes extracted from enterprise modelling standards EISs can be regarded as multidimensional information processing objects, which include three main dimensions [START_REF] Reix | Systèmes d'information et management des organisations[END_REF]: (1) an informational dimension: EISs are representations of the environment through a set of data; (2) a technological dimension: EISs are systems that carry out the processes of collecting, storing and processing information, which consist of hardware and software; (3) an organizational dimension: EISs support business processes and decision-making processes, which require actors and technological resources.

From this description, it can be concluded that the 5C Architecture only covers the informational and technological dimension of EIS, such as integrated software packages like ERP systems, but does not cover the organizational dimension. Therefore, it is pro-posed to build the other object classes of EIS on the basis of the enterprise modeling standards ISO 19439 (2006) andISO 19440 (2020), which precisely define a set of enterprise modeling constructs. Among these constructs, the relevant ones are selected as the necessary object classes for representing EIS, as shown in Table 2. Informational, technological and organizational dimensions of EIS are distinguished by three colors: pink, blue and orange.

Combining the object classes extracted from the 5C architecture and enterprise modeling standards, the meta-model, shown in Fig. 2, has been elaborated as a Unified Modelling Language (UML) object class diagram. Object classes of the EISs domain are highlighted using three colors (pink, blue and orange) corresponding to the three dimensions (respectively, informational, technological and organizational) usually covered in most EISs.

Interrelationships between object classes

The interrelationships between the object classes extracted from the 5C Architecture can be inferred and obtained from the description of this architecture. In the same way, the interrelationships between the object classes extracted from enterprise modelling standards can be derived directly from these standards. Therefore, these interrelationships are not described herein. Only the interrelationships between the classes extracted from the 5C Architecture and those extracted from the enterprise modelling standards are detailed. According to the three dimensions of EISs, these interrelationships are also categorized into three kinds (respectively, informational, technological and organizational relationships) as shown in Table 3 and are highlighted with three colors (pink, blue and orange) in Fig. 2.

• The technological relationships mean that EISs provide hardware, software and datarelated capabilities (such as data storage and processing capabilities) to perform the processes of collecting, storing and processing data. • The informational relationships mean that data and information are stored in EIS databases and represented by EIS interfaces. • The organizational relationships mean that EISs support the business processes and decision-making processes in production systems through humans and other technological resources.

A method for transforming an existing production system with its integrated EIS into a CPPS

By instantiating the meta-model, a method for the transformation of an existing production system with its integrated EISs into a CPPS is proposed in this section. The instantiation principles of the meta-model are first described. Then, based on these principles, a method for the transformation is presented.

Instantiation principles of the meta-model

Instantiation principles of the meta-model are described as follows, which gives guidance for the instantiation process:

• Principle 1: Classes extracted from the 5C Architecture should be instantiated layer by layer from the C1 level to the C5 level, as the 5C Architecture gives a sequential workflow for the implementation of CPSs. That is to say, if classes at the C1 level are not instantiated, it is impossible to instantiate classes at the C2 level and the same goes for other levels. • Principle 2: At each level, the classes extracted from the 5C

Architecture should be instantiated first and then the EIS classes associated with the technological, informational and organizational relationships at this level should be instantiated. This way, the technological relationships are first considered, then the informational relationships and finally the organizational relationships. Indeed, if there are no technological relationships, it is impossible to obtain data/information and to have an informational relationship. Also, if there are no informational relationships, it is impossible to support efficiently business processes and decision making and to have an organizational relationship.

Combining Principle 1 and Principle 2, the instantiation process starts with the C1 level, and goes further with the EIS classes associated with the technological, informational and organizational relationships at the C1 level. Then, this instantiation loop moves to the C2 level and repeats until the C5 level.

Method for transforming a production system into a CPPS

In this section, based on instantiating the meta-model, a method for the transformation into a CPPS is proposed as shown in Fig. 3.

• Step I: Understand the existing production system (As-Is system), including its composition, functionalities, used technologies, architectures and production processes.

•

Step II: Define To-Be system requirements, which is a formal description of the target system specification. System requirements can then be broken down into basic functions, and each of them can be fulfilled by dedicated classes in a CPPS, which form the component requirements. [START_REF] Wu | Concept and engineering development of cyber physical production systems: a systematic literature review[END_REF] conducted a systematic literature review on the existing works on the requirement analysis of CPPSs, which could be used as a reference to carry out this activity.

Table 3

Interrelationships between object classes extracted from the 5C Architecture and object classes extracted from enterprise modelling standards.

•

Step III: Perform gap analysis by instantiating the meta-model. In the transformation context, it means mapping the As-Is system with the meta-model. This enables firstly to identify the missing classes or those that need to be modified according to the To-Be system requirements, and then to instantiate the corresponding object classes. In this work, because the focus is on concept development, the instantiation of the object classes is considered as the investigation of possible solution options according to the component requirements and the choice of the optimal solution, without the detailed design and implementation. According to the principles defined in Section 5.1, the instantiation process of the meta-model is shown in Fig. 4. At each level, there are four kinds of mapping activities (mapping the 5C classes, mapping the EIS classes associated with the technological, informational and organizational relationships) and one instantiation activity. The use of the 5C Architecture is intended to assist the CPPS transformation process in the different levels of maturity, but it is not necessary to implement all five levels. If all requirements can be met at a given level, the transformation process ends; otherwise, it goes to the next level until the C5 level. Therefore, at the end of each level, there is a checking activity to see whether it is required to go to the next level according to the To-Be system requirements. To better understand the activities of the instantiation process of Fig. 4, an IDEF0 diagram (Fig. 5) is proposed to analyze the data required by each activity, including inputs, outputs, resources (or mechanisms) supporting the activity, and constraints (controls) required for the activity. There are five activities that are consistent with the activities in Fig. 4. After each mapping activity, a checking matrix of the object classes is proposed to immediately visualize the gap between the As-Is and To-Be system, as shown in Table 4. This matrix is structured in rows and columns. The columns represent the object classes in the meta-model. Meanwhile, the rows describe the instantiation of the As-Is system and To-be system and the three states of classes (to be created, to be modified, and no modification) of object classes. Each class should have one and only one state.

Case study

To illustrate the use of the method, an academic case study is presented to clarify each step of the method. As the method is positioned at the concept development stage, this case study refrains from deeper technological details. In addition, as the case study is for illustrating the use of the method, not for technological validation in industry cases, it is a simplified case inspired by a production line of the LS2N Laboratory at the University of Nantes, France.

As-Is description of a production system

Let us consider an example of an As-Is production system mainly consisting of three articulated ABB industrial robots, three CNC machine tools, computer and shop floor Kanban, MES, humans, warehouse (storing parts and manufactured products) and parts, as shown in Fig. 6. The pick and place operations between the conveyor and the CNC machine tools is performed by the robots. Robot #1 also performs the load and unload work between the warehouse and the conveyor.

In this system, the CNC machine tools and robots form a shop floor-level IoT. The detailed configuration of the As-Is system is shown in Fig. 7. The robotic arm has a controller with a serial interface and is fully actuated with each DOF (Degree of Freedom) by a motor. A Raspberry Pi board is connected to the robot controller via an RS-232 cable to a Serial converter, and software created in Python with a user interface is responsible for continuously sending and receiving data to/from the robot serial interface. The Raspberry Pi board has an SSH (Secure Shell) remote access interface, a secure communication protocol that can be used to exchange data over an Ethernet network. USB cameras are fixed on robots to recognize the object and position of parts. Embedded boards (Raspberry Pi) are also configured for CNC machines, with remote communication capabilities similar to those implemented in the robot. Vibration sensors are fixed on the spindle of CNC machines to receive the vibration value. By collecting vibration data, it is possible to monitor machines running conditions and manage predictive maintenance. Local databases deployed on each embedded board store the real-time data and the pre-processed data, while a MES database deployed in the cloud stores order data, production rules, historical data and other engineered data. Meanwhile, preprocessed data from the local databases is further synchronized to the MES database. For local data processing, the real-time data acquired from different data sources is first cleaned to eliminate inaccurate and duplicated data. The Sorted Neighborhood Method (SNM) and K-means clustering algorithms are used to realize data cleansing [START_REF] Ding | Defining a Digital Twinbased Cyber-Physical Production System for autonomous manufacturing in smart shop floors[END_REF]. Then, a Fast Fourier Transform (FFT) is used for feature extraction [START_REF] Ding | Defining a Digital Twinbased Cyber-Physical Production System for autonomous manufacturing in smart shop floors[END_REF], which could be treated as the machine health indicators. After this, the meaningful data is extracted and uploaded through the shop floor network to the public database for backup. The generated information, including production progress and machine status, is visualized in shop floor Kanban's for shop-floor managers and operators to make decisions and take actions. An MES can store manufacturing data, monitor production processes and display production status to humans. This production system does not implement the connectedness of all the elements within the industrial network for data interaction and sharing, which results in the inability to obtain information from the surrounding environment and to respond to internal and external changes. Therefore, the system must be transformed into a CPPS to have connectedness, intelligence and responsiveness.

Transformation of the As-Is system into a CPPS

The transformation of the As-Is system into a CPPS can be implemented by adding new elements or modifying existing elements.

However, due to the complexity of CPPSs, it is difficult to figure out which new elements should be added and which old elements are affected. The method proposed in Section 5 gives, for concept development, a detailed process for transforming existing production systems with its integrated EISs into CPPSs. There are three steps for the transformation process from the As-Is system to the CPPS as follows:

(1) Step I: Understand the As-Is system According to the description of the As-Is system in Section 6.1, machines (including CNC machine tools and industrial robots) network access (including interfaces, protocols, etc.) has been configured, together with the intelligence of machines. However, the connection of parts to the industrial network and the intelligence of parts has not been configured. The parts to be manufactured should have their local intelligence to know how they are manufactured, what kinds of resources they need and what the current manufacturing work-in-progress is. Besides, the autonomous interaction between parts and machines has not been carried out in the As-Is system and those should be interconnected within the industrial network for data interaction and sharing.

With the aid of MES, in the As-Is system, operators can perceive the real-time production data and monitor the production statuses. However, when there is interference, such as the breakdown of machines and new orders insertion, the operation will stop and wait for shop floor managers and operators to make decisions, which is centralized and with low efficiency.

(2) Step II: Define system requirements.

According to the problems identified for the As-Is system in step I, three requirements for the To-Be system are stated, as shown in Table 5.

(3) Step III: Instantiate the meta-model. According to Fig. 4, there are four mapping activities and an instantiation activity at each level.

At the C1 level, after the four mapping activities between the As-Is system and the meta-model, their mapping results are shown in Table 6. The technological relationships between EIS classes and other classes of CPPSs mean that databases and computer programs Then, the instantiations of each object class in the As-Is system are checked one by one to see if the new system requirements Fig. 7. As-Is system configuration.

Table 5

CPPSs Requirements statement.

ID Requirements

RQ1

Connectedness of parts to the industrial network and the autonomous interaction between parts and machines within the industrial network for information interaction and sharing.

RQ2

Intelligence of parts: parts can acquire information from their environment (capabilities and states about machines and the sequence of manufacturing operations and their current progress, including which kind of machine performs a certain operation and how is the production progressing) and make decisions about production scheduling autonomously.

RQ3

Autonomous production scheduling to respond quickly to unexpected events or disturbances.

Table 6

Mapping between the As-Is system and object classes in the meta-model. are met. To meet RQ1 and RQ2, the existing instantiation of the class "Data acquisition technology", "Data storage technology", "Raw data" needs to be modified for acquiring data of parts and connect parts to the industrial network. RFID technologies and embedded board for parts can implement the intelligence of parts and their communication with machines. The result is shown in the checking matrix (Table 7). As the RQ3 has not been met yet, the transformation process goes to the next level.

From the C2 level to the C5 level, the transformation process is the same as at the C1 level. The new requirement is to implement responsive production scheduling. The As-Is system only has local data processing. For global data analysis in the cloud, a decision tree can be used to infer the cause of the interference. Then, knowledge-based reasoning (KBR), Deep Neural Network (DNN) and the non-dominant sorting genetic algorithm (NSGA-II) can further be used to generate responsive production scheduling strategies [START_REF] Ding | Defining a Digital Twinbased Cyber-Physical Production System for autonomous manufacturing in smart shop floors[END_REF]. The checking matrix of states of object classes and their instantiation is shown in Table 8. The To-Be system configuration is shown in Fig. 8, where changes are highlighted in red.

Results

Through the creation and modification of object classes, the centralized and human-intervened manufacturing operations control in the As-Is production system can be replaced by a decentralized and autonomous one in the To-Be system.

In the To-Be system, autonomous production scheduling is as follows.

(1) When an order is received, detailed information of the part type (such as manufacturing requirements, quantity and quality) is written in an RFID tag attached to the part. The manufacturing operations for each part are generated based on the above data.

(2) Parts will announce their next operation to all the machines and each machine can decide whether it can process the part or not. On this basis, parts and machines can autonomously interact with each other to decide the optimal production sequences dynamically and react to disturbances collaboratively. For example, after calculating the real-time data of spindle speed and vibration based on a decision tree, a dominant disturbance is reasoned out that the CNC machine #1 has shut down. To keep normal manufacturing operations, machine #1 will broadcast a message about its shutdown to the other machines. Thus, the other machines can give their responsive messages to machine #1 on whether they can or cannot undertake the task. Finally, a scheduling strategy that recommends machine #2 to undertake the task of machine #1 is applied to the production system.

(3) Once all the manufacturing operations are finished, a product is generated for delivery.

From this example, one can note that some decisions on production scheduling, which are traditionally made in EISs by humans, could be managed by CPPS, by adding intelligence capabilities to the elements of CPPS. This will minimize response times, increase the flexibility and autonomy of the entire system, make the system selfaware and self-configurable and have minimal intervention from humans.

Conclusion and outlook

CPPSs can be considered as extremely important advances in the development of production systems to progress towards Smart Manufacturing or Industry 4.0. Transformation solutions of legacy systems into CPPSs are being proposed by academics. However, existing studies only focused on the transformation of specific elements of CPPSs (i.e., retrofit of machine tools), without considering all elements of CPPSs especially involved EISs. This work aims to propose a method for supporting the transformation of an existing production system with its EISs into a true CPPS.

The contributions of this work are: (1) According to the 5C Architecture and the enterprise modelling standards, a meta-model that describes the main object classes that constitute CPPSs is proposed. In particular, it includes three dimensions of EISs: informational, technological and organizational dimensions, respectively; and (2) by instantiating the meta-model, a method for supporting the transformation of an existing production system with its integrated EISs into a CPPS is proposed. As a result, a checking matrix is proposed, which is a useful tool to immediately visualize which elements are needed to be added and modified in the As-Is system. This work provides the first attempt to pave the way for the development of urgently needed CPPSs transformation methodologies.

As future work, further exploration and enhancement of the method are needed to ensure its applicability to real-world and large case applications. More specifically, the next step needs to move forward from the concept development stage to the engineering development stage of the system life cycle. As we have already identified three dimensions of EISs to be considered in the transformation, we will study how to transform them, especially the organizational dimension of EISs. In the organizational dimension, we will address the following question: how to transform the decision-making process of EISs? It may include these sub questions: which decisions can automatically be made by CPPSs components locally? which decisions have to be made by humans? What are the impacts of these local decisions on business processes? We will explore potential architectures, techniques and tools to support this transformation.

CRediT authorship contribution statement

Fig. 1 .

 1 Fig. 1. 5C Architecture for the implementation of CPSs (Lee et al., 2015).

Fig. 2 .

 2 Fig. 2. Meta-model of CPPSs. a) A global view of meta-model. b) A partial view of meta-model.

Fig. 3 .

 3 Fig. 3. Method for transforming a production system into a CPPS.

Fig. 4 .

 4 Fig. 4. Meta-model instantiation process.

Fig. 5 .

 5 Fig. 5. Activity A0 -To instantiate the meta-model.

Fig. 6 .

 6 Fig. 6. Layout of As-Is system.

Xuan Wu :

 Wu Methodology, Validation, Writing -Original Draft, Writing -Review & Editing. Virginie Goepp: Methodology, Validation, Writing -Review & Editing, Supervision. Ali Siadat: Validation, Writing -Review & Editing, Supervision. Franc ¸ois Vernadat: Methodology, Writing -Review & Editing, Supervision.

Table 1

 1 Object Classes extracted from the 5C Architecture.

	Levels	Object Classes extracted from the 5C architecture
	C1	Product, Component, Machine, Production System, Sensor,
		Controller, EIS Software Package, Raw Data,
		Communication Protocol, Data Acquisition Technology,
		Data Storage Technology, Central Server
	C2	Meaningful data, Data Preprocessing Technology
	C3	Information Hub, Data Analysis Technology
	C4	Information, Presentation Interface, Human, Decision
	C5	(nil)

Table 2

 2 Selection of the object classes for EIS from the enterprise modeling constructs.

Table 4

 4 Checking matrix of object classes.

Table 7

 7 Checking matrix of object classes and their instantiation.

		Object classes	Instantiation of object classes		States of object classes
		As-Is system	To-Be system	To be created	To be modified	No modification
	C1	Product Component Sensor Machine Controller Production System EIS software package Communication	Parts Robotic arm, spindle of CNC machine USB Camera, vibration sensor ABB Robot, CNC machine Controller of robot, micro-controller of CNC machine As-Is system To-Be system MES Ethernet, RS 232, SSH, cable, router		√	√ √ √ √ √ √
		Protocol
		Data Acquisition	• Hardware: sensors, controllers;• Software: computer programs		√
		Technology	-	RFID
		Data Storage	• Hardware: Raspberry Pi, computer; • Software: database		√
		Technology	-	Embedded board of
				parts (Raspberry
		Central Server	Pi) Local databases provided by embedded boards		√
	Technological dimension of EIS	Raw Data Resource Capability	Data from vibration sensor, camera, controller and MES Data from RFID Computer, local database, MES Data acquisition and storage capability -New data		√ √	√
				acquisition and
				storage capability
				of parts data

Fig. 8. To-Be system configuration.

Funding

This work was supported by China Scholarship Council under Grant 201706020154.

Declaration of Competing Interest

The authors declare that they have no conflict of interest.


The Red-Blue Separation problem on graphs Subhadeep Ranjan Dev 1 , Sanjana Dey 1 , Florent Foucaud 2,3 , Ralf Klasing 4 , and Tuomo Lehtilä 5,6

1 egw nitD sndin ttistil snstituteD uolktD sndi 2 niversité glermontEeuvergneD gxD wines de intEÉtienneD glermontEeuvergneEsxD vswyD TQHHH glermontEperrndD prne nivF yrlénsD sxe gentre l de voireD vspy ie RHPPD pERSHTU yrléns gedex PD prne niversité de fordeuxD fordeux sxD gxD vfsD w SVHHD leneD prne niv vyonD niversité glude fernrdD gxD vss E w SPHSD pTWTPPD prne 6 niversity of urkuD heprtment of wthemtis nd ttistisD urkuD pinlnd

Abstract. e introdue the Red-Blue Separation prolem on grphsD where we re given grph G = (V, E) whose verties re olored either red or lueD nd we wnt to selet @smllA suset S ⊆ V D lled redblue separating setD suh tht for every redElue pir of vertiesD there is vertex s ∈ S whose losed neighorhood ontins extly one of the two verties of the pirF e study the omputtionl omplexity of Red-Blue SeparationD in whih one sks whether given redElue olored grph hs redElue seprting set of size t most given inteE gerF e prove tht the prolem is xEomplete even for restrited grph lssesF e lso show tht it is lwys pproximle in polynomil time within ftor of 2 ln nD where n is the input grph9s orderF sn ontrstD for tringleEfree grphs nd for grphs of ounded mximum degreeD we show tht Red-Blue Separation is solvle in polynomil time when the size of the smller olor lss is ounded y onstntF roweverD on generl grphsD we show tht the prolem is W [2]Ehrd even when pE rmeterized y the solution size plus the size of the smller olor lssF e lso onsider the prolem Max Red-Blue Separation where the oloring is not prt of the inputF rereD given n input grph GD we wnt to determine the smllest integer k suh thtD for every possible red-bluecoloring of GD there is redElue seprting set of size t most kF e derive tight ounds on the rdinlity of n optiml solution of Max Red-Blue SeparationD showing tht it n rnge from logrithmi in the grph orderD up to the order minus oneF e lso give ounds with reE spet to relted prmetersF por trees however we prove n upper ound of twoEthirds the orderF e then show tht Max Red-Blue Separation is xEhrdD even for grphs of ounded mximum degreeD ut n e pproximted in polynomil time within ftor of O(ln 2 n)F his study hs een rried out in the frme of the snvestments for the future rogrmme sdix fordeux E ysxum @exEIHEshiEHQEHPAF eserh (nned y the prenh government shiEssi inititive ITEshiEHHHI @ge PHEPSA nd y the ex projet qevwigy @exEPIEgiRVEHHHREHIAF eserh supported y the pinnish gulturl poundtion nd y the edemy of pinlnd grnt QQVUWUF 1 Introduction

We introduce and study the Red-Blue Separation problem for graphs. Separation problems for discrete structures have been studied extensively from various perspectives. In the 1960s, Rényi [24] introduced the Separation problem for set systems (a set system is a collection of sets over a set of vertices), which has been rediscovered by various authors in dierent contexts, see e.g. [2,6,17,23].

In this problem, one aims at selecting a solution subset S of sets from the input set system to separate every pair of vertices, in the sense that the subset of S corresponding to those sets to which each vertex belongs to, is unique. The graph version of this problem (where the sets of the input set system are the closed neighborhoods of a graph), called Identifying Code [18], is also extensively studied. These problems have numerous applications in areas such as monitoring and fault-detection in networks [26], biological testing [23], and machine learning [20]. The Red-Blue Separation problem which we study here is a red-blue colored version of Separation, where instead of all pairs we only need to separate red vertices from blue vertices.

In the general version of the Red-Blue Separation problem, one is given a set system (V, S) consisting of a set S of subsets of a set V of vertices which are either blue or red; one wishes to separate every blue from every red vertex using a Problem denition. In the graph setting, we are given a graph G and a red-blue coloring c : V (G) → {red, blue} of its vertices, and we want to select a (small) subset S of vertices, called red-blue separating set, such that for every red-blue pair r, b of vertices, there is a vertex from S whose closed neighborhood contains exactly one of r and b.

Equivalently, N [r] ∩ S = N [b] ∩ S, where N [x] denotes the closed neighborhood of vertex x; the set N [x] ∩ S is called the code of x
(with respect to S), and thus all codes of blue vertices are dierent from all codes of red vertices. The smallest size of a red-blue separating set of (G, c) is denoted by sep RB (G, c). Note that if a red and a blue vertex have the same closed neighborhood, they cannot be separated. Thus, for simplicity, we will consider only twin-free graphs, that is, graphs where no two vertices have the same closed neighborhood. Also, for a twin-free graph, the vertex set V (G) is always a redblue separating set as all the vertices have a unique subset of neighbors. We have the following associated computational problem.

he Red-Blue Separation prolem on grphs Q Red-Blue Separation Input: A red-blue colored twin-free graph (G, c) and an integer k. Question: Do we have sep RB (G, c) ≤ k?

It is also interesting to study the problem when the red-blue coloring is not part of the input. For a given graph G, we thus dene the parameter max-sep RB (G) which denotes the largest size, over each possible red-blue coloring c of G, of a smallest red-blue separating set of (G, c). The associated decision problem is stated as follows.

Max Red-Blue Separation

Input: A twin-free graph G and an integer k.

Question: Do we have max-sep RB (G) ≤ k?

In Fig. 1, to note the dierence between sep RB and max-sep RB , a path of 6 vertices P 6 is shown, where the vertices are colored red or blue.

(a) 1. e pth of T verties where @A sepRB(P6, c) = 1 nd @A max-sepRB(P6) = 3Y the memers of the redElue seprting set re irledF Our results. We show that Red-Blue Separation is NP-complete even for restricted graph classes such as planar bipartite sub-cubic graphs, in the setting where the two color classes 1 have equal size. We also show that the problem is NP-hard to approximate within a factor of (1 -) ln n for every > 0, even for split graphs 2 of order n, and when one color class has size 1. On the other hand, we show that Red-Blue Separation is always approximable in polynomial time within a factor of 2 ln n. In contrast, for triangle-free graphs and for graphs of bounded maximum degree, we prove that Red-Blue Separation is solvable in polynomial time when the smaller color class is bounded by a constant (using algorithms that are in the parameterized class XP, with the size of the smaller color class as parameter). However, on general graphs, the problem is shown to be W [2]-hard even when parameterized by the solution size plus the size of the smaller color class. (This is in contrast with the geometric version of separating points by half-planes, for which both parameterizations are known to be xedparameter tractable [3,19].) As the coloring is not specied, max-sep RB (G) is a parameter that is worth studying from a structural viewpoint. In particular, we study the possible values 1 yne lss onsists of verties olored red nd the other lss onsists of verties olored blueF 2 e grph G = (V, E) is lled split graph when the verties in V n e e prtiE tioned into n independent set nd liqueF for max-sep RB (G). We show the existence of tight bounds on max-sep RB (G) in terms of the order n of the graph G, proving that it can range from log 2 n up to n -1 (both bounds are tight). For trees however we prove bounds involving the number of support vertices (i.e. which have a leaf neighbor), which imply that max-sep RB (G) ≤ 2n 3 . We also give bounds in terms of the (non-colored) separation number. We then show that the associated decision problem Max Red-Blue Separation is NP-hard, even for graphs of bounded maximum degree, but can be approximated in polynomial time within a factor of O(ln 2 n).

v 1 v 2 v 3 v 4 v 5 v 6 (b) v 1 v 2 v 3 v 4 v 5 v 6 Fig.
Related work. Red-Blue Separation has been studied in the geometric setting of red and blue points in the Euclidean plane [3,5,22]. In this problem, one wishes to select a small set of (axis-parallel) lines such that any two red and blue points lie on the two sides of one of the solution lines. The motivation stems from the Discretization problem for two classes and two features in machine learning, where each point represents a data point whose coordinates correspond to the values of the two features, and each color is a data class. The problem is useful in a preprocessing step to transform the continuous features into discrete ones, with the aim of classifying the data points [7,19,20]. This problem was shown to be NP-hard [7] but 2-approximable [5] and xed-parameter tractable when parameterized by the size of a smallest color class [3] and by the solution size [19].

A polynomial time algorithm for a special case was recently given in [22].

The Separation problem for set systems (also known as Test Cover and Discriminating Code) was introduced in the 1960s [24] and widely studied from a combinatorial point of view [1,2,6,17] as well as from the algorithmic perspective for the settings of classical, approximation and parameterized algorithms [8,10,23]. The associated graph problem is called Identifying Code [18] and is also extensively studied (see [21] for an online bibliography with almost 500 references as of January 2022); geometric versions of Separation have been studied as well [9,15,16]. The Separation problem is also closely related to the VC Dimension problem [27] which is very important in the context of machine learning. In VC Dimension, for a given set system (V, S), one is looking for a (large) set X of vertices that is shattered, that is, for every possible subset of X, there is a set of S whose trace on X is the subset. This can be seen as perfectly separating a subset of S using X; see [4] for more details on this connection.

Structure of the paper. We start with the algorithmic results on Red-Blue Separation in Section 2. We then present the bounds on max-sep RB in Section 3 and the hardness result for Max Red-Blue Separation in Section 4. Due to space constraints, we have omitted some proofs or parts of proofs.

Complexity and algorithms for Red-Blue Separation

We will prove some algorithmic results for Red-Blue Separation by reducing to or from the following problems.

he Red-Blue Separation prolem on grphs

S Set Cover

Input: A set of elements U , a family S of subsets of U and an integer k. Question: Does their exist a cover C ⊆ S, with |C| ≤ k such that C∈C C = U ?

Dominating Set

Input: A graph G = (V, E) and an integer k.

Question: Does there exist a set D ⊆ V of size k with ∀v ∈ V, N [v] ∩ D = ∅?
2.1 Hardness Theorem 1. Red-Blue Separation cannot be approximated within a factor of (1 -) • ln n for any > 0 even when the smallest color class has size 1 and the input is a split graph of order n, unless P = NP. Moreover, Red-Blue Separation is W[2]-hard when parameterized by the solution size together with the size of the smallest color class, even on split graphs.

Proof. For an instance ((U, S), k) of Set-Cover, we construct in polynomial time an instance ((G, c), k) of Red-Blue Separation where G is a split graph and one color class has size 1. The statement will follow from the hardness of approximating Min Set Cover proved in [11], and from the fact that Set Cover is W[2]-hard when parameterised by the solution size [12].

We create the graph (G, c) by rst creating vertices corresponding to all the sets and the elements. We connect a vertex u i corresponding to an element i ∈ U to a vertex v j corresponding to a set S j ∈ S if u i ∈ S j . We color all these vertices blue. We add two isolated blue vertices b and b . We connect all the vertices of type u i ∈ U to each other. Also, we add a red vertex r and connect all vertices u i ∈ U to r. Now, note that the vertices U ∪ {r} form a clique whereas the vertices v j along with b and b form an independent set. Thus, our constructed graph (G, c) with the coloring c is a split graph. See Fig. 2.

Sets

Elements Theorem 2. Red-Blue Separation is NP-hard for bipartite planar sub-cubic graphs of girth at least 12 when the color classes have almost the same size.

{} {} r u 1 u n u i v 1 v j v m b b'
Proof. We reduce from Dominating Set, which is NP-hard for bipartite planar sub-cubic graphs with girth at least 12 that contain some degree-2 vertices [28].

We reduce any instance (G, k) of Dominating Set to an instance ((H, c), k ) of Red-Blue Separation, where k = k + 1 and the number of red and blue vertices in c dier by at most 2.

H R G H B construction v v B v R u 1 u 2 u 3 u 4
Fig. 3. edution from Dominating Set to Red-Blue Separation of heorem PF Construction. We create two disjoint copies of G namely H B and H R and color all vertices of H B blue and all vertices of H R red. Select an arbitrary vertex v of degree-2 in G (we may assume such a vertex exists in G by the reduction of [28]) and look at its corresponding vertices v R ∈ V (H R ) and v B ∈ V (H B ). We connect v R and v B with the head of the path u 1 , u 2 , u 3 , u 4 as shown in Fig. 3. The tail of the path, i.e. the vertex u 4 , is colored blue and the remaining three vertices u 1 , u 2 and u 3 are colored red. Our nal graph H is the union of H R , H B and the path u 1 , u 2 , u 3 , u 4 and the coloring c as described. Note that if G is a connected bipartite planar sub-cubic graph of girth at least g, then so is H (since v was selected as a vertex of degree-2). We make the following claim.

Claim 2. The instance (G, k) is a YES-instance of Dominating Set if and only

if sep RB (H, c) ≤ k = k + 1.
In the previous reduction, we could choose any class of instances for which Dominating Set is known to be NP-hard. We could also simply take two copies of the original graph and obtain a coloring with two equal color class sizes (but then we obtain a disconnected instance). In contrast, in the geometric setting, the problem is xed-parameter-tractable when parameterised by the size of the smallest color class [3], and by the solution size [19]. It is also 2-approximable [5].

Positive algorithmic results

We start with a reduction to Set Cover implying an approximation algorithm.

Proposition 3. Red-Blue Separation has a polynomial time (2 ln n)-factor approximation algorithm. Proof. Without loss of generality, we assume |R| ≤ |B|. We construct a redblue separating set S of (G, c). First, we add all red vertices to S. It remains to separate every red vertex from its blue neighbors. If a red vertex v has at least two neighbors, we add (any) two such neighbors to S. Since G is triangle-free, no blue neighbor of v is in the closed neighborhood of both these neighbors of v, and thus v is separated from all its neighbors. If v had only one neighbor w, and it was blue, then we separate w from v by adding one arbitrary neighbor of w (other than v) to S. Since G is triangle-free, v and w are separated. Thus, we have built a red-blue separating set S of size at most 3|R|.

Proposition 5. Let (G, c) be a red-blue colored twin-free graph with maximum

degree ∆ ≥ 3. Then, sep RB (G, c) ≤ ∆ min{|R|, |B|}.
Proof. Without loss of generality, let us assume |R| ≤ |B|. We construct a redblue separating set S of (G, c). Let v be any red vertex. If there is a blue vertex w whose closed neighborhood contains all neighbors of v (w could be a neighbor of v), we add both v and w to S. If v is adjacent to w, since they cannot be twins, there must be a vertex z that can separate v and w; we add z to S. Now, v is separated from every blue vertex in G.

If such a vertex w does not exist, then we add all neighbors of v to S. Now again, v is separated from every vertex of G. Thus, we have built a red-blue separating set S of size at most ∆|R|.

The previous propositions imply that Red-Blue Separation can be solved in XP time for the parameter size of a smallest color class on triangle-free graphs and on graphs of bounded degree (by a brute-force search algorithm). This is in contrast with the fact that in general graphs, it remains hard even when the smallest color class has size 1 by Theorem 1. Theorem 6. Red-Blue Separation on graphs whose vertices belong to the color classes R and B can be solved in time O(n 3 min{|R|,|B|} ) on triangle-free graphs and in time O(n ∆ min{|R|,|B|} ) on graphs of maximum degree ∆.

Extremal values and bounds for max-sep RB

We denote by sep(G) the smallest size of a (non-colored) separating set of G, that is, a set that separates all pairs of vertices. We will use the relation max-sep RB (G) ≤ sep(G), which clearly holds for every twin-free graph G.

Lower bounds for general graphs

We can have a large twin-free colored graph with solution size 2 (for example, in a large blue path with a single red vertex, two vertices suce). We show that in every twin-free graph, there is always a coloring that requires a large solution.

Theorem 7. For any twin-free graph G of order n ≥ 1 and n ∈ {8, 9, 16, 17}, we have max-sep RB (G) ≥ log 2 (n) .

Proof. Let G be a twin-free graph of order n with max-sep RB (G) = k. There are 2 n dierent red-blue colorings of G. For each such coloring c, we have sep RB (G, c) ≤ k. Consider the set of vertex subsets of G which are separating sets of size k for some red-blue colorings of G. Notice that each red-blue coloring has a separating set of cardinality k. There are at most n k ≤ n k such sets.

Consider such a separating set S and consider the set I(S) of subsets S of S for which there exists a vertex v of G with N [v] ∩ S = S . Let i S be the number of these subsets: we have i S ≤ 2 |S| ≤ 2 k . If S is a separating set for (G, c), then all vertices having the same intersection between their closed neighborhood and S must receive the same color by c. Thus, there are at most 2 i S ≤ 2 2 k red-blue colorings of G for which S is a separating set. Overall, we thus have

2 n ≤ n k 2 2 k ≤ n k 2 2 k
, and thus n ≤ k log 2 (n) + 2 k . We now claim that this implies that k ≥ log 2 (n -log 2 (n) log 2 (n)). Suppose to the contrary that this is not the case, then we would obtain:

n < log 2 (n -log 2 (n) log 2 (n)) log 2 (n) + n -log 2 (n) log 2 (n) n < log 2 (n) log 2 (n) + n -log 2 (n) log 2 (n)
And thus n < n, a contradiction. Since k is an integer, we actually have k ≥ log 2 (n -log 2 (n) log 2 (n)) . To conclude, one can check that whenever n ≥ 70, we have log 2 (n -log 2 (n) log 2 (n)) ≥ log 2 (n) . Moreover, if we compute values for 2 nn k 2 2 k when 1 ≤ n ≤ 69 and k = log 2 (n) -1, then we observe that this is negative only when n ∈ {8, 9, 16, 17}. Thus, log 2 (n) is a lower bound for max-sep RB (G) as long as n ∈ {8, 9, 16, 17}.

The bound of Theorem 7 is tight for innitely many values of n.

Proposition 8. For any integers k ≥ 1 and n = 2 k , there exists a graph G of order n with max-sep RB (G) = k.

We next relate parameter max-sep RB to other graph parameters.

Theorem 9. Let G be a graph on n vertices. Then, sep(G) ≤ min{ log 2 (n) • max-sep RB (G), log 2 (∆(G) + 1) • max-sep RB (G) + γ(G)}, where γ(G) is the domination number of G and ∆(G) its maximum degree.

Proof. Let G be a graph on 2 k-1 + 1 ≤ n ≤ 2 k vertices for some integer k. We denote each vertex by a dierent k-length binary word x 1 x 2 • • • x k where each x i ∈ {0, 1}. Moreover, we give k dierent red-blue colorings c 1 , . . . , c k such that vertex x 1 x 2 • • • x k is red in coloring c i if and only if x i = 0 and blue otherwise. For each i, let S i be an optimal red-blue separating set of (G, c i ). We have

|S i | ≤ max-sep RB (G) for each i. Let S = k i=1 S i . Now, |S| ≤ k•max-sep RB (G) = log 2 (n) • max-sep RB (G).
We claim that S is a separating set of G. Assume to the contrary that for two vertices

x = x 1 x 2 • • • x k and y = y 1 y 2 • • • y k , N [x] ∩ S = N [y] ∩ S.
For some i, we have y i = x i . Thus, in coloring c i , vertices x and y have dierent colors and hence, there is a vertex s ∈ c i such that s ∈ N [y] N [x], a contradiction which proves the rst bound.

Let S be an optimal red-blue separating set for such a coloring c and let D be a minimum-size dominating set in G; S ∪ D is also a red-blue separating set for coloring c. At most ∆(G) + 1 vertices of G may have the same closed neighborhood in D. Thus, we may again choose log 2 (∆(G) + 1) colorings and optimal separating sets for these colorings, each coloring (roughly) halving the number of vertices having the same vertices in the intersection of separating set and their closed neighborhoods. Since each of these sets has size at most max-sep RB (G), we get the second bound.

We do not know whether the previous bound is reached, but as seen next, there are graphs G such that sep(G) = 2 max-sep RB (G).

Proposition 10. Let G = K k1,...,kt be a complete t-partite graph for t ≥ 2,

k i ≥ 5 odd for each i. Then sep(G) = n -t and max-sep RB (G) = (n -t)/2.

Upper bound for general graphs

We will use the following classic theorem in combinatorics to show that we can always spare one vertex in the solution of Max Red-Blue Separation.

Theorem 11 (Bondy's Theorem [2]). Let V be an n-set with a family

A = {A 1 , A 2 , . . . , A n } of n distinct subsets of V . There is an (n -1)-subset X of V such that the sets A 1 ∩ X, A 2 ∩ X, A 3 ∩ X, . . . , A n ∩ X are still distinct.
Corollary 12. For any twin-free graph G on n vertices, we have max-sep RB (G)

≤ sep(G) ≤ n -1.
This bound is tight for every even n for complements of half-graphs (studied in the context of identifying codes in [14]).

Denition 13 ). For any integer k ≥ 1, the half-graph H k is the bipartite graph on vertex sets {v 1 , . . . , v k } and {w 1 , . . . , w k }, with an edge between v i and w j if and only if i ≤ j.

The complement H k of H k thus consists of two cliques {v 1 , . . . , v k } and {w 1 , . . . , w k } and with an edge between v i and w j if and only if i > j.

Proposition 14. For every k ≥ 1, we have max-sep RB (H k ) = 2k -1.

Upper bound for trees

We will now show that a much better upper bound holds for trees.

Degree-1 vertices are called leaves and the set of leaves of the tree T is L(T ). Vertices adjacent to leaves are called support vertices, and the set of support vertices of T is denoted S(T ). We denote (T ) = |L(T )| and s(T ) = |S(T )|. The set of support vertices with exactly i adjacent leaves is denoted S i (T ) and the set of leaves adjacent to support vertices in S i (T ) is denoted L i (T ). Observe that |L 1 (T )| = |S 1 (T )|. Moreover, let L + (T ) = L(T ) \ L 1 (T ) and S + (T ) = S(T ) \ S 1 (T ). We denote the sizes of these four types of sets s i (T ), i (T ), s + (T ) and + (T ).

To prove our upper bound for trees, we need Theorems 15 and 16.

Theorem 15. For any tree T of order n ≥ 5, we have max-sep RB (T ) ≤ n+s(T ) 2 .

Proof. Observe that the claim holds for stars (select the vertices of the smallest color class among the leaves, and at least two leaves). Thus, we assume that s(T ) ≥ 2. Let c be a coloring of T such that max-sep RB (T ) = sep RB (T, c).

We build two separating sets C 1 and C 2 ; the idea is that one of them is small. We choose a non-leaf vertex x and add to the rst set C 1 every vertex at odd distance from x and every leaf. If there is a support vertex u ∈ S 1 (T )∩C 1 and an adjacent leaf v ∈ L 1 (T )∩N (u), we create a separating set C 1 from C 1 by shifting the vertex away from leaf v to some vertex w ∈ N (u) \ L(T ). We construct in a similar manner sets C 2 and C 2 , except that we add the vertices at even distance from x to C 2 and do the shifting when u ∈ S 1 (T ) has even distance to x.

Claim 3. Both C 1 and C 2 are separating sets.

Let us denote by N S 3 (T ) a smallest set of vertices in T such that for each vertex

v ∈ S 3 (T ) which has N (v) ∩ S + (T ) = ∅, we have at least one vertex u ∈ N (v) \ L(T ) in N S 3 (T ) (such a set exists since T is not a star).
We assume that out of the two sets C 1 and C 2 , C a (a ∈ {1, 2}) has less vertices among the vertices in V (T ) \ (L(T ) ∪ S + (T ) ∪ N S 3 (T )). In particular, it contains at most half of those vertices and we have |C a \ (L(T ) ∪ S + (T ) ∪ N S 3 (T ))| ≤ (n -(T ) -s + (T ) -|N S 3 (T )|)/2. Now, we will construct set C from C a . Let us start by having each vertex in C a be in C. Let us then, for each support vertex u ∈ S + (T ), remove from C every adjacent leaf w ∈ L + (T ) ∩ N (u) such that w is in the more common color class within the vertices in N (u) ∩ L + (T ) in coloring c. We then add some vertices to C as follows. For u ∈ S i (T ), i ≥ 4, we add u to C and some leaves so that there are at least two vertices in N (u) ∩ C. We have at most |L(T

) ∩ N [u]|/2 + 1 vertices in C ∩ (N [u] ∩ L(T ) ∪ {u}).
For i = 3, we add u and any v ∈ N S 3 (T ) ∩ N (u) \ C, depending on which one already belongs to C. Then, if all leaves in N (u) have the same color, we add one of them to C. Hence, we have |C ∩ (L 2 (T ) ∪ N S 3 (T ))|/s 3 (T ) ≤ 2.

Finally, for i = 2, if the two leaves have same color and u ∈ C a , we add u and one of the two leaves to C. If the two leaves have the same color and u ∈ C a , we add a non-leaf neighbor of u to C. If the leaves have dierent colors, one of them, say v, has the same color as u. We add u to C and shift the vertex in C in the leaves so that v is in C. We added at most two vertices to C in this case.

Notice that now we have S + (T ) ⊆ C.

Each time, we added to C at most half the considered vertices in N (u), and at most one additional vertex. After these changes, we shift some vertices in C away from L 1 (T ) the same way we built C a from C a . As |C a \ (L(T ) ∪ S + (T ) ∪ consisting of the vertices {p 1 , . . . , p 6 , q 1 , . . . , q 4 }. Every vertex p i is connected to a unique pair of vertices from {u 1 , u 2 , u 3 , u 4 } and every vertex q j is connected to a unique triple of vertices from {u 1 , u 2 , u 3 , u 4 }. For example in the gure we have p 4 connected with the pair of vertices u 2 and u 3 and q 3 connected with the triplet of vertices u 1 , u 3 and u 4 . Let H(v 1 , v 2 ) be a subgraph of some graph G such that H is connected to the rest of G only by the vertices v 1 and v 2 . We dene a worst-coloring of G as any red-blue coloring of G where sep RB (G, c) = max-sep RB (G). We make the following claim.

Claim 5. For any worst-coloring c of G the optimal red-blue separating code of (G, c) will always contain the vertices u 1 , u 2 , u 3 and u 4 .

The variable gadget for a variable x consists of the graph H(x 1 , x 2 ) and H(x, x) with additional edges (x 1 , x 2 ), (x 1 , x) and (x 1 , x). If x 1 and x 2 are colored dierently, then either x or x needs to be in the red-blue separating set. Selecting at least one of x or x also separates x and x themselves. The clause gadget for a clause c = (x ∨ y ∨ z) is H(c 1 , c 2 ), where c 1 is connected to the vertices x, y and z. If c 1 and c 2 are colored dierently, then the red-blue separating set should contain at least one of x, y or z in order to separate them. This is used to show the following, and complete the proof. Claim 6. σ is satisable if and only if max-sep RB (G) ≤ k = 4m + 9n.

We can use Theorem 9 and a reduction to Set Cover to show the following.

Theorem 20. Max Red-Blue Separation can be approximated within a factor of O((ln n) 2 ) on graphs of order n in polynomial time.

Conclusion

We have initiated the study of Red-Blue Separation and Max Red-Blue Separation on graphs, problems which seem natural given the interest that their geometric version has gathered, and the popularity of its non-colored variants Identifying Code on graphs or Test Cover on set systems.

When the coloring is part of the input, the solution size of Red-Blue Separation can be as small as 2, even for large instances; however, we have seen that this is not possible for Max Red-Blue Separation since max-sep RB (G) ≥ log 2 (n) for twin-free graphs of order n. max-sep RB (G) can be as large as n -1 in general graphs, yet, on trees, it is at most 2n/3 (we do not know if this is tight, or if the upper bound of 3n/5, which would be best possible, holds). It would also be interesting to see if other interesting upper or lower bounds can be shown for other graph classes.

We have shown that sep(G) ≤ log 2 (n) • max-sep RB (G). Is it true that sep(G) ≤ 2 max-sep RB (G)? As we have seen, this would be tight.

We have also shown that Max Red-Blue Separation is NP-hard, yet it

  solution subset C of S (here a set of C separates two vertices if it contains exactly one of them). Motivated by machine learning applications, a geometric-based special case of Red-Blue Separation has been studied in the literature, where the vertices of V are points in the plane and the sets of S are half-planes [7]. The classic problem Set Cover over set systems generalizes both Geometric Set Cover problems and graph problem Dominating Set (similarly, the set system problem Separation generalizes both Geometric Discriminating Code and the graph problem Identifying Code). It thus seems natural to study the graph version of Red-Blue Separation.

Fig. 2 .

 2 Fig. 2. edution from Set Cover to Red-Blue Separation of heorem IF

  he Red-Blue Separation prolem on grphs U Proposition 4. Let (G, c) be a red-blue colored triangle-free and twin-free graph with R, B the two color classes. Then, sep RB (G, c) ≤ 3 min{|R|, |B|}.

Fig. 4 .

 4 Fig. 4. edution from 3-SAT-2l to Max Red-Blue SeparationF

  does not naturally belong to NP. Is the problem actually hard for the second level of the polynomial hierarchy? References IF fF folloás nd eF hF ottF yn seprting systemsF European Journal of Combinatorics PVXIHTV!IHUID PHHUF PF tF eF fondyF sndued susetsF Journal of Combinatorial Theory, Series B IP@PAXPHI!PHPD IWUPF QF ÉF fonnetD F qinnopoulos nd wF vmpisF yn the prmeterized omplexity of redElue points seprtionF Journal of Computational Geometry IH@IAXIVI!PHTD PHIWF RF xF fousquetD eF vgoutteD F viD eF rreu nd F homsséF sdentifying odes in hereditry lsses of grphs nd gEdimensionF SIAM Journal on Discrete Mathematics PW@RAXPHRU!PHTRD PHISF SF qF g § linesuD eF humitresuD rF tF urlo' nd F nF eprting points y xisE prllel linesF International Journal Of Computational Geometry & ApplicationsIS@TAXSUS!SWHD PHHSF TF iF ghritD sF ghronD qF gohenD yF rudry nd eF vosteinF hisriminting odes in iprtite grphsX oundsD extreml rdinlitiesD omplexityF Advances in Mathematics of Communications P@RAXRHQ!RPHD PHHVF UF fF F ghleus nd F rF xguyenF yn (nding optiml disretiztions for two tE triutesF roeedings of the Ist snterntionl gonferene on ough ets nd gurrent rends in gomputing @gg IWWVAF Lecture Notes in Computer Science IRPRXSQU!SRRD IWWVF VF F growstonD qF qutinD wF tonesD qF wuii nd eF eoF rmeteriztions of test over with ounded test sizesF Algorithmica UR@IAXQTU!QVRD PHITF WF F heyD pF pouudD F gF xndy nd eF enF hisriminting odes in geometri setupsF roeedings of the QIst snterntionl ymposium on elgorithms nd gomputtion @seeg PHPHAF Leibniz International Proceedings in Informatics IVIDPRXIEPRXITD PHPHF IR F F hevD F heyD pF pouudD F ulsingD F vehtilä IHF uF wF tF he fontridderD fF F rlldórssonD wF wF rlldórssonD gF eF tF rurkensD tF uF venstrD F vi nd vF tougieF epproximtion lgorithms for the test over prolemF Mathematical Programming Series B WVXRUU!RWID PHHQF IIF sF hinur nd hF teurerF enlytil pproh to prllel repetitionF ACM Symposium on Theory of computingD RTXTPR!TQQD PHIRF IPF F qF howney nd wF F pellowsF Parameterized ComplexityF pringer erlgD IWWWF IQF F ird®sF ome omintorilD geometri nd set theoreti prolems in mesure theoryF sn Measure Theory Oberwolfach 1983D pges QPI!QPUF pringerD IWVRF IRF pF pouudD iF querriniD wF uov²eD F xsersrD eF rreu nd F liovF ixtreml grphs for the identifying ode prolemF European Journal of Combinatorics QP@RAXTPV!TQVD PHIIF ISF F qledel nd eF rreuF sdenti(tion of points using disksF Discrete Mathematics QRPXPST!PTWD PHIWF ITF F rrEeled nd wF tonesF yn seprting points y linesF Discrete and Computational Geometry TQXUHS!UQHD PHPHF IUF wF eF renning nd eF eoF histinguishingEtrnsversl in hypergrphs nd idenE tifying open odes in ui grphsF Graphs and Combinatorics QH@RAXWHW!WQPD PHIRF IVF wF qF urpovskyD uF ghkrrty nd vF fF vevitinF yn new lss of odes for identifying verties in grphsF IEEE Transactions on Information Theory RRXSWW!TIID IWWVF IWF F urtshD F ws°íkD sF wuziD wF ilipzuk nd wF orgeF yptiml disretizE tion is (xedEprmeter trtleF roeedings of the QPnd egwEsew ympoE sium on hisrete elgorithms @yhe PHPIAD ppF IUHPEIUIWD PHPIF PHF tF uujl nd F ilomF smproved lgorithms for univrite disretiztion of ontinuous feturesF roeedings of the IIth iuropen gonferene on rini ples nd rtie of unowledge hisovery in htse @uhh PHHUAF Lecture Notes in Computer Science RUHPXIVV!IWWD PHHUF PIF eF vosteinF thing systemsD identifyingD lotingEdominting nd disE riminting odes in grphsX iliogrphyF https://www.lri.fr/~lobstein/ debutBIBidetlocdom.pdf PPF xF wisrD rF wittl nd eF ethiF edElue point seprtion for points on irE leF roeedings of the QPnd gndin gonferene on gomputtionl qeometry @gggq PHPHAD ppF PTT!PUPD PHPHF PQF fF wF iF woret nd rF hF hpiroF yn minimizing set of testsF SIAM Journal of Scientical and Statistical Computation T@RAXWVQ!IHHQD IWVSF PRF eF ényiF yn rndom generting elements of (nite foolen lgerF Acta Scientiarum Mathematicarum Szeged PPXUS!VID IWTIF PSF gF eF oveyF e simpli(ed xEomplete stis(ility prolemF Discrete Applied Mathematics V@IAXVS!VWD IWVRF PTF F ngrngsiD eF rhtenerg nd hF troinskiF en implementtion of indoor lotion detetion systems sed on identifying odesF Proceedings of Intelligence in Communication Systems, INTELLCOMM 2004F Lecture Notes in Computer Science QPVQXIUS!IVWD PHHRF PUF F xF pnik nd eF F ghervonenkisF yn the uniform onvergene of reltive frequenies of events to their proilitiesF Theory of Probability & Its Applications IT@PAXPTR!PVHD IWUIF PVF sF iF vervih nd F iF verovihF en indued sugrph hrteriztion of domintion perfet grphsF Journal of Graph Theory PH@QAXQUSEQWSD IWWSF

Claim 4. C is a red-blue separating set for coloring c.

The upper bound of Theorem 15 is tight. Consider, for example, a path on eight vertices. Also, the trees presented in Proposition 18 are within 1/2 from this upper bound. In the following theorem, we oer another upper bound for trees which is useful when the number of support vertices is large.

Theorem 16. For any tree T of order n ≥ 5, sep(T ) ≤ n -s(T ).

The following corollary is a direct consequence of Theorems 15 and 16. Indeed, we have max-sep RB (T ) ≤ min{n -s(T ), (n + s(T ))/2}.

Corollary 17. For any tree T of order n ≥ 5, we have max-sep RB (T ) ≤ 2n 3 .

We next show that Corollary 17 (and Theorem 15) is not far from tight.

Proposition 18. For any k ≥ 1, there is a tree T of order n = 5k + 1 with

4 Algorithmic results for Max Red-Blue Separation

The problem Max Red-Blue Separation does not seem to be naturally in the class NP (it is in the second level of the polynomial hierarchy). Nevertheless, we show that it is NP-hard by reduction from a special version of 3-SAT [25].

3-SAT-2l

Input: A set of m clauses C = {c 1 , . . . , c m } each with at most three literals, over n Boolean variables X = {x 1 , . . . , x n }, and each literal appears at most twice. Question: Is there an assignment of X where each clause has a true literal?

Theorem 19. Max Red-Blue Separation is NP-hard even for graphs of maximum degree 12.

Proof. To show hardness we reduce from the 3-SAT-2l problem. Given an instance σ of 3-SAT-2l with m clauses and n variables, we create an instance (G, k) of Max Red-Blue Separation as follows.

First let us explain the construction of a domination gadget and its properties.

A domination gadget on vertices v 1 and v 2 is represented in Fig. 4. The vertices v 1 and v 2 may be connected to each other or to some other vertices which is represented by the dashed edges. Both v 1 and v 2 are also connected to the vertices u 1 , u 2 , u 3 and u 4 as shown in the gure. Next we have a clique K 10