Faster parameterized algorithm for pumpkin vertex deletion set
classification
💻 cs.DS
keywords
algorithmpumpkinvertexcommondirectedgraphpathsvertices
read the original abstract
A directed graph $G$ is called a pumpkin if $G$ is a union of induced paths with a common start vertex $s$ and a common end vertex $t$, and the internal vertices of every two paths are disjoint. We give an algorithm that given a directed graph $G$ and an integer $k$, decides whether a pumpkin can be obtained from $G$ by deleting at most $k$ vertices. The algorithm runs in $O^*(2^k)$ time.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.