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

• Published in: Algorithmica 2017-09, Vol.79 (1), p.3-28
• Main Authors: Jansen, Bart M. P., Pieterse, Astrid
• Format: Article
• Language: English
• Subjects: Algebra; Algorithm Analysis and Problem Complexity; Algorithms; Coloring; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Equivalence; Graph theory; Kernels; Lower bounds; Mathematical analysis; Mathematics of Computing; Theory of Computation; Traveling salesman problem; Upper bounds
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-016-0189-9

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 - ε ) for  ε > 0 , unless NP ⊆ 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 - ε ) edges, unless NP ⊆ coNP / 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  n d - 1 . We show that our kernel is tight under the assumption that NP ⊈ coNP / poly .