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].

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
Full Text: DOI