| Autor: |
Jansen, Bart M.P., Pieterse, Astrid, Husfeldt, T., Kanj, I. |
| Přispěvatelé: |
Algorithms, Geometry and Applications |
| Jazyk: |
angličtina |
| Rok vydání: |
2015 |
| Předmět: |
|
| Zdroj: |
STARTPAGE=163;ENDPAGE=174;TITLE=10th International Symposium on Parameterized and Exact Computation, IPEC'15, September 16-18, 2015, Patras, Greece |
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
