Data Reduction for Graph Coloring Problems

Details Data Reduction for Graph Coloring Problems Data Reduction for Graph Coloring Problems

2011-04-21

arxiv.org/abs/1104.4229v1

Computer Science

Data Structures and Algorithms

Scientific paper

This paper studies the kernelization complexity of graph coloring problems, with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring problems, in terms of the chosen parameter. It is well known that deciding 3-colorability is already NP-complete, hence parameterizing by the requested number of colors is not fruitful. Instead, we pick up on a research thread initiated by Cai (DAM, 2003) who studied coloring problems parameterized by the modification distance of the input graph to a graph class on which coloring is polynomial-time solvable; for example parameterizing by the number k of vertex-deletions needed to make the graph chordal. We obtain various upper and lower bounds for kernels of such parameterizations of q-Coloring, complementing Cai's study of the time complexity with respect to these parameters.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178160