On the Reduction of the CSP Dichotomy Conjecture to Digraphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10188781" target="_blank" >RIV/00216208:11320/13:10188781 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-40627-0" target="_blank" >http://dx.doi.org/10.1007/978-3-642-40627-0</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-40627-0" target="_blank" >10.1007/978-3-642-40627-0</a>

Result language
angličtina
Original language name
On the Reduction of the CSP Dichotomy Conjecture to Digraphs
Original language description
It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a reduction and use it to show that the algebraic dichotomy conjecture is equivalent to its restriction to digraphs and that the polynomial reduction can be made in logspace. We also show that our reduction preserves the bounded width property, i.e., solvability by local consistency methods. We discuss further algorithmic properties that are preserved and related open problems.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Principles and Practice of Constraint Programming
ISBN
978-3-642-40626-3
ISSN
0302-9743
e-ISSN
—
Number of pages
16
Pages from-to
184-199
Publisher name
Springer
Place of publication
Berlin Heidelberg
Event location
Uppsala, Sweden
Event date
Sep 16, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)