A separator theorem for hypergraphs and a CSP-SAT algorithm

0551098 - MÚ 2022 RIV DE eng J - Článek v odborném periodiku
Koucký, M. - Rödl, V. - Talebanfard, Navid
A separator theorem for hypergraphs and a CSP-SAT algorithm.
Logical Methods in Computer Science. Roč. 17, č. 4 (2021), č. článku 17. ISSN 1860-5974. E-ISSN 1860-5974
Grant CEP: GA ČR(CZ) GX19-27871X
Institucionální podpora: RVO:67985840
Klíčová slova: computational complexity * logic in computer science * computer science
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 0.591, rok: 2021
Způsob publikování: Open access
https://doi.org/10.46298/lmcs-17(4:17)2021

We show that for every r≥2 there exists ϵr>0 such that any r-uniform hypergraph with m edges and maximum vertex degree o(m−−√) contains a set of at most (12−ϵ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−ϵr)m that decides satisfiability of m-variable (d,k)-CSPs in which every variable appears in at most r constraints, where ϵr depends only on r and k∈o(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−ϵ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.
Trvalý link: http://hdl.handle.net/11104/0326454