Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-181 | 18th February 2020 12:39

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

RSS-Feed




Revision #1
Authors: Michal Koucky, Vojtech Rodl, Navid Talebanfard
Accepted on: 18th February 2020 12:39
Downloads: 29
Keywords: 


Abstract:

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph on $m$ edges with bounded vertex degree has a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. We use this to give an algorithm running in time $d^{(1 - \epsilon_r)m}$ that decides satisfiability of $m$-variable $(d, k)$-CSPs in which every variable appears in at most $r$ constraints, where $\epsilon_r$ depends only on $r$ and $k\in o(\sqrt{m})$. We will also show that CNF representations of unsatisfiable $(2, k)$-CSPs with variable frequency $r$ can be refuted in tree-like resolution in size $2^{(1 - \epsilon_r)m}$. Furthermore for Tseitin formulas on graphs with degree at most $k$ (which are $(2, k)$-CSPs) we give a deterministic algorithm finding such a refutation.



Changes to previous version:

Improved presentation and minor edits.


Paper:

TR19-181 | 9th December 2019 17:12

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm





TR19-181
Authors: Michal Koucky, Vojtech Rodl, Navid Talebanfard
Publication: 13th December 2019 16:39
Downloads: 204
Keywords: 


Abstract:

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph on $m$ edges with bounded vertex degree has a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. We use this to give a satisfiability algorithm for $n$-variable $(d, k)$-CSPs in which every variable appears in at most $r$ constraints in time $d^{(1 - \epsilon_r)n}$ where $\epsilon_r$ depends only on $r$, provided that $k$ is small enough as a function of $m$. We will also show that unsatisfiable $(2, k)$-CSPs with variable frequency $r$ can be refuted in tree-like resolution in size $2^{(1 - \epsilon_r)n}$. Furthermore for Tseitin formulas on graphs with degree at most $k$ (which are $(2, k)$-CSPs) we give a deterministic algorithm finding such a refutation.



ISSN 1433-8092 | Imprint