Hitting and Harvesting Pumpkins

Details Hitting and Harvesting Pumpkins Hitting and Harvesting Pumpkins

2011-05-13

arxiv.org/abs/1105.2704v1

Computer Science

Data Structures and Algorithms

27 pages, 6 figures

Scientific paper

The "c-pumpkin" is the graph with two vertices linked by c>0 parallel edges. A c-pumpkin-model in a graph G is a pair A,B of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on covering and packing c-pumpkin-models in a given graph: On the one hand, we provide an FPT algorithm running in time 2^O(k) n^O(1) deciding, for any fixed c>0, whether all c-pumpkin-models can be covered by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex Set, which correspond to the cases c=1,2 respectively. On the other hand, we present a O(log n)-approximation algorithm for both the problems of covering all c-pumpkin-models with a smallest number of vertices, and packing a maximum number of vertex-disjoint c-pumpkin-models.

Affiliated with

Also associated with

No associations

Rating

Hitting and Harvesting Pumpkins does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hitting and Harvesting Pumpkins, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hitting and Harvesting Pumpkins will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-27274