pith. sign in

arxiv: 1901.02491 · v1 · pith:XHBXH2BYnew · submitted 2019-01-08 · 💻 cs.DS

Faster parameterized algorithm for pumpkin vertex deletion set

classification 💻 cs.DS
keywords algorithmpumpkinvertexcommondirectedgraphpathsvertices
0
0 comments X
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.