On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting

Vertex splitting is a graph operation that replaces a vertex v with two nonadjacent new vertices u , w and makes each neighbor of v adjacent with one or both of u or w . Vertex splitting has been used in contexts from circuit design to statistical analysis. In this work, we generalize from specific vertex-splitting problems and systematically explore the computational complexity of achieving a given graph property Π by a limited number of vertex splits, formalized as the problem Π Vertex Splitting ( Π -VS ). We focus on hereditary graph properties and contribute four groups of results: First, we classify the classical complexity of Π -VS for graph properties characterized by forbidden induced subgraphs of order at most 3. Second, we provide a framework that allows one to show NP-completeness whenever one can construct a combination of a forbidden (induced) subgraph and prescribed vertex splits that satisfy certain conditions. Using this framework we show NP-completeness when Π is characterized by sufficiently well-connected forbidden (induced) subgraphs. In particular, we show that F -Free-VS is NP-complete for each biconnected graph F , both as a forbidden induced subgraph and as a forbidden subgraph. Third, we study infinite families of forbidden induced subgraphs, obtaining NP-completeness for Bipartite-VS and Perfect-VS, contrasting the known result that Π -VS is in P if Π is the set of all cycles. Finally, we contribute to the study of the parameterized complexity of Π -VS with respect to the number of allowed splits. We show para-NP-hardness for Triangle-Free Vertex Splitting and derive an XP-algorithm when each vertex is only allowed to be split at most once, showing that the ability to split a vertex more than once is a key driver of the problems’ complexity.