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 (Π), \textsc{(Π)-Vertex Splitting} 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 \textsc{Cograph Vertex Splitting} is \textsf{NP}-complete, even on graphs of girth at least 5, resolving a question…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.13517
curl -X POST /api/v1/records/arxiv/2607.13517/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.13517/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'