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....

書目詳細資料
Main Authors:	Fulla, P, Zivny, S
格式:	Conference item
出版:	Dagstuhl Publishing 2016

相似書籍

On planar valued CSPs
由: Fulla, P, et al.
出版: (2017)

The complexity of Boolean surjective general-valued CSPs
由: Fulla, P, et al.
出版: (2017)

The complexity of Boolean surjective general-valued CSPs
由: Fulla, P, et al.
出版: (2017)

The complexity of Boolean surjective general-valued CSPs
由: Fulla, P, et al.
出版: (2018)

The complexity of finite-valued CSPs
由: Thapper, J, et al.
出版: (2016)

The complexity of conservative valued CSPs
由: Kolmogorov, V, et al.
出版: (2012)

The complexity of conservative valued CSPs
由: Kolmogorov, V, et al.
出版: (2011)

The complexity of conservative valued CSPs
由: Kolmogorov, V, et al.
出版: (2013)

The Complexity of Finite-Valued CSPs
由: Thapper, J, et al.
出版: (2013)

The complexity of finite-valued CSPs
由: Thapper, J, et al.
出版: (2013)

The Power of Linear Programming for Valued CSPs
由: Thapper, J, et al.
出版: (2012)

The power of linear programming for valued CSPs
由: Thapper, J, et al.
出版: (2015)

The power of linear programming for valued CSPs
由: Thapper, J, et al.
出版: (2012)

The complexity of conservative finite-valued CSPs
由: Kolmogorov, V, et al.
出版: (2010)

Sherali-Adams relaxations for valued CSPs
由: Thapper, J, et al.
出版: (2015)

Necessary conditions for tractability of valued CSPs
由: Thapper, J, et al.
出版: (2015)

PTAS for sparse general-valued CSPs
由: Mezei, BF, et al.
出版: (2021)

PTAS for sparse general-valued CSPs
由: Mezei, B, et al.
出版: (2023)

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

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

Sparsification of binary CSPs
由: Butti, S, et al.
出版: (2020)

Sparsification of Binary CSPs
由: Butti, S, et al.
出版: (2019)

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

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

Additive sparsification of CSPs
由: Pelleg, E, et al.
出版: (2021)

Additive sparsification of CSPs
由: Pelleg, E, et al.
出版: (2023)

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

Point-width and max-CSPs
由: Carbonnel, C, et al.
出版: (2019)

Point-width and Max-CSPs
由: Carbonnel, C, et al.
出版: (2020)

Pliability and approximating max-CSPs
由: Romero, M, et al.
出版: (2023)

Treewidth-pliability and PTAS for Max-CSPs
由: Romero, M, et al.
出版: (2021)

CLAP: A new algorithm for promise CSPs
由: Ciardo, L, et al.
出版: (2023)

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

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

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

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

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

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

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

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