arXiv preprint ·
Matroid Parity Meets Vertex Splitting
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
A vertex split replaces a vertex by two non-adjacent descendants and partitions its incident edges between them. We study exclusive $\ell$-shallow splitting, where each original vertex has at most $\ell+1$ 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 $\ell=2$. These algorithms are complemented by NP-hardness for every fixed $\ell\ge3$; 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 $\ell$, using matroid intersection. For cluster graphs, both objectives admit linear-time algorithms when $\ell=1$ and are NP-hard for every fixed $\ell\ge2$. Together, these results identify how the target class, the local splitting bound, and the choice of objective determine the complexity of vertex splitting.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Multi-seed information diffusion with varying reproduction
Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$
Speed-Robust Scheduling for Total Completion Time
Color Refinement Distinguishes Connected Rooted Outerplanar Graphs
An Optimal Online Algorithm for Single-machine Scheduling with Two Agents
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.