Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs

A graph is

d

-degenerate if its every subgraph contains a vertex of degree at most

d

. For instance, planar graphs are 5-degenerate. Inspired by recent work by Philip, Raman and Sikdar, who have shown the existence of a polynomial kernel for

Dominating Set

in

d

-degenerate graphs, we investigate kernelization hardness of problems that include connectivity requirement in this class of graphs.

Our main contribution is the proof that

Connected Dominating Set

does not admit a polynomial kernel in

d

-degenerate graphs for

d

 ≥ 2 unless the polynomial hierarchy collapses up to the third level. We prove this using a problem originated from bioinformatics –

Colourful Graph Motif

– analyzed and proved to be NP-hard by Fellows et al. This problem nicely encapsulates the hardness of the connectivity requirement in kernelization. Our technique yields also an alternative proof that, under the same complexity assumption,

Steiner Tree

does not admit a polynomial kernel. The original proof, via reduction from

Set Cover

, is due to Dom, Lokshtanov and Saurabh.

We extend our analysis by showing that, unless

$PH = \Sigma_p^3$

, there do not exist polynomial kernels for

Steiner Tree

,

Connected Feedback Vertex Set

and

Connected Odd Cycle Transversal

in

d

-degenerate graphs for

d

 ≥ 2. On the other hand, we show a polynomial kernel for

Connected Vertex Cover

in graphs that do not contain the biclique

K

i

,

j

as a subgraph.