Hardness of Vertex Splitting: Cographs, Chordal Graphs, and Beyond

Vertex splitting replaces a vertex (v) by two nonadjacent vertices whose neighborhoods together equal (N(v)). A split is \emph{exclusive} if these neighborhoods are disjoint and \emph{shallow} if no newly created vertex is split again. For a graph property (Π), $\text{textsc}(\mathrm{\Pi })-VertexSplitting$ asks whether at most (k) splits can transform a graph (G) into one satisfying (Π). We continue the systematic study of this operation and settle several open problems. First, we prove that $\text{textsc}CographVertexSplitting$ is $\mathsf{\text{NP}}$-complete, even on graphs of girth at least 5, resolving a question of Firbas and Sorge (ISAAC 2024). More generally, $\text{textsc}(P_t)-freeVertexSplitting$ is $\mathsf{\text{NP}}$-complete for every fixed (t\geq 4). We also prove that $\text{textsc}ChordalVertexSplitting$ and $\text{textsc}Unit-IntervalVertexSplitting$ are $\mathsf{\text{NP}}$-complete, resolving two questions of Abu-Khzam, Chakraborty, Isenmann, and Oijid (IWOCA 2026). Our hardness results extend to the exclusive and shallow variants. Assuming the Exponential Time Hypothesis, none of these problems admits an algorithm running in (2^{o(k)}n^{O(1)}) time; moreover, except for the unit-interval cases, none admits an algorithm running in (2^{o(n)}) time.