Abstract
We present several sparsification lower and upper bounds for classic problems in graph theory and logic. For the problems 4Coloring, (Directed) Hamiltonian Cycle, and (Connected) Dominating Set, we prove that there is no polynomialtime algorithm that reduces any nvertex input to an equivalent instance, of an arbitrary problem, with bitsize O(n^{2epsilon}) for epsilon > 0, unless NP is a subset of coNP/poly and the polynomialtime hierarchy collapses. These results imply that existing linearvertex kernels for kNonblocker and kMax Leaf Spanning Tree (the parametric duals of (Connected) Dominating Set) cannot be improved to have O(k^{2epsilon}) edges, unless NP is a subset of NP/poly. We also present a positive result and exhibit a nontrivial sparsification algorithm for dNotAllEqualSAT. We give an algorithm that reduces an nvariable input with clauses of size at most d to an equivalent input with O(n^{d1}) clauses, for any fixed d. Our algorithm is based on a linearalgebraic proof of LovĂˇsz that bounds the number of hyperedges in critically 3chromatic duniform nvertex hypergraphs by binom{n}{d1}. We show that our kernel is tight under the assumption that NP is not a subset of NP/poly.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs:2015:5580,
author = {Bart M. P. Jansen and Astrid Pieterse},
title = {{Sparsification Upper and Lower Bounds for Graphs Problems and NotAllEqual SAT}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {163174},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897927},
ISSN = {18688969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5580},
URN = {urn:nbn:de:0030drops55806},
doi = {10.4230/LIPIcs.IPEC.2015.163},
annote = {Keywords: sparsification, graph coloring, Hamiltonian cycle, satisfiability}
}
Keywords: 

sparsification, graph coloring, Hamiltonian cycle, satisfiability 
Collection: 

10th International Symposium on Parameterized and Exact Computation (IPEC 2015) 
Issue Date: 

2015 
Date of publication: 

19.11.2015 