2026-07-20T06:35:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5580 2024-03-06T10:36:35Z ddc:004 open_access

Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT Jansen, Bart M. P. Pieterse, Astrid sparsification graph coloring Hamiltonian cycle satisfiability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bart M. P. Jansen and Astrid Pieterse 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.163 urn:nbn:de:0030-drops-55806 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.163 eng https://creativecommons.org/licenses/by/3.0/legalcode