The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
The result's identifiers
Result code in 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>
Result on the web
<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
—
Alternative languages
Result language
angličtina
Original language name
The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Multiple-Valued Logic and Soft Computing
ISSN
1542-3980
e-ISSN
1542-3999
Volume of the periodical
44
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
20
Pages from-to
333-352
UT code for WoS article
001439942900002
EID of the result in the Scopus database
—