Olivier Bonnaud
email: olivier.bonnaud@univ-rennes1.fr

Mandatory Matching Between Microelectronics Industry and Higher Education in Engineering Towards a Digital Society

Keywords: Microelectronics, Higher Education structuring, Industry 4.0., Engineering

Mandatory matching between microelectronics industry and higher education in engineering toward a digital society

O.

Introduction

Everybody knows that the XXI century will be the era of the fourth industrial revolution with the progressive introduction of digital society, with connected objects, smart objects, and new manufacturing governed by robotics, internet of things and artificial intelligence. They are all included in the Internet of Things (IoT). The production should be performed by the so-called industry 4.0. This means the development of computer sciences associated to new objects and systems that can fulfil the adequate missions thanks to new technologies. The core of these objects and tools capable of integrating software is microelectronics. In practice, the real evolution towards this new world has been possible thanks to the fabulous evolution of microelectronic technologies, based on the integration of billions of transistors per circuit. This evolution has made it possible to store billions of data, to process these data with more than one hundred billion operations per second but also to communicate them with such a flow. In addition, microelectronics technological processes are capable of developing sensors and actuators that are the links between the real and physical world and digital space. Behind this physical evolution, huge teams of engineers, technicians and researchers have been working since the early 1960s. The new industry 4.0 plants, requires skills and competencies not only in robotics and production management, but also in microelectronic design and technological manufacturing. The challenge is to meet the needs of the industry. Practical training must be constantly updated with good knowledge of dedicated tools and equipment. To achieve this objective, higher education must provide students with knowledge and skills on increasingly expensive tools. A dedicated and strongly industry-related organization must be set up with common platforms allowing the sharing of technological equipment and CAD tools. This article deals with the French national microelectronics network (CNFM [START_REF] Cnfm | Coordination Nationale pour la formation en Microélectronique and nanotechnologies[END_REF][START_REF] Bonnaud | GIP-CNFM: a French education network moving from microelectronics to nanotechnologies[END_REF]) that has proven its worth in higher education in microelectronics engineering for more than thirty years. After a presentation of the context, the organization and objectives are highlighted and several examples of innovative practical work are given.

2

Trends of the microelectronics industry

Evolution of the integration in microelectronics

The world evolution towards a digital society is highly dependent on microelectronic technologies, which are therefore at the heart of all devices and systems involved in IoT. This evolution, exponential in practice, is the result of more than fifty years of increasing integration, which is becoming very complex and combines many technological approaches and multidisciplinary architectures. Figure 1 shows the evolution of integration into a chip predicted by G. Moore and called Moore's Law [START_REF] Moore | Cramming more components onto integrated circuits[END_REF] and the recent evolution of systems that include systems on a chip or in a package that grow exponentially in a similar way to Moore's Law [START_REF] Simonite | Moore's Law Is Dead. Now What?[END_REF] and thus allow connected objects to be created.

Towards a digital society: connected objects

As we have already presented [START_REF] Bonnaud | Innovation for education on Internet of things, International Conference on Advanced Technology Innovation (ICATI[END_REF], connected objects make it possible to analyze and control many aspects of society's needs remotely. They are first of all composed of on-site functions such as sensors, actuators, and signal processing as shown Figure 1, and at remote sites, of a transmitter and receiver, a signal processing system and a remote control system.

Fig. 1. Evolution of the integration during the last sixty years. The density of transistors per die increased exponentially following the prediction of G. Moore [START_REF] Moore | Cramming more components onto integrated circuits[END_REF]. Since 1995, the integration had started a new exponential evolution [START_REF] Simonite | Moore's Law Is Dead. Now What?[END_REF], the density of transistors reaching 10 13 .

Fig. 2 Simplified architecture of a connected object with on-site component and remote component (after O. Bonnaud et al. [START_REF] Bonnaud | Innovation for education on Internet of things, International Conference on Advanced Technology Innovation (ICATI[END_REF]). It is mainly composed of sensors, actuators, signal converters, processor, emitter-receiver, visualization, alarms and controls, and energy harvesting.

Multidisciplinarity of the fields of applications

The most important interest of connected objects is related to the wide spectrum of their applications. All the major areas of modern society are concerned. These include communications and information, health, safety, environment, energy, transport, agriculture, manufacturing in industry 4.0. As a result, future designers of these objects must have skills and abilities in the field of microelectronics, but also be able to work in teams with specialists in the fields of application [START_REF] Bonnaud | Towards multidisciplinarity for microelectronics education: a strategy of the French national network[END_REF].

Heterogeneous integration toward systems on chip and systems in package

The connected objects must integrate new functions adapted to the application fields. These functions can have physical, chemical, and biological-based detectors and actuators combining a large variety of architectures and physical elements (optical, mechanical) thermal dependence devices, chemical or biological functionalization. In many cases, they need also an energy autonomy; this means integration of batteries or electrical charge storage, and energy harvesting cells. This is becoming possible thanks to a heterogeneous integration (figure 3) [START_REF] Bottoms | System Level Design and Simulation for Heterogeneous Integration Electronic Design Process Symposium[END_REF]. It is clear that the third dimension (3D) takes more and more importance at the level of ULSI (Ultra large Scale Integration) for example with Coolcub TM [START_REF] Batude | Demonstration of low temperature 3D sequential FDSOI integration down to 50nm gate length[END_REF]) or in packaging that combines several technologies as thin film technologies or Micro-Electro-Mechanical systems (MEMS).

Fig. 3. Diversity of the heterogeneous integration (After B. Bottoms [START_REF] Bonnaud | Know-how needs for higher education in nanoelectronics: French CNFM network strategy[END_REF]). Many functions are integrated involving several technologies and 3D stacking.

In summary, new device and packaging architectures are needed to meet future market demand and to develop connected objects for industry 4.0. The consequence is that in 2018 the world's microelectronics activities represented an income of more than 480 billion US dollars, while the global activities involving microelectronic devices represented more than 6.8 billion US dollars as shown in Figure 4 [START_REF] Matheron | Microelectronics evolution, Keynote, European, Microelectronics Summit[END_REF]. The challenge is today to have competences and skills adapted to the development of future technologies and to the future market. An effort must be made in the Higher Education and more especially in microelectronic engineering.

3

Higher education meeting the industry needs

Evolution of the knowledge acquisition in the digital environment

With the development of computer equipment, combined with the increase in storage capacity, communications and Internet, many new tools dedicated to online higher education have been created. One can mention the massive open online courses (MOOC's) and the whole family of these online tools [START_REF] Fox | From MOOCs to SPOCs[END_REF]. Several tools have been developed in the field of microelectronics [START_REF] Stuchlikova | Massive open online courses in microelectronics education[END_REF] and have been discussed within the microelectronics community about the opportunity and threat of the global dissemination of these tools. Indeed, if MOOCs are good theoretical learning tools and can change the way-people learn [START_REF] Littlefield | What Makes a Good Online Course?[END_REF], they have a low effectiveness for the acquisition of know-how, which is an essential skill for engineers [START_REF] Bonnaud | New Vision in Microelectronics Education: Smart e-Learning and Knowhow, a Complementary Approach[END_REF].

The know-how: a mandatory complement of the knowledge

Indeed, the use of MOOCs has some limitations in engineering sciences. In the field of micro and nanoelectronics, the online presentation of the electrical behavior of an integrated circuit remains essentially virtual. Due to their complexity, it is almost impossible to take into account all the physical and environmental parameters that can affect their electrical behavior. The simulation models are always approximate. A characterization of the actual (and physical) product is required to warranty the final properties of the circuits. Thus, practice is the key to understanding and acquiring skills [START_REF] Bonnaud | Practice in microelectronics education as a mandatory complement to the future numeric-based pedagogy: a strategy of the French national network[END_REF]. It is fundamental for innovation [START_REF] Bonnaud | A way to introduce Innovative approach in the field of Microelectronics and nanotechnologies in the Chinese Education system[END_REF], and producing innovative objects.

Needs of mutualization of the microelectronics engineering training

As mentioned above, the field of microelectronics and nanotechnology is undergoing a huge evolution towards complexity, heterogeneity of technologies and multidisciplinarity. The corresponding practice requires very expensive tools and equipment, both in CAD using dedicated software and in cleanroom manufacturing processes, or in physical characterization and electrical testing. The only appropriate solution is to organize a network with several platforms common to several academic institutions in the same area and to share expenses between users. This approach is realistic in the context of a national network that can obtain several financial supports from public agencies, the Ministry of Higher Education and industrial partners.

4

The French National network for microelectronics education

Constitution of the CNFM network: academic/industry partnership

The microelectronic higher education in France is organized through a 35-year old national network, the National Coordination for Education in Microelectronics and Nanotechnologies, recognized by the Higher Education Ministry [START_REF] Cnfm | Coordination Nationale pour la formation en Microélectronique and nanotechnologies[END_REF]. This network is composed of twelve academic members that have in charge the twelve common centers spread over the French territory as shown figure 5. It also includes two representations of industrial organizations and especially the most representative association ACSIEL Alliance Electronics consortium [START_REF]ACSIEL Alliance Electronique[END_REF]. The industrial partners consider the training activities as an important factor for maintaining and developing electronics in France, and thus provide the network with valuable advice necessary.

The missions and the strategy of the CNFM network

The very essence of the GIP-CNFM network is to share platforms because of their very high equipment and operating costs, but also to share pedagogical approaches and good practices towards students trained in initial training or LifeLong Learning (LLL). Collaboration within the network exists in several forms, through the sharing and common use of technological and design platforms, and through collaborative work in the context of national, or international, multi-year projects and through pedagogical days and brainstorming seminars. These joint activities allow for the exchange of knowledge and practices in order to produce and disseminate knowledge and know-how to the entire academic community.

The main results of the network

The 12 centers offering many training platforms receive yearly more than 90 degrees in its 7 clean rooms and 81 platforms covering most aspects of electronics, i.e. basic silicon microelectronic technology and design, low-power electronics, power electronics, embedded electronics, RF and millimeter wave electronics, MEMS, biological MEMS (BioMEMS), organic electronics, thin-film technologies, photovoltaic technology. More than 16,000 students are users of the platforms each year, representing more than 890,000 hours-students per year of training.

Strategy of the CNFM network towards know-how and innovation

In order to meet societal needs directly related to technological change, the content of practical training must be constantly updated. To this end, the management has a policy oriented towards an innovative approach, both in the content of practical training and in pedagogical approaches. In 2011, the network applied for an innovative national program under the Excellence in Higher Education Initiative. The FINMINA project (Innovative Formation in Microelectronics and Nanotechnologies) of the CNFM network has been accepted [START_REF]FINMINA: Formations Innovantes en Microélectronique et Nanotechnologies, See website of CNFM, IDEFI project[END_REF]. This is an eight-year project dedicated to innovation. This associated financial support enables the twelve joint centers to develop innovative practices mainly oriented towards new technologies for IoT.

Innovative practice

Know-how at the heart of the microelectronics field: innovative platforms

The innovative practice is first of all dedicated to the field of microelectronics and nanotechnologies. Indeed, this field is directly connected to the Moore's Law and More than More's evolution. New software for modeling the elementary devices for which the dimension reaches the nanoscale, new tools for CAD able to design very complex analog and digital circuits that contain billions of transistors, but also very high frequency modules for the transmission a very high flow of digital data, must be introduced in the content of the CAD platforms of the network. In addition, the heterogeneous technology assembling that combines many functions involved in connected objects must be designed with new multi-physic simulators in order to include in the systems sensors and actuators, significant components of the connected objects. All the students at the level of master of engineering must have some know-how of these tools that are used in the research centers and in the companies. Because the performances are directly linked to the fabrication process, the innovative platforms are created in order to prepare the students to the novel technologies such as, 3D elementary devices, optoelectronics involving III-V compound materials, thin film technologies, large area electronics for displays and energy conversion, flexible electronics, and more recently "plastronics", for the most known ones. Specific training on technological platforms are thus created and introduced in the menu of the users.

Concrete examples of innovative practice realized in the centers

With more than 80 new platforms set up in the twelve microelectronic centers of the network since 2012, several training activities are described below. Figure 6 shows a selection of achievements designed, manufactured and tested by students as part of their initial training or of advanced training. These are mainly master of engineering students but also PhD students in further training, or employees of companies in LLL.

For each achievement, the microelectronics center is mentioned in the figure.

The diversity of the topics is shown: from integrated devices in bulk silicon technology to silicon thin film transistors for displays, sensors or actuators [START_REF] Bonnaud | New Approach for Sensors and Connecting Objects Involving Microelectronic Multidisciplinarity for a Wide Spectrum of Applications[END_REF], flexible electronics or radiofrequency circuits, and three dimension electronic on plastic (called "plastronics", for example [START_REF]Progress in the manufacturing of molded interconnected devices by 3D Microcontact Printing[END_REF]). Many other examples are available on the website of GIP-CNFM [START_REF] Cnfm | Coordination Nationale pour la formation en Microélectronique and nanotechnologies[END_REF]. The topics are mainly involved in the development of the connected objects and meet the industry needs.

Contribution of the network to the education of graduate students

The strategy of innovation is adopted by all the members of the network [START_REF] Bonnaud | Innovative practice in the French microelectronics education targeting the industrial needs[END_REF]. Since 2012, each year, new practice that can be suggested by the industry representatives are set-up and proposed to the user formations. The managers of these formations progressively introduce the new practice in their menus. Figure 7 shows the significant growth of the innovative practice during the seven past years. The growth slope is close to 1,000/year. One can notice that the most significant component of this growth is generated by other disciplines that are more and more attracted by the multidisciplinary approach of the microelectronics field. For example, mechanicians are concerned by the MEMS, whereas biologists and medical specialists by the BioMEMS.

Conclusion

The societal evolution is definitely oriented towards the digital world with connected objects and IoT that can respond to many societal challenges such as health, environment, security, transport or energy. The training of students must meet the needs of the company by providing knowledge and know-how adapted to these future challenges. Because microelectronics is at the heart of all new objects, it is very important, on the one hand, to prepare these specialists for the specificities of this field, and on the other hand, to raise awareness among a wider community of students from other disciplines in order to be better prepared to team working in the multidisciplinary approach to potential applications. Moreover, the tools used in the field of microelectronics and its applications are becoming so complex and expensive that the most realistic solution for training in know-how, which is compulsory, is to pool infrastructure, software, and operating resources. This approach adopted by the French microelectronics network makes it possible, on the one hand, to minimize the cost and, on the other hand, to train future graduates on efficient, recent and, if possible, implemented tools in companies. This guarantees a good adaptation of training to the labor market, a good matching between training structures and companies, and thus ensures a professional future for graduates.

Fig. 4 .

 4 Fig. 4. Relative importance of microelectronics activities for developing future objects in the global activities. The amplifying ration is close to 16 (After G. Matheron [10], with updating in 2017).

Fig. 5 .

 5 Fig. 5. French academic and industrial activities in microelectronics. The 12 CNFM common centers (red labels) manage platforms for practice training.

Fig. 6 .

 6 Fig. 6. Selection of achievements made by the students on the training platforms. The type of training and the name of the center are mentioned in each picture. The diversity of topics is great. Many other examples are available on the CNFM network's website [1].

Fig. 7 .

 7 Fig. 7. Evolution from 2011 to 2018 of the number of users in the twelve common centers of the CNFM network on innovative practice platforms. It is clear that the initial training is much more concerned.

Acknowledgment

The author wants to thank all the members of the French GIP-CNFM network for they contribution to this work, which is financially supported by French Education Ministry and by IDEFI-FINMINA program. A special thanks to L. Chagoya-Garzon, secretary of GIP-CNFM for her fruitful advice for the redaction of this paper.


Kaveh Khoshkhah
email: kavehkho@ut.ee

Khosravian Mehdi
email: m.khosravian@gmail.com

Jérôme Ghadikolaei

Dirk Oliver Monnot

Theis

Mehdi Khosravian Ghadikolaei

Jérôme Monnot
email: jerome.monnot@dauphine.fr

Dirk Oliver Theis
email: dotheis@ut.ee

Complexity and Approximability of Extended Spanning Star Forest Problems in General and Complete Graphs

Keywords: Computational complexity, Parameterized complexity, Approximation algorithms, Graphs, Extended solution, Spanning Star Forest

published or not. The documents may come

L'archive ouverte

Introduction

In [START_REF] Agra | A spanning star forest model for the diversity problem in automobile industry[END_REF], a diversity problem with application in the automobile industry is introduced. Here, each node corresponds to a cable configuration u (cable with a set of active option connections) and the cost w u,v between nodes u and v means that the cable configuration v will be supplied by the cable configuration u. In this application, a decision maker wishes to produce a set of cable configurations of minimum global cost under the constraint, that only configurations in the form of node-disjoint directed trees of depth at most 1 are feasible. In other words, the feasible solutions of this problem are directed spanning star forests; also called spanning star branchings. Several generalizations of this problem known as Carpooling problems have been studied in the literature (see the survey on ride-sharing [START_REF] Niels | Optimization for dynamic ride-sharing: A review[END_REF]). One of them, called Maximum Carpool Matching models an automatic service to match commuting trips between passengers and drivers [START_REF] Ben-Arroyo Hartman | Theory and practice in large carpooling problems[END_REF][START_REF] Kutiel | Approximation algorithms for the maximum carpool matching problem[END_REF]. In this case, new constraints are added: each star has an upper bound on its size. These bounds may be different for each potential driver and they represent the capacity of the car according to the number of passengers each user can drive if she was selected as a driver. Sometimes it is convenient to enforce some option connections in scheduling plans for the diversity problem or preselect some drivers with passengers together in the carpool Matching problem (enforcing them may be desirable for reasons outside of the scope of the model itself). This corresponds to requiring some arcs to belong to any feasible collection of spanning star branchings. Motivated by scheduling or control networking applications [START_REF] Delbot | Graphs with Forbidden and Required Vertices[END_REF][START_REF] Fotakis | Conference program design with single-peaked and single-crossing preferences[END_REF][START_REF] Tuza | Graph colorings with local constraints -a survey[END_REF][START_REF] Weller | On residual approximation in solution extension problems[END_REF], this type of problem, which consists of extending partial solutions, has recently drawn attention of the research community.

The undirected maximization version of the spanning star forest problem also has several motivations in bioinformatics [START_REF] Chen | Improved approximation algorithms for the spanning star forest problem[END_REF][START_REF] He | Improved approximation for spanning star forest in dense graphs[END_REF][START_REF] Nguyen | Approximating the spanning star forest problem and its application to genomic sequence alignment[END_REF]. Subproblems involving extending partial solutions can be used as a subroutine to design approximation algorithms for the master problem. In particular, He and Liang in [START_REF] He | Improved approximation for spanning star forest in dense graphs[END_REF] define and solve the complementary partial dominating set problem.

Graph terminology and definitions

Throughout this paper, we consider edge-weighed undirected graphs G = (V, E) on n = |V | vertices and m = |E| edges without isolated vertices. Each edge e = uv ∈ E between vertices u and v is weighted by a non-negative weight w(e) ≥ 0; K n denotes the complete graph on n vertices; a split graph G = (L, R, E) is an undirected graph where the vertex set L∪R is decomposable into a clique L and a independent set R. The degree d G (v) of vertex v ∈ V in G is the number of edges incident to v. A star S ⊂ E of a graph G = (V, E) is a tree of G where at most one vertex has a degree greater than 1 or, equivalently, it is isomorphic to K 1,ℓ for some ℓ ≥ 0. The vertices of degree 1 (except the center when ℓ ≤ 1) are called leafs of the star while the remaining vertex is called center of the star. A ℓ-star is a star of ℓ leafs; when ℓ = 0, the star is called trivial and it is reduced to a single vertex (the center). A non-trivial spanning star forest S = ∪ r i=1 S i ⊆ E3 of G is a spanning forest into stars, that is, each S i is a non trivial star, V (S i )∩V (S j ) = ∅ and ∪ p i=1 V (S i ) = V . Hence in this paper, a spanning star forest of a graph G is a collection of node disjoint non trivial stars (without isolated vertices, i.e., K 1,0 ) that covers all vertices of G. A matching M ⊆ E is a subset of pairwise non-adjacent edges. A matching M of G is perfect if all vertices of G are covered by M . A claw is a K 1,3 . A Spanning Star Forest Problem is defined as follows: The first problem is the restriction of the second to U = ∅. Given an instance I = (G, w) of Spanning Star Forest Problem (resp., I = (G, w, U) of Extended Spanning Star Forest Problem), S * = {S * 1 , . . . , S * ℓ * } will be an optimal solution with stars S * i and value w(S * ) = opt SSF (I). The {0, 1}-Spanning Star Forest Problem is the restriction to binary weights w(e) ∈ {0, 1}. Notice that for general connected graphs G, one non-trivial spanning star forest4 containing U may not exists. For example consider G is a P 4 and U is the middle edge of G. However, for complete graphs with arbitrary set U, there always exists some spanning star forest containing U. For each of these problems, two possible goals will be considered in this paper: maximization and minimization. Hence, the Max Spanning Star Forest Problem consists of finding a spanning star forest S = {S 1 , . . . , S r } ⊆ E maximizing its weight. For instance, in Max {0, 1}-Spanning Star Forest Problem the size of a spanning star forest is the number of leaves in all its components. The goal in this case is to find the maximum-size spanning star forest of a given graph (induced by the edges of unit weight). From now, we assume the forced set U = M U ∪ S U is decomposed into a matching M U = {p i q i : i = 1, . . . , k ′ } of k ′ edges and a set S U = {F 1 , . . . , F k } of k vertex-disjoint stars with at least two leafs (c i will be the center of F i and C = {c 1 , . . . , c k } is the set of centers in S U ). An illustration of these definitions is depicted in Figure 1. Cost Function Variants In this paper, when the graphs are complete, we will consider variants of the problem according to the cost function w: One variant assumes that w is any non-negative integer weight function; another that w satisfies the c-relaxed triangle inequality. Mainly consider that the c-relaxed triangle inequality might be satisfied outside the subgraph induced by V (U), ie., inside V \ V (U) because the structure of feasible solutions are strongly constrained by subset U.

Spanning Star Forest Problem

c1 . . . c k p1 q1 . . . p k ′ q k ′ x1 x2 . . . xt

Definition 1 (c-relaxed triangle inequality).

For a fixed c > 1/2, a weight function w on K n satisfies the c-relaxed triangle inequality, if:

∀x, y, z ∈ V (K n ), w(x, y) ≤ c (w(x, z) + w(z, y)) (1)
The case c = 1 is usually called in the literature triangle inequality while for c ∈ (1/2; 1) it is called sharpened triangle inequality. Note that the extreme case c = 1/2 becomes trivial since all edges must have the same weight. A detailed motivation of the study of the Traveling Salesman problem satisfying sharpened triangle inequalities is given in [START_REF] Böckenhauer | Approximation algorithms for the TSP with sharpened triangle inequality[END_REF]. In the context of extended problems, Definition 1 leads to a new definition called the Extended c-relaxed triangle inequality: Definition 2 (Extended c-relaxed triangle inequality). For a fixed c ≥ 1, a weight function w on K n satisfies the extended c-relaxed triangle inequality, if:

(i) w(e) = 0 for e ∈ U;
(ii) for all {x, y, z} V (U), w satisfies the c-relaxed triangle inequality.

Condition (i) of Definition 2 refers to the discussion in [START_REF] Weller | On residual approximation in solution extension problems[END_REF] which argues that the "residue" part of a feasible solution S, i.e., the part given in S \ U, is the most important of the valuation. Another consequence of conditions (i) and (ii) concerns the valuation of w restricted to the subgraph induced by V (U) (except for edges of U): this function does not satisfy any specified property. The main reason is that they could never contribute in any spanning star forest containing U. Finally, the reason for assuming c ≥ 1 is that condition (ii) implies max{w(xz), w(yz)} ≤ c min{w(xz), w(yz)} when xy ∈ U and z / ∈ V (U).

Related work

The minimization version of Spanning Star Forest Problem, is well known by weighted upper edge cover problem. An edge cover of a connected graph G is a subset of edges which covers all vertices of G and given a weighted connected graph (G, w), the weighted edge cover problem consists of finding an edge cover S ⊆ E of G minimizing ρ w (G) = w(S) = ∑ e∈S w(e). This problem is polynomial-time solvable (see chapters 33 and 34 volume A of [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]).

Proposition 3. Min Spanning Star Forest Problem is polynomial-time solvable.

Proof. We essentially prove that this problem is equivalent to solve the weighted edge cover problem. Let I = (G, w) be an instance of the Min Spanning Star Forest Problem. Obviously, opt SSF (I) ≥ ρ w (G) because any spanning star forest is a particular edge cover. Conversely, there is an optimal edge cover S * ⊆ E of (G, w) (with value w(S * ) = ρ w (G)) which is a spanning star forest. Actually, otherwise a P 4 or a K 3 exists in the subgraph (V, S * ); in each case, an edge of the P 4 or the K 3 can be deleted without increasing the cost because the weights are non-negative.

The maximization version of Spanning Star Forest Problem, called here Max Star Forest Problem, in general graphs has been investigated intensively in recent years for unweighed graphs without isolated vertices. Usually, the input is an undirected connected graph (weighted or not) and trivial stars are allowed as part of a feasible spanning star forests. In [START_REF] Nguyen | Approximating the spanning star forest problem and its application to genomic sequence alignment[END_REF], an APXhardness proof with explicit non-approximability bound is proposed, together with a polynomial-time algorithms for trees. A combinatorial 0.6-approximation algorithm which mainly solves the dominating set problem is presented as well while better algorithms with approximation ratio 0.71 and 0.803 are given respectively in [START_REF] Chen | Improved approximation algorithms for the spanning star forest problem[END_REF] and [START_REF] Athanassopoulos | Energy-efficient communication in multi-interface wireless networks[END_REF]. In contrast, for edge weighted graphs with non-negative weights, few results are proposed in the literature. As indicated above, trivial stars (ie., isolated vertices) are allowed because we want to maximize the total weight of the stars. This requirement is equivalent to find a packing star forest (ie. a collection of vertex disjoint stars): a 0.5-approximation is given in [START_REF] Nguyen | Approximating the spanning star forest problem and its application to genomic sequence alignment[END_REF] (which is the best ratio obtained so far) and polynomial-time algorithms for special classes of graphs such as trees and cactus graphs are presented in [START_REF] Nguyen | Approximating the spanning star forest problem and its application to genomic sequence alignment[END_REF][START_REF] Viet | The maximum weight spanning star forest problem on cactus graphs[END_REF]. Negative approximation results are presented in [START_REF] Nguyen | Approximating the spanning star forest problem and its application to genomic sequence alignment[END_REF][START_REF] Chakrabarty | On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP[END_REF][START_REF] Chen | Improved approximation algorithms for the spanning star forest problem[END_REF]. For any ε > 0, the unweighted version (or equivalently the Max {0, 1}-Spanning Star Forest Problem) is hard to approximate within a factor of 545 546 + ε unless P=NP [START_REF] Nguyen | Approximating the spanning star forest problem and its application to genomic sequence alignment[END_REF]. The edge-weighted version is NP-hard to approximate within 10 11 + ε [START_REF] Chakrabarty | On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP[END_REF]. For the Maximum Carpool Matching problem, a 0.33-approximation algorithm and a 0.5-approximation algorithm for both the general problem and the unweighted variant are given in [START_REF] Kutiel | Approximation algorithms for the maximum carpool matching problem[END_REF]. To the best of our knowledge, the extended versions of both problems have not been studied in the literature.

As indicated in introduction, extending a partial solution into a feasible solution has been studied from a computational complexity for independent dominating set 5 , conference programs and coloration in [START_REF] Delbot | Graphs with Forbidden and Required Vertices[END_REF][START_REF] Fotakis | Conference program design with single-peaked and single-crossing preferences[END_REF][START_REF] Tuza | Graph colorings with local constraints -a survey[END_REF] respectively. Dealing with approximation algorithms with performance guarantee of NP-hard of optimization problems, results on extension problems are given in [START_REF] Delbot | Graphs with Forbidden and Required Vertices[END_REF][START_REF] Weller | On residual approximation in solution extension problems[END_REF] for several problems including vertex cover, connected vertex cover feedback vertex set, Steiner tree, max leaf and bin packing. For algorithms finding an optimal solution, it often does not matter whether we optimize the weight of whole solution S or the weight of the residue part S \ U . However, in the context of approximation algorithms, this difference may produce important modifications as for bin packing. It is the main reason explaining the works given in [START_REF] Weller | On residual approximation in solution extension problems[END_REF] where the authors define and propose the approx-imation classes FRAPX and RAPX capturing approximability of the residue. The residue approximation of a solution S is the approximation of w(S) -w(U).

In the conclusion of their paper [START_REF] Weller | On residual approximation in solution extension problems[END_REF], the authors elaborate that obtaining parameterized complexity results [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] of extension problems parameterized by |U| leads to challenging open problems.

Summary of results and orginization

We prove the following results in this paper. First, in Section 2 we show that for a given graph G = (V, E) and a packing of stars U ⊆ E, even deciding the existance of a spanning star forest containing U is a NP-hard problem. However, by introducing a dynamic programming algorithm for bounded tree-width graphs, we show that not only the decision version is decidable in polynomial time but also both Max\Min Extended Spanning Star Forest problems are solvable in polynomial time.

In Sections 3 and 4, we focused on complete graphs. Minimization version is studied in Section 3. A dichotomy result of the computational complexity is presented depending on parameter c of the (extended) c-relaxed triangle inequality (Theorems 10 and 13). Then, a parameterized complexity, which shows this version is FPT is given. Positive and negative approximation results conclude this section. In section 4, we focus on Max Extended Spanning Star Forest in complete graphs. We prove that, compared to the unextended version, the same positive approximation result is reached, while we strengthen the negative approximation result to hold even for the Max Extended {0, 1}-Spanning Star Forest Problem. Table 1 summarizes the results obtained in sections 3,4 on complete graphs.

w-general c-relaxed Extended c-relaxed Min Extended NP-hard NP-hard c > 1 NP-hard c > 1 Spanning Star inapproximable at all polynomial 1 2 ≤ c ≤ 1 polynomial c = 1
• V (G) = V (C) ∪ V (X ) where V (C) = {v j : c j ∈ C} and V (X ) = {v 0 i , v 1 i : i = 1, . . . , n}, • U = {v 0 i v 1 i : x i ∈ X } and let M = m ∪ j=1 ({v j v 1 i : x i ∈ c j } ∪ {v j v 0 i : ¬x i ∈ c j }). • E(G) = U ∪ M . It is clear that I ′ is built in polynomial-time.
Suppose that I is satisfiable and let T be a truth assignment of I. For each clause c j , we define f (j) as an index of a variable x f (j) which satisfies clause c j in T ; we build a spanning star forest S containing U as follows:

S = {v 1 f (j) v j : T (x i ) = true} ∪ {v 0 f (j) v j : T (x i ) = false} ∪ U .
Conversely, assume that S * is a spanning star forest containing U. So S * \ U are incident to at most one of v 0 i , v 1 i for each 1 ≤ i ≤ n. Hence, we can build a truth assignment T as follows: if

v j v 1 i ∈ S * , then T (x j ) = true and T (x i ) = false otherwise.
Concerning the result of Theorem 4 we can easily derive:

Corollary 5. Dec Extended Spanning Star Forest is NP-hard for general graphs of maximum degree 3 and even if the packing of non-trivial stars U makes a matching.

Proof. Instead of SAT, we start the reduction from 2-balanced 3-SAT, denoted (3, B2)-SAT. An instance of (3, B2)-SAT is given by a set C of clauses defined over a set X of variables such that each clause has exactly 3 literals and each variable appears 4 time in C, 2 twice positive and twice negative. Deciding weather an instance of (3, B2)-SAT is satisfiable is NP-complete [START_REF] Berman | Approximation hardness of short symmetric instances of MAX-3SAT[END_REF]. So, by considering the Corollary 5, we should focus on some instances which has always some feasible solutions for Max\Min Extended Spanning Star Forest. Since, there exists some feasible solution for the problem, in complete graphs with every arbitrary packing of stars U, thus in Sections 3,4 we will study both minimization and maximization versions of the problem on complete graphs. Here, we propose a polynomial algorithm with dynamic programming method for Max\Min Extended Spanning Star Forest for bounded treewidth graphs. Instead of operating an algorithm on the input graph, we should operate it on a non-unique representation of the original graph, called Tree Decomposition as described in [START_REF] Hans | Treewidth: Algorithmic techniques and results[END_REF] and [START_REF] Kloks | Treewidth: computations and approximations[END_REF]. A tree decomposition (TD) of the original graph G = (V, E), includes some bags B X ⊆ V which satisfies following conditions:

(i) ∪ x∈T D B x = V . (ii) ∀(uv) ∈ E, ∃x ∈ T D such that u, v ∈ B x . (iii) There is a path of bags containing v between B x and B y in T D if v ∈ B x ∩ B y .
The TD is converted easily into a nice tree decomposition (nice TD), to decrease the possible transactions between bags [START_REF] Kloks | Treewidth: computations and approximations[END_REF]. A TD is nice if every node x be one of the following types:

-Leaf: a node with no children,

|B x | = 1.
-Introduce: a node with one child y such that B x = B y ∪{v} for some v ∈ V .

-Forget: a node with one child y such that B x = B y \ {v} for some v ∈ V .

-Join: a node with two children y and z such that B x = B y = B z . Definition 6. For any vertex v ∈ V of a given graph G = (V, E) and a spanning star forest f , we assign a labeling of v as follows:

l f (v, G) :=      center if v is a center of a star in f, leaf if v is a leaf of a star in f, isolated if v is a single vertex in f.
Since both endpoints of each K 1,1 in the spanning star forest f can be center and leaf, one of them is labeled in arbitrary with center and the other with leaf . In the following, we propose a dynamic programming for Min Extended Spanning Star Forest problem. Definition 7. For a weighted graph G = (V, E, w), packing of stars U and a sub-labeling function l from S ⊆ V to {center, leaf, isolated}, the value of minimum extended spanning star forest of G such that satisfies l and is allowed to have isolated vertices in S is defined as follows:

F l S (G, U) := min f ∈ESSFI (G,U ) {w(f )|∀s ∈ S, l f (s, G) = l(s) and ∀s / ∈ S, l f (s, G) ̸ = isolated} ∪ {∞}.
(

) 2
Let T be a nice tree decomposition of G by rooted r. We note B x and V x vertices appearing in node x and vertices appearing in the subtree rooted at x respectively. Actually, the solution of Min Extended Spanning Star Forest of G is arrived from min l∈L F l r (G, U) where L is a family of sub-labeling on B r such that no vertex in B r is labeled with isolated. The computation progresses from leaves of T to the root r by postorder traversal and all valid sub-labeling of x are achieved by possible sub-labeling of it's children. For each node x of T , let

G x = G[V x ] and U x = G x [E(G x ) ∩ E(U)]. We need to calculate F l x (G x , U x
) for all valid sub-labeling l on B x for each node x in T . Since there are four different types of nodes in T , we propose four types of function F l x (G x , U x ) as follows:

•Leaf node Suppose that B x = {u} is a leaf in T . It is clear that |V x | = 1, G x =
u and the only valid sub-labeling is l(u) = isolated, so we have:

F l x (G x , U x ) = { 0 if l(u) = isolated, ∞ otherwise.

•Introduce node

Suppose that y is the only child of x in T and B x = B y ∪ {a}. The important thing here is the label of node a for all valid sub-labeling B x . Node a can accept all the three labels isolated, leaf and center :

if l(a) = isolated and node a is not in V (U § ), then by keeping all valid sublabeling on B y and adding a label "isolated" for node a we make some valid sub-labeling on B x . if l(a) = leaf , it means that node a is a leaf of a star s in G[V x ], so by considering the structure of TD, center of s has to be in B y . Every node b ∈ B y such that ab ∈ E and b has one of the labels {isolated, center} on B y can be a candidate for the center of s. if l(a) = center, it means that node a is a center of a star s in G[V x ], so by considering the structure of TD, all of its leaves must be appeared in B y . So every subset M of vertices with label isolated on B y such that M ⊆ N G (a) can be a candidate for leaves of s.

In addition, we have to consider in all above cases that whether node a ∈ V (U x ) or not. Thus based on the label of a in the valid sub-labeling l on B x , we consider following cases:

if l(a) = isolated, F l x (G x , U x ) := { F l ′ y (G y , U y ) if a / ∈ V (U x ) ∞ otherwise.
where

l ′ (v) = l(v) for each v ∈ B y . if l(a) = leaf , F l x (G x , U x ) :=          min l(b)=center,ab∈E(Gx) {F l ′ b y (G y , U y ) + w(ab), F l ′′ b y (G y , U y ) + w(ab)} if a / ∈ V (U x ) min l(b)=center,ab∈E(Ux) {F l ′ b y (G y , U y ) + w(ab), F l ′′ b y (G y , U y ) + w(ab)} if d Ux (a) = 1 ∞ if d Ux (a) > 1 where l ′ b (v) := l(v) for v ∈ B y \ {b} and is isolated when v = b and l ′′ b (v) := l(v) for v ∈ B y \ {b} and is center when v = b. if l(a) = center, let S = {v ∈ V x : l(v) = leaf and va ∈ E}, F l x (G x , U x ) :=        ∞ if S = ∅, ∞ if ∃b ∈ U x : ab ∈ E(U x ) and d Ux (b) > 1 min ∅̸ =M ⊆S,NU x (a)⊆M {F l ′ M y (G y , U y ) + ∑ v∈M w(av)} otherwise.
where

l ′ M (v) := isolated for every v ∈ M and equals l(v) if v ∈ B y \ M .

•Forget node

Suppose that y is the only child of x in T and B y = B x ∪ {a} for a / ∈ B x . Because of the structure of TD, we will not see again node a in other bags in the following of the algorithm. On the other hand, notice that the final solution does not contain any non-trivial stars (an isolated vertex). Hence, label a can not be isolated and all valid sub-labeling of B y with l(a) = isolated will be invalid on B x . Therefore, for each valid sub-labeling l on B x we have:

F l x (G x , U x ) := min{F l ′ y (G y , U y ), F l ′′ y (G y , U y )} where l ′ (v) = l ′′ (v) = l(v) for v ∈ B
x and l ′ (a) = center and l ′′ (a) = leaf .

•Join node

In the last case, suppose that y 1 and y 2 are children of x in T and B x = B y1 = B y2 . Since, in the Join node x, two subgraphs V y1 and V y2 will be merged then the two sub-labeling l 1 , l 2 defined on B y1 and B y2 respectively, have to be adapted to each other. For example, for a node v ∈ B x , with l 1 (v) = leaf and l 2 (v) = leaf does not lead to a valid sub-labeling for B x , because it makes a P 3 in G x . Thus, for each valid sub-labeling l on B x we have:

F l x (G x , U x ) := min <l1,l2>∈L {F l1 y1 (G y1 U y1 ) + F l2 y2 (G y2 , U y2 )} < l 1 , l 2 >∈ L iff      {l 1 (v), l 2 (v)} = {isolated, leaf } if l(v) = leaf, {l 1 (v), l 2 (v)} = {isolated, center} or {center} if l(v) = center, {l 1 (v), l 2 (v)} = {isolated} if l(v) = isolated.
Theorem 8. Min Extended Spanning Star Forest is solvable in polynomial time for bounded tree-width graphs.

Proof. Now, we show that our proposed algorithm gives the optimal solution of Min Extended Spanning Star Forest for a given weighted graph G = (V, E, w) and a packing of non-trivial stars U. We focus on recursive functions F and show that the algorithm for each node x of TD, calculate and stores the optimal solution of each valid sub-labeling of

B x on G[V x ].
Hence, in the last step of the algorithm, the optimal solution of each valid sub-labeling of B r on G = G[V r ] is achieved. Among these optimal solutions, one which does not contain the label isolated for all vertices in B r and has maximum amount of F , is the final solution of Min Extended Spanning Star Forest on (G, U). Here we show that how F obtains the amount of optimal solution for each types of node and for every labeling in TD.

If x is a Leaf node in TD, it is trivial. Assume that x is an Introduce node with B x = B y ∪ {a} and assume that the algorithm calculated and stored the optimal amount of F for all valid sub-labeling of B y on G[V y ]. Concerning the labeling for vertex a (center, leaf, isolated) and all valid sub-labellings of B y on G[V y ] and also by considering U x , we obtain optimal amount of F for all sub-labeling of B x on G[V x ]: If l(a) = isolated and vertex a isn't an endpoint of U x , then the amount of F isn't changed and if a ∈ V (U x ), since the final solution must contains U, the amount of F is ∞; If l(a) = leaf , the number of edges in U x incident to a can not be more than 1 and for other cases we can easily calculate the amount of F ; If l(a) = center, for every neighbor v of a, d Ux (v) ≤ 1 and also a must have some neighbors M with label leaf in B x which have label isolated in B y . For all of these cases we calculate the amount of F and store the labeling.

Suppose node x is Forget and parent of y in TD such that B x = B y \ {a}. Since vertex a will not be appeared in the following steps of the algorithm, then we don't consider the cases that label of vertex a was isolated among valid sublabeling of B y on G[V y ], but by considering other cases (when label of vertex a was leaf, center, we obtain optimal amount of function F for all valid sublabelings of

B x on G[V x ].
Now assume x is a Join node with two children y 1 and y 2 in TD such that B x = B y1 = B y2 . Suppose that the algorithm calculated and stored the optimal amount of F for all valid sub-labeling of B y1 and B y2 on G[V y1 ] and G[V y2 ] respectively. Recall that by construction of TD, V y1 ∩ V y2 = B x and also there is no edges between vertices of V y1 \ B x and V y2 \ B x in G. Hence, optimal amount of F for all valid sub-labelings of B x on G[V x ] is obtained by checking valid sub-labelings of B y1 and B y2 . A valid sub-labeling of B x does not contain three following cases:

1-there is a vertex v ∈ B x , with label leaf in B y1 and B y2 , 2-there is a vertex v ∈ B x , with label leaf in B y1 and label center in B y2 , 3-there is a vertex v ∈ B x , with label leaf in B y2 and label center in B y1 .

For all valid sub-labelings in B x we calculate optimal amounts of F .

Assuming that the size of tree-width of input graph is bounded by k. Since for each vertex v ∈ B x there are three labels, we have 3 k different labelings for each B x . Also by considering the calculating method of F for each node type, the worst case for time complexity happens for join nodes where we have to consider three different cases when l(u) = center and two different cases when l(u) = leaf for each u ∈ B x . Let z 1 (resp. z 2 , z 3 ) be the number of vertices with labeling center (resp., leaf, isolated) in B x for a join node x. All possible sub-labelings for B x where |B x | = k can be computed as follows:

∑ z1+z2+z3=k ( k z 1 , z 2 , z 3 ) .3 z1 .2 z2 .1 z3 = (1 + 2 + 3) k = 6 k (3)
Thus the time complexity of the algorithm is O * (6 k ).

By changing function F of the algorithm such that putting max instead of min and -∞ instead of ∞, we can solve Max Extended Spanning Star Forest.

Corollary 9. Max Extended Spanning Star

Forest is solvable in polynomial time for bounded tree-width graphs.

Min Extended spanning star forest in complete graphs

Let us start this section by a definition of a special transformation on weighted complete graphs, called H-extended procedure.

H-extended procedure In several parts of this section, we will consider the weighted graph I ′ = (H, w H ) built from an instance I = (K n , w, U) of the Min Extended Spanning Star Forest Problem where U = S U ∪ M U is a packing of nontrivial stars (see Figure 1). H = (V H , E H ) is a complete weighted split graph defined as follows:

• V H = X ∪ (R ∪ C) where X = V (K n ) \ V (U), C = {c 1 , . . . , c k } is the set of centers of starts in S U and R = {r 1 , . . . , r k ′ } is a set of vertices correspond- ing to stars in M U ;
• E H is the set of edges of a complete split graph where the left side is a complete graph on X, the right side is an independent set on R ∪ C and we have a complete bipartite graph between them; • w

H (uv) =      w(uv) if u, v / ∈ R ∪ C, u ̸ = v w(uv) if u / ∈ R ∪ C, v ∈ C min{w(up i ), w(uq i )} if u / ∈ R ∪ C, v = r i .
Figure 2 gives an illustration of the construction. The H-extended procedure transforms any subset F ⊆ E(H) into a subset F ′ ⊆ E(K n ) by adding U and replacing any edge xr i ∈ F by edge xp i if w(xr i ) = w(xp i ), else by xq i . Obviously, these two constructions (H and H-extension procedure) are done in polynomialtime. Figure 3 proposes an example of the H-extended procedure. We now prove that the extended version of Min Spanning Star Forest problem can be much harder than the unextended version even in complete graphs. Actually, we will give a dichotomy result depending on parameter c of the (extended) c-relaxed triangle inequality.

Theorem 10. Min Extended Spanning Star Forest problem in complete graphs is NP-hard for both c-and extended c-relaxed triangle inequality when c > 1.

Proof. Let c > 1 be a constant. For both cases, we propose a reduction similar to what we did in Theorem 4 and build an instance I ′ = (K 2n+m , w, U) of Min Extended Spanning Star Forest as follows:

• V (K 2n+m ) = V (C) ∪ V (X ) where V (C) = {v j : c j ∈ C} and V (X ) = {v 0 i , v 1 i : i = 1, . . . , n}, • U = {v 0 i v 1 i : x i ∈ X } and let M = m ∪ j=1 {v j v 1 i : x i ∈ c j } ∪ {v j v 0 i : ¬x i ∈ c j }.
It is clear that I ′ is built in polynomial-time. The weight function w is defined by, ∀xy ∈ E(K 2n+m ),

w(xy) =          0 if xy ∈ U, 1 if xy ∈ M, c if xy / ∈ M, x ∈ V (C), y ∈ V (X ), 2c otherwise.
We can easily verify that w satisfies the extended c-relaxed (and c-relaxed) triangle inequality. We claim that I is satisfiable if and only if opt SSF (I ′ ) ≤ m.

Suppose that I is satisfiable and let T be a truth assignment of I. For each clause c j , we define f (j) as an index of a variable x f (j) which satisfies clause c j in T ; we build a spanning star forest S containing U such that w(S) = ∑ e∈S w(e) = m as follows:

S = {v 1 f (j) v j : T (x i ) = true} ∪ {v 0 f (j) v j : T (x i ) = false} ∪ U.
Conversely, assume that S * is a spanning star forest containing U with w(S * ) = opt SSF (I ′ ) ≤ m. Since U is a matching of size n, and by construction of the weights, if S * contains ℓ edges of weights 2c, then w(S * ) ≥ 2cℓ + (m -2ℓ) = m -2ℓ(c -1) because these ℓ edges cover at most 2ℓ vertices of V (C) and the weight of any other edge is at least 1 (recall c > 1). Hence, we deduce ℓ = 0. Now, if S * contains ℓ ′ edges of weight c > 1, then these ℓ ′ edges cover exactly ℓ ′ vertices of V (C) and w(S * ) ≥ ℓ ′ c + (m -ℓ ′ ) > m, contradiction. Hence, S * only contains unit weights. We can build a truth assignment T as follows: if v j v 1 i ∈ S * , then T (x j ) = true and T (x i ) = false otherwise. Corollary 11. The Min Extended Spanning Star Forest Problem for general weight function w is not approximable at all unless P=NP.

Proof. Revisit the proof of Theorem 10 by replacing the weight of any edge e by w ′ (e) = 0 if e ∈ M and w ′ (e) = 1 otherwise. Now, this restriction becomes the Min Extended {0, 1}-Spanning Star Forest Problem and it is NPcomplete to distinguish between opt SSF (I ′ ) = 0 and opt SSF (I ′ ) > 0.

In the following, in order to get some positive results, we will use of the Min weighted lower-upper-cover problem which is defined as follows:

Min weighted lower-upper-cover problem Input: A weighted graph (V, E, w) and two non-negative integer functions a, b

on V such that ∀v ∈ V , 0 ≤ a(v) ≤ b(v) ≤ d G (v). Solution: A subset M ⊆ E such that the subgraph G M = (V, M ) induced by M satisfies a(v) ≤ d GM (v) ≤ b(v). Output: Minimizing w(M ) = ∑ e∈M w(

e).(if any)

The Min weighted lower-upper-cover problem is known to be solvable in polynomial-time (Theorem 35.2 Chapter 35 of Volume A in [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]). For an instance I = (G, w) of the Min weighted lower-upper-cover problem, opt LU C (I) denotes the value of an optimal solution. Proof. We only deal with the c-relaxed triangle inequality case, because the other case is simpler. Let c be a constant with 1/2 ≤ c ≤ 1. We solve Min Extended Spanning Star Forest Problem for the c-relaxed triangle inequality via the help of the Min weighted lower-upper-cover problem.

Let I = (K n , w, U) be an instance of the Min Extended Spanning Star Forest Problem where w satisfies the c-relaxed triangle inequality and U is a packing of stars. From I, we build an instance I ′ = (H, w H ) where H is a complete split graph which described in H-extended procedure. Moreover, we consider two functions a, b of the Min weighted lower-upper-cover problem as follows: 4 proposes an illustration of the construction. By construction of I ′ , an optimal lower-upper-cover with parameters a, b is {P 4 , C 3 }-free and then is an extended spanning star forest of I. Hence,

if v ∈ V H \ (R ∪ C), then a(v) = 1 and b(v) = 2. Otherwise, v ∈ R ∪ C and a(v) = 0 and b(v) = 1. Figure
c1 . . . c k p1 q1 . . . p k ′ q k ′ x1 x2 . . . xt I = (Kn, U, w) c1 . . . c k r1 . . . r k ′ x1 x2 . . . xt I ′ = (H = (VH , EH ), a, b) a(v) = 1 b(v) = 2 a(v) = 0 , b(v) = 1
opt LU C (I ′ ) ≥ opt SSF (I) (4)
Conversely, let S * be an optimal extended spanning star forest of I. The next property allows us to focus on spanning star forest claw U-free. Property 14. There is an optimal extended spanning star forest of I which is claw U-free.

Proof. Let S be an optimal extended spanning star forest. Assume S is not claw U-free and let S = {uv i : i = 1, 2, 3} be a claw not U-free with uv i / ∈ U for i = 1, 2. In particular, vertices v 1 and v 2 are not adjacent to U; hence, S * = (S \S)∪{v 1 v 2 , uv 3 } is an extended spanning star forest with w(S * ) ≤ w(S). By repeating this process, we get the expected result. Note that if c < 1, all optimal extended spanning star forests are indeed claw U-free.

Hence, we can assume that S * is claw U-free, and then it is a lower-upper-cover with parameters a, b of I ′ :

opt SSF (I) = w(S * ) ≥ w H (S * ) ≥ opt LU C (I ′ ) (5)
Inequalities ( 4) and ( 5) give the expected result.

We end this subsection by giving a parameterized complexity result depending on the number of forced edges. Proof. Let I = (K n , w, U) be an instance of the Min Extended Spanning Star Forest Problem where we recall that U = M U ∪ S U with M U = {p i q i : i = 1, . . . , k ′ } and S U = {F 1 , . . . , F k }. The set of centers is C = {c 1 , . . . , c k } where c i is the center of star F i . As in Theorem 13, we solve several instances I J of the Min weighted lower-upper-cover problem for each set J ⊆ {1, . . . , k ′ }. At the end, we return the solution minimizing w(S J ) = opt LU C (I J ) among all possible sets J, that is S = argmin J opt LU C (I J ) where opt LU C (I J ) is the optimal value of the Min weighted lower-upper-cover problem on instance I J .

Let I = (K n , w, U) be an instance of the Min Extended Spanning Star Forest Problem where U is a packing of stars. From I and a set J ⊆ {1, . . . , k ′ }, we built an instance I J = (H J , w) where H J = (V HJ , E HJ ) is a complete subgraph of K n and two functions a J , b J of the Min weighted lower-upper-cover problem as follows:

V HJ = (V (K n ) \ V (U))∪({p j : j ∈ J} ∪ {q j : j ∈ {1, . . . , k ′ } \ J} ∪ C). Finally, if v ∈ V (K n ) \ V (U), then a J (v) = 1 and b J (v) = d H J (v). Otherwise, for v ∈ {p j : j ∈ J}∪{q j : j ∈ {1, . . . , k ′ }\J}∪C, a J (v) = 0 and b J (v) = d HJ (v)
. Let S J be an optimal solution of the Min weighted lower-upper-cover problem on (I J , a J , b J ). Clearly, S J is a spanning star forest on I and by construction there exists J * such that w(S J * ) = w(S * ) = opt SSF (I). The complexity of the whole algorithm is O * (2

|M U | ) = O * (2 |U| ) and then Min Extended Spanning Star Forest Problem is FPT.
The second part of the proof is a direct consequence of Corollary 11 for the Min Extended {0, 1}-Spanning star forest problem and use the Exponential Time Hypothesis (ETH in short): ∃s > 0 such that 3-CNF-Sat with n variables cannot be solved in time O * (2 sn ) [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF].

From Corollary 11 and Theorem 13, we focus on the approximation of the Min Extended Spanning Star Forest Problem for both c-and extended c-relaxed triangle inequality. Hence, let c > 1 be a fixed constant. In algorithm Approx 1 we use optimal solution of the Min weighted lower-upper-cover problem as subroutine which is already explained in Theorem 13.

Algorithm 1: Approx 1

Input: I = (K n , w, U) where U is a packing of forced stars.

Output: A spanning star forest S of I containing U.

1 Build instance I ′ = (H, w H ) from I as is described in H-extended procedure, where H = (X, (R ∪ C), E H ) is a split complete graph; 2 Find an optimal solution S * H ⊆ E H of the Min weighted lower-upper-cover problem on (I ′ , a 1 , b 1 ) with a 1 (v) = 1 and b 1 (v) = d H (v) if v ∈ X, a 1 (v) = 0 and b 1 (v) = 1 for v ∈ R and a 1 (v) = 0 and b 1 (v) = d H (v) for v ∈ C; 3 Convert S *
H into S using the H-extended procedure; 4 Return S. Proof. Let I = (K n , w, U) be an instance of the Min Extended Spanning Star Forest Problem which satisfies the c-relaxed (resp., extended c-relaxed) triangle inequality. Clearly, for c > 1, a ρ-approximation algorithm for the case of extended c-relaxed triangle is also a ρ-approximation algorithm for the c-relaxed triangle. Hence, we will prove the correctness of Approx 1 only for the case that weight function satisfies extended c-relaxed triangle inequality. Considering the H-extended procedure which already explained in the beginning of Section 3, we have:

-S contains U and the degree of each vertex in S is at least 1, since a 1 (v) = 1 for v ∈ X. by the minimality and since b 1

(v) = 1 for v ∈ R, S is P 3 -free.
So S is a spanning star forest of K n containing U.

Let S * be an optimal spanning star forest on I, we show how we can convert S * into a claw U-free S H ⊆ E H which is also a feasible solution of the Min weighted lower-upper-cover problem on (I ′ , a 1 , b 1 ) by losing at most a factor c.

For each p i q i ∈ M U , let S * i is the star of S * containing edge p i q i ; wlog., assume that p i is the center of S * i , and L * i denotes the leafs of S * i except q i . If

|L * i | ≥ 2
(v) = 1 and b ′ (v) = d H (v) if v ∈ X and a 2 (v) = 0 and b 2 (v) = d H (v) for v ∈ R ∪ C; 3 Convert S *
H into S using the H-extended procedure; 4 for (each connected component F i of S with L i as leafs such that p i q i ∈ F i and L i ∩ {p i , q i } = ∅) do 5 Build two stars

S 1 i = {p i x : x ∈ (L i ∪ {q i })} and S 2 i = {q i x : x ∈ (L i ∪ {p i })}; 6 if w(S 1 i ) ≤ w(S 2 i ) then S ← (S \ F i ) ∪ S 1 i ; 7 else S ← (S \ F i ) ∪ S 2 i ; 8 Return S ← S.
By construction, each connected component F i of S with p i q i ∈ F i and L i ∩ {p i , q i } = ∅ has a diameter equals to 3 (some leafs are connected to p i while the others leafs are connected to q i ). The other connected components are stars. Hence, S is a spanning star forest of I. 4. of Approx 2 and wlog., assume that w(S 1 i ) ≤ w(S 2 i ) for all i ≤ ℓ. Hence, the spanning star forest S outputted by Approx 2 can be decomposed into S 1 1 , . . . , S 1 ℓ and S ′ where

S ′ = S \ ( ∪ ℓ i=1 F i )
. By construction and using the extended c-relaxed triangle inequality, we have:

2w(S 1 i ) ≤ w(S 1 i ) + w(S 2 i ) ≤ ∑ x∈Li w(p i x) + ∑ x∈Li w(q i x) ≤ ∑ x∈Li w(p i x) + w(q i x) ≤ ∑ x∈Li (c + 1) min{w(p i x), w(q i x)} ≤ (1 + c)w(F i ) (6)
Summing up inequality (6) for all i ≤ ℓ and adding twice w(S ′ ), we obtain:

2w(S) = 2w(S ′ ) + 2 ℓ ∑ i=1 w(S 1 i ) ≤ (1 + c)w(S ′ ) + (1 + c) ℓ ∑ i=1 w(F i ) ≤ (1 + c)w(S * H ) = (1 + c)opt LU C (I ′ )
Let S * be an optimal spanning star forest on I of value opt SSF (I); S * is a feasible lower upper cover on (H, a 2 , b 2 ). Hence, we deduce opt LU C (I ′ ) ≤ w(S * ) = opt SSF (I). The two last inequalities provide the expected result. [START_REF] Håstad | Some optimal inapproximability results[END_REF], we know, for every ϵ > 0, given a 3-SAT instance Φ it is NP-hard to distinguish between two following cases:

• (Yes-instance) There exist an assignment satisfying (1 -ϵ) fraction of the clauses in Φ. • (No-instance) No assignment satisfies more than ( 78 + ϵ) fraction of clauses in Φ.

ning Star Forest Problem is defined in general graphs (ie., not necessarily complete), and allowing trivial stars. This assumption is not restrictive because by completing the graph by weights 0, the two problems become equivalent. Moreover, by replacing the weights of required edges U by a large enough value, then Max Spanning Star Forest Problem and Extended Spanning Star Forest Problem are completely equivalent from a computational complexity point of view. However, these modifications affect the approximability of the problem. Hence, here we are interested in the hardest case which corresponds to w(e) = 0 for ∀e ∈ U. This means that the obtained results will be valid for the residual approximation [START_REF] Weller | On residual approximation in solution extension problems[END_REF]. Recall that

U = {U 1 , . . . , U r } = M U ∪ S U where r = k + k ′ , M U = {e i : i = 1, . . . , k ′ } is a matching of k ′ edges and S U = {F 1 , . . . , F k } is a set of k vertex-disjoint
S = {S 1 , . . . , S r } ⊆ E of G such that U i ⊆ S i . Output: Maximizing w(S) = ∑ e∈S w(e) = ∑ r i=1 ∑ e∈Si w(e).
Solving Extended Disjoint Spanning Forest is polynomial and use the same arguments that solving maximum weighted spanning tree.

Algorithm 3: Approx 3

Input: I = (Kn, w, U ) where U is a packing of forced stars. Output: A spanning star forest S of I containing U.

7 if w(S 1 i ) ≥ w(S 2 i ) then S ← S ∪ S 1 i ; 8 else S ← S ∪ S 2 i ;
Lemma 20. There is a linear-time algorithm that solves Extended Disjoint Spanning Forest.

Proof. The algorithm starts from U, sorts the edges by non increasing weights and iteratively adds edges satisfying condition U i ⊆ S i for all i ≤ r. The arguments of optimality are the standard ones and more generally are valid for matroid. We present them for sake of completeness. Consider a connected weighted graph I = (G, w) and let S * 1 be an optimal spanning forest S * 1 = {S * 1 , . . . , S * r } of G such that U i ⊆ S * i . Consider S 1 = {S 1 , . . . , S r } the solution returned by the greedy algorithm; let e ∈ S * 1 \ S 1 . The addition of e * to S 1 leads to either the creation of a cycle or the fusion of two subtrees S ℓ and S ℓ ′ . In any case, all edges of that cycle or the path between U ℓ and U ℓ ′ are larger or equals than w(e * ).

From I = (K n , w, U), we delete all edges xy / ∈ U with x ∈ L i for some i ≤ k and y ∈ V (K n ). Let G = (V, E) be the resulting connected graph and I ′ = (G, w, U) be the instance of Extended Disjoint Spanning Forest. Consider the Algorithm 3. Let us formally explain how solutions are built during Step 5. Here, U i ⊂ S * i ; first we root subtree S * i at the center of U i (if U i = {p i q i }, we root S * i at p i ). Then, we construct a first partial solution which consider edges of S * i \ U i with odd levels and another partial solution with even levels. At the end of this Step 5. we add edges of U i for both partial solutions. Figure 6 propose an illustration on the construction of the two spanning star forests (containing trivial stars at this stage) S 1 i and S 2 i of the induced subgraph (V, S * i ) according to the structure of U i . Theorem 21. Approx 3 is a 1 2 -approximation of Max Extended Spanning Star Forest Problem in complete graphs.

Proof. Let I = (K n , w, U) be an instance of the of the max Extended Spanning Star Forest Problem where w(x, y) ≥ 0 for all xy ∈ E(K n ). Consider a subtree S * i ̸ = U i of the optimal solution S * 1 found by Approx 3 for the Extended Disjoint Spanning Forest problem on instance (G, w). Clearly, either S * 1 \U i has two subtrees (one containing p i , the other containing q i ) and in this case U i = {p i q i } or S * 1 \U i remains a subtree. Wlog., assume w(S 1 i ) ≥ w(S 2 i ) (Step of Approx 3); hence, since S 1 i and S 2 i are two spanning star forests (with possibly containing trivial stars at this stage) such that S 1 i ∩ S 2 i = U i and S 1 i ∪ S 2 i = S * i , we get: ∀i ≤ r, 2w(S 1 i ) ≥ w(S 1 i ) + w(S 2 i ) ≥ w(S * i ) + w(U i ). By summing up inequality [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for all i ≤ ℓ (note this inequality also holds when S * i = U i ), and using w(e) ≥ 0, we obtain:

2w(S) ≥ r ∑ ℓ=1 w(S * i ) = w(S * 1 ) (10)
On the other hand, from an optimal spanning star forest S * containing U with a maximum value w(S * ) = opt SSF (I) and by adding n -r -|U| edges, we get particular feasible solution of Extended Disjoint Spanning Forest on I ′ = (G, w, U). Hence, because the weights are non-negative:

w(S * 1 ) ≥ opt SSF (I) (11)
Combining inequalities [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] and [START_REF] Fotakis | Conference program design with single-peaked and single-crossing preferences[END_REF] gives the result.

Setting w(e) = 0 for e ∈ U leads to the following corollary. [START_REF] Håstad | Some optimal inapproximability results[END_REF], we obtain the result.

Conclusion

In this article, we have studied two Max and Min Extended Spanning Star Forest Problems. We have shown both problems is solvable in polynomial time for bounded tree-width graphs while are N P -hard for general graphs. Moreover, We have studied both versions in complete graphs. For Min Extended Spanning Star Forest, we considered different types of weight function w for edges of input graphs. We have shown for general-w, the problem is not approximable at all but for c-relaxed and extended c-relaxed triangle, it is in RAPX. Moreover, we have shown the Min Extended Spanning Star Forest Problem parameterized by the cardinality of U is in FPT. Furthermore, we proved Max Extended Spanning Star Forest Problem is in RAPX for general-w. It would be interesting to study parameterized complexity of the maximizing version with respect to the cardinality of U on the future.

  Input: A weighted graph (G, w) where G = (V, E) and w(e) ≥ 0 for e ∈ E. Solution: Non-trivial spanning star forest S = {S 1 , . . . , S p } ⊆ E. Output: Optimizing w(S) = ∑ e∈S w(e) = ∑ p i=1 ∑ e∈Si w(e). The extended version of the Spanning Star Forest Problem, called Extended Spanning Star Forest Problem consists of extending a given packing of stars into a spanning star forest. Formally, we have: Extended Spanning Star Forest problem Input: A weighted graph (G, w) and a packing of non-trivial stars U = {U 1 , . . . , U r } where G = (V, E) and w(e) ≥ 0 for e ∈ E. Solution: Non-trivial spanning star forest S = {S 1 , . . . , S p } ⊆ E containing U. Output: Optimizing w(S) = ∑ e∈S w(e) = ∑ p i=1 ∑ e∈Si w(e).

Fig. 1 .

 1 Fig. 1. Bold Edges corresponds to forced edges of U: sets SU and MU are indicated to the left and to the right of the figure respectively. Set X = {x1, ..., xt} are the vertices of the graph, out of U .

Fig. 2 .

 2 Fig. 2. Illustration of the construction of the split graph H = (X, (C ∪ R), EH ).

Fig. 3 .

 3 Fig. 3. H-extended procedure. Bold edges are in U.

Definition 12 .Theorem 13 .

 1213 Let I = (K n , w, U) be an instance of Min Extended Spanning Star Forest Problem. Solution S is called claw U-free if for each claw F = K 1,3 subset of S, at least two edges of the claw F belongs to U, i.e. |F ∩ U| ≥ 2. Min Extended spanning star forest problem in complete graphs is solvable in polynomial-time for the c-relaxed triangle inequality when 1/2 ≤ c ≤ 1 and the extended c-relaxed triangle inequality when c = 1.

Fig. 4 .

 4 Fig. 4. An instance I of the Min weighted lower-upper-cover problem is shown on the right hand. Bold edges are in U.

Theorem 15 .

 15 Min Extended Spanning Star Forest Problem in complete graphs, parameterized by |U| is FPT and under ETH, Min Extended Spanning Star Forest Problem cannot be solved in time O * (2 s|U | ) for some s > 0.

Theorem 16 .

 16 Approx 1 is a c-approximation of Min Extended Spanning Star Forest Problem in complete graphs for both c-and extended c-relaxed triangle inequality.

Figure 5 2 iFig. 5 .

 525 Fig. 5. Illustration of construction of stars S 1 i and S 2 i from Fi. Bold edges are in U .

Fig. 6 .

 6 Fig. 6. Construction of solutions S 1i and S 2 i depending on S * i contains piqi (case (b)) or not (case (a)); bold edges are in Ui. For each case both solutions S 1 i and S 2 i are indicated (at this stage, trivial stars are allowed).

Table 1 .

 1 The results given for complete graphs

	Forest	in FPT parameterized by	in RAPX with c apx-ratio in RAPX with c+1 2	apx-
		|U |			ratio
			inapproximable	with	inapproximable with 7+c 8 -
			7+c 8 -ϵ		ϵ
	Max Extended in RAPX with 1 2 apx-ratio
	Spanning Star inapproximable within 7 8 +	-		-
		ϵ

2 Max\Min Extended Spanning Star Forest in general graphs

First of all, let us give a NP-hardness proof for decision problem Dec Extended Spanning Star Forest which is defined as follows: Dec Extended Spanning Star Forest Input: A graph G = (V, E) and a packing of non trivial stars U ⊆ E. Question: Does G admit a non-trivial spanning star forest containing U? Theorem 4. Dec Extended Spanning Star Forest is NP-hard for general graphs even if U makes a matching in G.

Proof. We propose a simple reduction from SAT to the Dec Extended Spanning Star Forest problem. SAT is an NP-complete problem

[START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]

which consists of deciding if an instance I = (C, X ) of SAT is satisfiable. Here, C = {c 1 , . . . , c m } and X = {x 1 , . . . , x n } are the set of clauses and variables respectively; a variable x i which appears negatively will be denoted ¬x i . From I = (C, X ), we build an instance I ′ = (G, U) of Dec Extended Spanning Star Forest Problem as follows:

  and x, y ∈ L * i are two distinct leafs, we replace edges p i x and p i y of S * i by two stars S * i \ {p i x, p i y} and {xy}. By repeating this process until the star S * i (containing p i q i ) satisfy |L * i | ≤ 1 for each p i q i ∈ M U , we obtain a packing of stars S ′ i such that w(S ′ i ) ≤ c.w(S * i ) since w(xy) ≤ c (w(p i x) + w(p i y)). By summing up these inequalities for all such stars, at the end we get a spanning star forest S H (which is the union of S ′ i ) with w(S H ) ≤ c.w(S * ) = c.opt SSF (I). This spanning star forest S H is by construction a feasible lower-upper-cover of (H, w H ) with parameters (a 1 , b 1 ). In conclusion, w(S) = w(S * H ) ≤ w(S H ) ≤ c × w(S * ). Corollary 17. For complete graphs, Min Extended Spanning Star Forest Problem is in RAPX for both c-and extended c-relaxed triangle inequality.Proof. Using the proof of Theorem 16 and the extended c-relaxed triangle inequality, we deduce that Approx 1 is a residue c-approximation[START_REF] Weller | On residual approximation in solution extension problems[END_REF]. Input: I = (K n , w, U) where U is a packing of forced stars. Build instance I ′ = (H, w H ) from I as is described in H-extended procedure, where H = (X, (R ∪ C), E H ) is a split complete graph; 2 Find an optimal solution S * H ⊆ E H of the Min weighted lower-upper-cover problem on (I ′ , a 2 , b 2 ) with a 2

	Algorithm 2: Approx 2

Output: A spanning star forest S of I containing U.

1

Theorem 19 .

 19 For any ϵ > 0 it is NP-hard to approximate and residue approximate the Min Extended Spanning Star Forest Problem in complete graphs within 7+c 8 -ϵ for both c and extended c-relaxed triangle inequalities. Proof. Let Φ be an instance of Max 3-SAT with variable set X = {x 1 , . . . , x n } and clause set C = {c 1 , . . . , c m }. W.l.o.g., assume m > n (otherwise, we duplicate the clauses c 1 , . . . , c m till m > n). Using the result of

  stars with at least two leafs each. The set of centers is C = {c 1 , . . . , c k } and L i are the leafs of F i . We study an intermediary problem called here Extended Disjoint Spanning Forest because it will provide an upper bound of our problem:Extended Disjoint Spanning Forest Input: A weighted connected graph (G, w) and a packing of non trivial stars U = {U 1 , . . . , U r }.

Solution: Spanning forest

  Corollary 22. Max Extended Spanning Star Forest Problem in complete graphs is in RAPX. For any ϵ > 0 it is NP-hard to approximate and residue approximate Max Extended Spanning Star Forest Problem in complete graphs within 7 8 + ϵ. Proof. The reduction given in Corollary 11 is indeed a reduction preserving approximation from 3-SAT to Max Extended {0, 1}-Spanning Star Forest Problem. Hence, using

	Theorem 23.

By abuse of notations, we write S = {S1, . . . , Sr} ⊆ E.

To simplify the notations, most of the time, we speak about spanning star forest instead of non-trivial spanning star forest.

In this case, it is also required that some vertices are forbidden.

Complete S into a spanning star forest by connecting each isolated vertex to some center;

Return S ← S.

Acknowledgments. Many thanks to the anonymous referee and the anonymous associate editor for pertinent and useful comments and suggestions.

Let ε > 0 and consider the reduction given in Theorem 10 for instances I Φ satisfying both c and extended c-relaxed triangle inequalities when c > 1. Recall that w(xy) =

Completeness: Suppose there is an assignment of variables {x 1 , . . . , x n } which satisfies (1 -ϵ) fraction of clauses (i.e., a Yes-instance). We build a spanning star forest S of n stars containing U as follows: Suppose T (Φ) is an assignment satisfies (1 -ϵ)m clauses C ′ = {c 1 , . . . , c (1-ϵ)m }. We start the construction of these n stars with total weight (1 -ϵ)m by taking the matching {p i q i : i = 1, . . . , n} and by connecting one vertex of each M U to some vertices v i corresponding to clauses of C ′ ; then we complete these n stars into a stars spanning by connecting arbitrarily the ϵm remaining vertices (corresponding to other clauses which are not satisfied) to some centers. Hence, S is a spanning star forest which contain U with w(S) = (1 -ϵ)m + cϵm, thus we have:

Soundness: Consider an optimal spanning star forest S * of I Φ with value opt SSF (I Φ ). Clearly, for each 1 ≤ i ≤ n, at least one vertex of {v 0 i , v 1 i } is s a leaf of the star S * i of S * . From S * we build a truth assignment T for Φ as follows:

i , then clause c j is satisfied by assignment T . Hence, the total weight of S * is: opt SSF (I Φ ) ≥ |{c j : c j is satisfied}| + c|{c j : c j is not satisfied}| Furthermore, if at most ( 78 + ϵ)m clauses are satisfied in Φ, the weight of opt SSF (I Φ ) is at least:

The completeness and soundness arguments imply that it is NP-hard to distinguish whether instance I Φ has a spanning star forest with weight at least m(1 -ϵ + cϵ) or at most m( 7 8 + ϵ + 1 8 c -cϵ). Therefore, we can conclude that it is NP-hard to approximate the Min Extended Spanning Star Forest Problem within factor:

By picking a small enough ϵ, we get the expected result.

Max Extended spanning star forest in complete graphs

Now, we study the maximization case when the weight function w is general, but non-negative and the graph is complete. Usually (see Subsection 1.2), the Span-