### Abstract

The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring. First, we use a recent technique of finding redundant constraints by representing them as lowdegree polynomials, to obtain a kernel of bitsize O(k^{q-1} log k) for q-Coloring parameterized by Vertex Cover for any q ≥ 3. This size bound is optimal up to k^{o(1)} factors assuming NP ⊈ coNP/poly, and improves on the previous-best kernel of size O(k^{q}). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP ⊈ coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n^{2-ϵ}) for any ϵ > 0. Previously, such a lower bound was only known for coloring with q ≥ 4 colors.

Original language | English |
---|---|

Title of host publication | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 |

Place of Publication | Dagstuhl |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Number of pages | 12 |

ISBN (Electronic) | 978-3-95977-051-4 |

DOIs | |

Publication status | Published - 1 Feb 2018 |

Event | 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) - Vienna, Austria Duration: 6 Sep 2017 → 8 Sep 2017 Conference number: 12 https://algo2017.ac.tuwien.ac.at/ipec |

### Publication series

Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|

Volume | 89 |

### Conference

Conference | 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) |
---|---|

Abbreviated title | IPEC 2017 |

Country | Austria |

City | Vienna |

Period | 6/09/17 → 8/09/17 |

Internet address |

### Fingerprint

### Keywords

- Graph coloring
- Kernelization
- Sparsification

### Cite this

*12th International Symposium on Parameterized and Exact Computation, IPEC 2017*[22] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 89). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2017.22

}

*12th International Symposium on Parameterized and Exact Computation, IPEC 2017.*, 22, Leibniz International Proceedings in Informatics (LIPIcs), vol. 89, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Vienna, Austria, 6/09/17. https://doi.org/10.4230/LIPIcs.IPEC.2017.22

**Optimal data reduction for graph coloring using low-degree polynomials.** / Jansen, Bart M.P.; Pieterse, Astrid.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Optimal data reduction for graph coloring using low-degree polynomials

AU - Jansen, Bart M.P.

AU - Pieterse, Astrid

PY - 2018/2/1

Y1 - 2018/2/1

N2 - The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring. First, we use a recent technique of finding redundant constraints by representing them as lowdegree polynomials, to obtain a kernel of bitsize O(kq-1 log k) for q-Coloring parameterized by Vertex Cover for any q ≥ 3. This size bound is optimal up to ko(1) factors assuming NP ⊈ coNP/poly, and improves on the previous-best kernel of size O(kq). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP ⊈ coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n2-ϵ) for any ϵ > 0. Previously, such a lower bound was only known for coloring with q ≥ 4 colors.

AB - The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring. First, we use a recent technique of finding redundant constraints by representing them as lowdegree polynomials, to obtain a kernel of bitsize O(kq-1 log k) for q-Coloring parameterized by Vertex Cover for any q ≥ 3. This size bound is optimal up to ko(1) factors assuming NP ⊈ coNP/poly, and improves on the previous-best kernel of size O(kq). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP ⊈ coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n2-ϵ) for any ϵ > 0. Previously, such a lower bound was only known for coloring with q ≥ 4 colors.

KW - Graph coloring

KW - Kernelization

KW - Sparsification

UR - http://www.scopus.com/inward/record.url?scp=85044713947&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2017.22

DO - 10.4230/LIPIcs.IPEC.2017.22

M3 - Conference contribution

AN - SCOPUS:85044713947

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 12th International Symposium on Parameterized and Exact Computation, IPEC 2017

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

ER -