WorksComputer Science
Matroid Parity Meets Vertex Splitting
Abstract
A vertex split replaces a vertex by two non-adjacent descendants and partitions its incident edges between them. We study exclusive -shallow splitting, where each original vertex has at most descendants, with the aim of obtaining a forest, a pseudoforest, or a cluster graph. We consider two natural objectives: minimizing the total number of split operations and minimizing the number of original vertices that are split. Our main conceptual contribution is a connection between vertex splitting and matroid parity. For both forests and pseudoforests, we give a characterization of feasible splitting sequences that leads, via weighted linear matroid parity, to polynomial-time algorithms for minimizing the number of split vertices when . These algorithms are complemented by NP-hardness for every fixed ; for pseudoforests, hardness holds even on graphs of maximum degree four. The total number of split operations behaves differently: for both sparse target classes, this objective is polynomial-time solvable for every , using matroid intersection. For cluster graphs, both objectives admit linear-time algorithms when and are NP-hard for every fixed . Together, these results identify how the target class, the local splitting bound, and the choice of objective determine the complexity of vertex splitting.