The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10509285" target="_blank" >RIV/00216208:11320/25:10509285 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=HXyywg.qmp" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=HXyywg.qmp</a>
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
Popis výsledku v původním jazyce
We introduce the framework of the left-hand side restricted promise constraint satisfaction problem, which includes problems like approximating clique number of a graph. We study the parameterized complexity of problems in this class and provide some initial results. The main technical contribution is a sufficient condition for W[1]-hardness which, in particular, covers left-hand side restricted bounded arity CSPs.
Název v anglickém jazyce
The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
Popis výsledku anglicky
We introduce the framework of the left-hand side restricted promise constraint satisfaction problem, which includes problems like approximating clique number of a graph. We study the parameterized complexity of problems in this class and provide some initial results. The main technical contribution is a sufficient condition for W[1]-hardness which, in particular, covers left-hand side restricted bounded arity CSPs.

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

Rok uplatnění
2025
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)