Establishing hereditary graph properties via vertex splitting

Abstract

We examine the Π-Vertex Splitting problem, which consists of determining if a given graph can be transformed into a member of a fixed graph class Π using at most k vertex splits. A vertex split is a graph modification that replaces a vertex v with two new vertices, v_1 and v_2, and assigns each edge previously incident to v to either v_1, v_2, or both. We present polynomial-time algorithms for Forest-, Split-, and Threshold-Vertex Splitting, but show that Π-Vertex Splitting is NP-complete for various hereditary graph classes, including cluster graphs, bipartite graphs, perfect graphs, graphs free of finite sets of (induced) cycles, graphs free of a single biconnected forbidden (induced) subgraph, graphs free of a set of triconnected forbidden (induced) subgraphs with bounded diameter, and graphs free of a set of 4-connected forbidden (induced) subgraphs. Furthermore, we provide a dichotomy regarding the classical complexity of Π-Vertex Splitting for graph classes characterized by sets of forbidden induced subgraphs, each containing no more than three vertices. For each such class Π, we either demonstrate that Π-Vertex Splitting is in P, or show that the problem is NP-complete. Lastly, we investigate the parameterized complexity of Π-Vertex Splitting with respect to the number of splits as the parameter. We demonstrate that Triangle-Free Vertex Splitting is para-NP-hard, which implies that for Π characterized by a finite set of forbidden induced subgraphs, Π-Vertex Splitting is in general not fixed-parameter tractable. However, we obtain a linear kernel for Cluster Vertex Splitting.