2026-07-23T08:46:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22157 2024-12-04T06:53:44Z ddc:004 open_access

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting Firbas, Alexander Sorge, Manuel NP-completeness polynomial-time solvability graph theory graph transformation graph modification 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 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 subgraph and prescribed vertex splits that satisfy certain conditions. Using this framework we show NP-completeness when Π is characterized by sufficiently well-connected forbidden subgraphs. In particular, we show that F-Free-VS is NP-complete for each biconnected graph F. Third, we study infinite families of forbidden 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 K₃-Free-VS 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Firbas and Manuel Sorge 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.30 urn:nbn:de:0030-drops-221572 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.30 eng https://creativecommons.org/licenses/by/4.0/legalcode