Počet záznamů: 1
A separator theorem for hypergraphs and a CSP-SAT algorithm
- 1.
SYSNO ASEP 0551098 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název A separator theorem for hypergraphs and a CSP-SAT algorithm Tvůrce(i) Koucký, M. (CZ)
Rödl, V. (US)
Talebanfard, Navid (MU-W) SAI, ORCID, RIDČíslo článku 17 Zdroj.dok. Logical Methods in Computer Science. - : Logical Methods in Computer Science - ISSN 1860-5974
Roč. 17, č. 4 (2021)Poč.str. 14 s. Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova computational complexity ; logic in computer science ; computer science Vědní obor RIV BA - Obecná matematika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GX19-27871X GA ČR - Grantová agentura ČR Způsob publikování Open access Institucionální podpora MU-W - RVO:67985840 UT WOS 000744066500008 EID SCOPUS 85123311375 DOI 10.46298/lmcs-17(4:17)2021 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2022 Elektronická adresa https://doi.org/10.46298/lmcs-17(4:17)2021
Počet záznamů: 1