TY - GEN
T1 - The complexity of general-valued CSPs seen from the other side
AU - Carbonnel, Clément
AU - Romero, Miguel
AU - Živný, Stanislav
N1 - Funding Information:
Stanislav Zˇ ivny´ was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/11/30
Y1 - 2018/11/30
N2 - The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand side structures, the results of Dal-mau, Kolaitis, and Vardi [CP'02], Grohe [FOCS'03/JACM'07], and Atserias, Bulatov, and Dalmau [ICALP'07] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalisation of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the k-th level of the Sherali-Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognising the tractable cases; the latter has an application in database theory.
AB - The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand side structures, the results of Dal-mau, Kolaitis, and Vardi [CP'02], Grohe [FOCS'03/JACM'07], and Atserias, Bulatov, and Dalmau [ICALP'07] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalisation of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the k-th level of the Sherali-Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognising the tractable cases; the latter has an application in database theory.
KW - Fractional homomorphism
KW - Homomorphism problems
KW - Sherali-Adams LP relaxation
KW - Treewidth
KW - Valued constraint satisfaction
UR - http://www.scopus.com/inward/record.url?scp=85059818420&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2018.00031
DO - 10.1109/FOCS.2018.00031
M3 - Conference contribution
AN - SCOPUS:85059818420
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 236
EP - 246
BT - Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
A2 - Thorup, Mikkel
PB - IEEE Computer Society
T2 - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Y2 - 7 October 2018 through 9 October 2018
ER -