On the Reduction of the CSP Dichotomy Conjecture to Digraphs

Kód výsledku v 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>
Výsledek na webu
<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>

Jazyk výsledku
angličtina
Název v původním jazyce
On the Reduction of the CSP Dichotomy Conjecture to Digraphs
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
On the Reduction of the CSP Dichotomy Conjecture to Digraphs
Popis výsledku anglicky
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.

Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)