Michal Koucký ; Vojtěch Rödl ; Navid Talebanfard - A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

lmcs:7484 - Logical Methods in Computer Science, December 13, 2021, Volume 17, Issue 4 - https://doi.org/10.46298/lmcs-17(4:17)2021
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Authors: Michal Koucký ORCID-iD; Vojtěch Rödl ; Navid Talebanfard ORCID-iD

    We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph with $m$ edges and maximum vertex degree $o(\sqrt{m})$ contains 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})$. Furthermore our algorithm solves the corresponding #CSP-SAT and Max-CSP-SAT of these CSPs. We 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.

    Volume: Volume 17, Issue 4
    Published on: December 13, 2021
    Accepted on: October 7, 2021
    Submitted on: May 17, 2021
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity
    Fundings :
      Source : OpenAIRE Graph
    • Extremal and Ramsey-Type Problems for Graphs and Hypergraphs; Funder: National Science Foundation; Code: 1764385


    Consultation statistics

    This page has been seen 365 times.
    This article's PDF has been downloaded 167 times.