License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.163
URN: urn:nbn:de:0030-drops-55806
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5580/
Go to the corresponding LIPIcs Volume Portal

Jansen, Bart M. P. ; Pieterse, Astrid

Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT

pdf-format:
17.pdf (0.5 MB)

Abstract

We present several sparsification lower and upper bounds for classic problems in graph theory and logic. For the problems 4-Coloring, (Directed) Hamiltonian Cycle, and (Connected) Dominating Set, we prove that there is no polynomial-time algorithm that reduces any n-vertex input to an equivalent instance, of an arbitrary problem, with bitsize O(n^{2-epsilon}) for epsilon > 0, unless NP is a subset of coNP/poly and the polynomial-time hierarchy collapses. These results imply that existing linear-vertex kernels for k-Nonblocker and k-Max Leaf Spanning Tree (the parametric duals of (Connected) Dominating Set) cannot be improved to have O(k^{2-epsilon}) edges, unless NP is a subset of NP/poly. We also present a positive result and exhibit a non-trivial sparsification algorithm for d-Not-All-Equal-SAT. We give an algorithm that reduces an n-variable input with clauses of size at most d to an equivalent input with O(n^{d-1}) clauses, for any fixed d. Our algorithm is based on a linear-algebraic proof of Lovász that bounds the number of hyperedges in critically 3-chromatic d-uniform n-vertex hypergraphs by binom{n}{d-1}. 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 Not-All-Equal SAT}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{163--174},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5580},
  URN =		{urn:nbn:de:0030-drops-55806},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI