Complexity and approximability of extended Spanning Star Forest problems in general and complete graphs

作     者：Khoshkhah, Kaveh Ghadikolaei, Mehdi Khosravian Monnot, Jerome Theis, Dirk Oliver 

作者机构：Tartu Univ Inst Comp Sci Tartu Estonia Univ Paris 09 PSL Res Univ CNRS UMR 7243 LAMSADE F-75016 Paris France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2019年第775卷

页      面：1-15页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Estonian Research Council (PUT Exploratory Grant) DORA Plus scholarship of the Archimedes Foundation - (European Regional Development Fund) 

主　　题：Computational complexity Parameterized complexity Approximation algorithms Graphs Extended solution Spanning Star Forest 

摘      要：A solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP-hardness, parameterized complexity, positive and negative approximation results. (C) 2018 Elsevier B.V. All rights reserved.