Optimal data reduction for graph coloring using low-degree polynomials

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
28 Downloads (Pure)

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

Original languageEnglish
Title of host publication12th International Symposium on Parameterized and Exact Computation, IPEC 2017
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Electronic)978-3-95977-051-4
DOIs
Publication statusPublished - 1 Feb 2018
Event12th International Symposium on Parameterized and Exact Computation (IPEC 2017) - Vienna, Austria
Duration: 6 Sep 20178 Sep 2017
Conference number: 12
https://algo2017.ac.tuwien.ac.at/ipec

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume89

Conference

Conference12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Abbreviated titleIPEC 2017
CountryAustria
CityVienna
Period6/09/178/09/17
Internet address

Fingerprint

Coloring
Data reduction
Polynomials
Parameterization
Structural properties
Color

Keywords

  • Graph coloring
  • Kernelization
  • Sparsification

Cite this

Jansen, B. M. P., & Pieterse, A. (2018). Optimal data reduction for graph coloring using low-degree polynomials. In 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
Jansen, Bart M.P. ; Pieterse, Astrid. / Optimal data reduction for graph coloring using low-degree polynomials. 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. (Leibniz International Proceedings in Informatics (LIPIcs)).
@inproceedings{b6774cd1aa6c431382d0dad9159e8eb0,
title = "Optimal data reduction for graph coloring using low-degree polynomials",
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(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.",
keywords = "Graph coloring, Kernelization, Sparsification",
author = "Jansen, {Bart M.P.} and Astrid Pieterse",
year = "2018",
month = "2",
day = "1",
doi = "10.4230/LIPIcs.IPEC.2017.22",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
booktitle = "12th International Symposium on Parameterized and Exact Computation, IPEC 2017",

}

Jansen, BMP & Pieterse, A 2018, Optimal data reduction for graph coloring using low-degree polynomials. in 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.

12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. 22 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 89).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 -

Jansen BMP, Pieterse A. Optimal data reduction for graph coloring using low-degree polynomials. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2018. 22. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.IPEC.2017.22