Linear Kernels in Linear Time, or How to Save k Colors in O(n 2) Steps

This paper examines a parameterized problem that we refer to as

n

–

k

Graph Coloring

, i.e., the problem of determining whether a graph

G

with

n

vertices can be colored using

n

–

k

colors. As the main result of this paper, we show that there exists a

O

(

kn

2

+

k

2

+ 2

3.8161k

)=

O

(

n

2

) algorithm for

n

–

k

Graph Coloring

for each fixed

k

. The core technique behind this new parameterized algorithm is kernalization via maximum (and certain maximal) matchings.

The core technical content of this paper is a near linear-time kernelization algorithm for

n

–

k

Clique Covering

. The near linear-time kernelization algorithm that we present for

n

–

k

Clique Covering

produces a linear size (3

k

–3) kernel in

O

(

k

(

n

+

m

)) steps on graphs with

n

vertices and

m

edges. The algorithm takes an instance 〈

G

,

k

〉 of

Clique Covering

that asks whether a graph

G

can be covered using |

V

|–

k

cliques and reduces it to the problem of determining whether a graph

G

′=(

V

′,

E

′) of size ≤ 3

k

–3 can be covered using |

V

′| –

k

′ cliques. We also present a similar near linear-time algorithm that produces a 3

k

kernel for

Vertex Cover

. This second kernelization algorithm is the

crown reduction rule

.