Answers are grounded in this paper and cite their sources.
Investigates computational complexity of hereditary graph properties through vertex splitting, suggesting new pathways for analysis.
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 ). 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.
No takes yet. Share an insight, caveat, or question.
Firbas et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: