דקל צור

A directed graph G is called a pumpkin if G is a union of induced directed 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.