zbMATH — the first resource for mathematics

Linear kernels in linear time, or how to save $$k$$ colors in $$O(n^{2})$$ steps. (English) Zbl 1112.68412
Hromkovič, Juraj (ed.) et al., Graph-theoretic concepts in computer science. 30th international workshop, WG 2004, Bad Honnef, Germany, June 21–23, 2004. Revised papers. Berlin: Springer (ISBN 3-540-24132-9/pbk). Lecture Notes in Computer Science 3353, 257-269 (2004).
Summary: 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.8161 k})= 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 $$\langle G, k\rangle$$ 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 $$\leq 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.
For the entire collection see [Zbl 1067.68006].

MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C15 Coloring of graphs and hypergraphs 05C85 Graph algorithms (graph-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity
Edgebreaker
Full Text: