betaFeedback

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 ℓ\ell-shallow splitting, where each original vertex has at most ℓ+1\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 ℓ=2\ell=2. These algorithms are complemented by NP-hardness for every fixed ℓ≥3\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 ℓ=1\ell=1 and are NP-hard for every fixed ℓ≥2\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.

Paper details

vlnc:W_mz9wzbwz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…