Number of the records: 1
A separator theorem for hypergraphs and a CSP-SAT algorithm
- 1.
SYSNO ASEP 0551098 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title A separator theorem for hypergraphs and a CSP-SAT algorithm Author(s) Koucký, M. (CZ)
Rödl, V. (US)
Talebanfard, Navid (MU-W) SAI, ORCID, RIDArticle number 17 Source Title Logical Methods in Computer Science. - : Logical Methods in Computer Science - ISSN 1860-5974
Roč. 17, č. 4 (2021)Number of pages 14 s. Language eng - English Country DE - Germany Keywords computational complexity ; logic in computer science ; computer science Subject RIV BA - General Mathematics OECD category Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) R&D Projects GX19-27871X GA ČR - Czech Science Foundation (CSF) Method of publishing Open access Institutional support MU-W - RVO:67985840 UT WOS 000744066500008 EID SCOPUS 85123311375 DOI https://doi.org/10.46298/lmcs-17(4:17)2021 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2022 Electronic address https://doi.org/10.46298/lmcs-17(4:17)2021
Number of the records: 1