Answers are grounded in this paper and cite their sources.
We define a set $P$ to be a \emph{branching $k$-path vertex cover} of an undirected forest $F$ if all leaves and isolated vertices (vertices of degree at most $1$) of $F$ belong to $P$ and every path
We define a set P to be a branching k-path vertex cover of an undirected forest F if all leaves and isolated vertices (vertices of degree at most $1$) of F belong to P and every path on k vertices (of length $k-1$) contains either a branching vertex (a vertex of degree at least $3$) or a vertex belonging to P. We define the branching k-path vertex cover number of an undirected forest F, denoted by ψb(F,k), to be the number of vertices in the smallest branching k-path vertex cover of F. These notions for a rooted directed forest are defined similarly, with natural adjustments. We prove the lower bound ψb(F,k) ≥ n+3k-1/2k for undirected forests, the lower bound ψb(F,k) ≥ n+k/2k for rooted directed forests, and that both of them are tight.
No takes yet. Share an insight, caveat, or question.
Mikhail Makarov (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: