CLAP: A NEW ALGORITHM FOR PROMISE CSPS\ast

被引：10

作者：

Ciardo, Lorenzo ^{[1
]}

Zivny, Stanislav ^{[1
]}

机构：

[1] Univ Oxford, Dept Comp Sci, Wolfson Bldg, Parks Rd, Oxford OX1 3QD, England

来源：

SIAM JOURNAL ON COMPUTING | 2023年 / 52卷 / 01期

基金：

欧洲研究理事会;

关键词：

promise constraint satisfaction; homomorphism problems; linear programming; CONSTRAINT SATISFACTION; ALGEBRAIC STRUCTURE; ARC CONSISTENCY; COMPLEXITY; HARDNESS; POWER;

D O I：

10.1137/22M1476435

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP + AIP algorithm of Brakensiek et al. [SIAM J. Comput., 49 (2020), pp. 1232--1248] and not by a reduction to tractable finite-domain CSPs.

引用

页码：1 / 37

页数：37

共 71 条

[11] The wonderland of reflections
Barto, Libor
Oprsal, Jakub
Pinsker, Michael
[J]. ISRAEL JOURNAL OF MATHEMATICS, 2018, 223 (01) : 363 - 398
[12] ROBUSTLY SOLVABLE CONSTRAINT SATISFACTION PROBLEMS
Barto, Libor
Kozik, Marcin
[J]. SIAM JOURNAL ON COMPUTING, 2016, 45 (04) : 1646 - 1669
[13] The collapse of the bounded width hierarchy
Barto, Libor
[J]. JOURNAL OF LOGIC AND COMPUTATION, 2016, 26 (03) : 923 - 943
[14] Constraint Satisfaction Problems Solvable by Local Consistency Methods
Barto, Libor
Kozik, Marcin
[J]. JOURNAL OF THE ACM, 2014, 61 (01)
[15] Berman J, 2010, T AM MATH SOC, V362, P1445
[16] Theoretical analysis of singleton arc consistency and its extensions
Bessiere, Christian
Debruyne, Romuald
[J]. ARTIFICIAL INTELLIGENCE, 2008, 172 (01) : 29 - 41
[17] NEW APPROXIMATION ALGORITHMS FOR GRAPH-COLORING
BLUM, A
[J]. JOURNAL OF THE ACM, 1994, 41 (03) : 470 - 516
[18] ω-CATEGORICAL STRUCTURES AVOIDING HEIGHT 1 IDENTITIES
Bodirsky, Manuel
Mottet, Antoine
Olsak, Miroslav
Oprsal, Jakub
Pinsker, Michael
Willard, Ross
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2021, 374 (01) : 327 - 350
[19] Discrete Temporal Constraint Satisfaction Problems
Bodirsky, Manuel
Martin, Barnaby
Mottet, Antoine
[J]. JOURNAL OF THE ACM, 2018, 65 (02)
[20] BRAKENSIEK J., 2021, P 48 INT C AUT LANG, V198, P37, DOI 10.4230/LIPIcs.ICALP.2021.37

← 1 2 3 4 5 6 7 8 →