Kernel Bounds for Path and Cycle Problems

Details Kernel Bounds for Path and Cycle Problems Kernel Bounds for Path and Cycle Problems

2011-06-21

arxiv.org/abs/1106.4141v2

Computer Science

Data Structures and Algorithms

Scientific paper

Connectivity problems like k-Path and k-Disjoint Paths relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a modulator to a cluster graph, or a (promised) max leaf number. We obtain lower bounds via cross-composition, e.g., for Hamiltonian Cycle and related problems when parameterized by a modulator to an outerplanar graph.

Affiliated with

Also associated with

No associations

Rating

Kernel Bounds for Path and Cycle Problems 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 Kernel Bounds for Path and Cycle Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kernel Bounds for Path and Cycle Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178195