On planar valued CSPs

On planar valued CSPs

Show other versions (1)

We study the computational complexity of planar valued constraint satisfaction problems (VCSPs). First, we show that intractable Boolean VCSPs have to be self-complementary to be tractable in the planar setting, thus extending a corresponding result of Dvořák and Kupec [ICALP’15] from CSPs to VCSPs....

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Fulla, P, Zivny, S
Fformat:	Conference item
Cyhoeddwyd:	Dagstuhl Publishing 2016

Eitemau Tebyg

On planar valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2017)

The complexity of Boolean surjective general-valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2017)

The complexity of Boolean surjective general-valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2017)

The complexity of Boolean surjective general-valued CSPs
gan: Fulla, P, et al.
Cyhoeddwyd: (2018)

The complexity of finite-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2016)

The complexity of conservative valued CSPs
gan: Kolmogorov, V, et al.
Cyhoeddwyd: (2012)

The complexity of conservative valued CSPs
gan: Kolmogorov, V, et al.
Cyhoeddwyd: (2011)

The complexity of conservative valued CSPs
gan: Kolmogorov, V, et al.
Cyhoeddwyd: (2013)

The Complexity of Finite-Valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2013)

The complexity of finite-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2013)

The Power of Linear Programming for Valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2012)

The power of linear programming for valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2015)

The power of linear programming for valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2012)

The complexity of conservative finite-valued CSPs
gan: Kolmogorov, V, et al.
Cyhoeddwyd: (2010)

Sherali-Adams relaxations for valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2015)

Necessary conditions for tractability of valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2015)

PTAS for sparse general-valued CSPs
gan: Mezei, BF, et al.
Cyhoeddwyd: (2021)

PTAS for sparse general-valued CSPs
gan: Mezei, B, et al.
Cyhoeddwyd: (2023)

The limits of SDP relaxations for general-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2018)

The limits of SDP relaxations for general-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2017)

Sparsification of binary CSPs
gan: Butti, S, et al.
Cyhoeddwyd: (2020)

Sparsification of Binary CSPs
gan: Butti, S, et al.
Cyhoeddwyd: (2019)

The power of Sherali-Adams relaxations for general-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
gan: Thapper, J, et al.
Cyhoeddwyd: (2017)

Additive sparsification of CSPs
gan: Pelleg, E, et al.
Cyhoeddwyd: (2021)

Additive sparsification of CSPs
gan: Pelleg, E, et al.
Cyhoeddwyd: (2023)

The complexity of general-valued CSPs seen from the other side
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2018)

Point-width and max-CSPs
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2019)

Point-width and Max-CSPs
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2020)

Pliability and approximating max-CSPs
gan: Romero, M, et al.
Cyhoeddwyd: (2023)

Treewidth-pliability and PTAS for Max-CSPs
gan: Romero, M, et al.
Cyhoeddwyd: (2021)

CLAP: A new algorithm for promise CSPs
gan: Ciardo, L, et al.
Cyhoeddwyd: (2023)

On singleton arc consistency for CSPs defined by monotone patterns
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2018)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
gan: Cooper, M, et al.
Cyhoeddwyd: (2016)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
gan: Cooper, M, et al.
Cyhoeddwyd: (2017)

Tractable classes of binary CSPs defined by excluded topological minors
gan: Cohen, D, et al.
Cyhoeddwyd: (2015)

Small Promise CSPs that reduce to large CSPs
gan: Alexandr Kazda, et al.
Cyhoeddwyd: (2022-08-01)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
gan: Martin C. Cooper, et al.
Cyhoeddwyd: (2017-12-01)

A Galois connection for valued constraint languages of infinite size
gan: Fulla, P, et al.
Cyhoeddwyd: (2015)