标题： 包含与排斥顶点分割到特定图类：NP难性与算法 显示英文标题

标题： Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms

摘要： 我们研究了一类称为F-顶点分裂的问题的图修改问题。 给定一个图G，任务是确定是否可以通过最多k次顶点分裂将G转换为属于图类F的图G'。 我们针对几个目标图类进行了研究，即星形图、环图、线性森林和二部图。 我们分析了顶点分裂的包含型和排除型变体，如Abu-Khzam及其合作者（ISCO 2018）所引入的。 我们的结果表明，当F是环图或线性森林时，对于两种变体，F-顶点分裂问题都可以在多项式时间内求解。 相反，当F是星形图或二部图时，对于两种变体，该问题都是NP完全的。 显示英文摘要

摘要： We study a family of graph modification problems called the F-Vertex Splitting problem. Given a graph G, the task is to determine whether G can be transformed into a graph G-prime belonging to a graph class F through a sequence of at most k vertex splits. We investigate this problem for several target graph classes, namely constellations, cycle graphs, linear forests, and bipartite graphs. We analyze both inclusive and exclusive variants of vertex splitting, as introduced by Abu-Khzam and collaborators (ISCO 2018). Our results show that the F-Vertex Splitting problem is polynomial-time solvable when F is a cycle graph or a linear forest, for both variants. In contrast, when F is a constellation or a bipartite graph, the problem is NP-complete for both variants.