Sparsification upper and lower bounds for graphs problems and not-all-equal SAT

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

4 Citations (Scopus)
25 Downloads (Pure)

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.
Original languageEnglish
Title of host publication10th International Symposium on Parameterized and Exact Computation, IPEC'15, September 16-18, 2015, Patras, Greece
EditorsT. Husfeldt, I. Kanj
Place of PublicationWadern
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages163-174
ISBN (Electronic)978-3-939897-92-7
DOIs
Publication statusPublished - 23 Nov 2015
Event10th International Symposium on Parameterized and Exact Computation (IPEC 2015) - Patras, Greece
Duration: 16 Sep 201518 Sep 2015
Conference number: 10
http://algo2015.upatras.gr/ipec

Publication series

NameLIPICS
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik
Volume43
ISSN (Electronic)1868-8969

Conference

Conference10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Abbreviated titleIPEC 2015
Country/TerritoryGreece
CityPatras
Period16/09/1518/09/15
Internet address

Keywords

  • sparsification
  • graph coloring
  • Hamiltonian cycle
  • satisfiability

Fingerprint

Dive into the research topics of 'Sparsification upper and lower bounds for graphs problems and not-all-equal SAT'. Together they form a unique fingerprint.

Cite this