On planar valued CSPs

On planar valued CSPs

Показать другие версии (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....

Полное описание

Библиографические подробности
Главные авторы:	Fulla, P, Zivny, S
Формат:	Conference item
Опубликовано:	Dagstuhl Publishing 2016

Схожие документы

On planar valued CSPs
по: Fulla, P, и др.
Опубликовано: (2017)

The complexity of Boolean surjective general-valued CSPs
по: Fulla, P, и др.
Опубликовано: (2017)

The complexity of Boolean surjective general-valued CSPs
по: Fulla, P, и др.
Опубликовано: (2017)

The complexity of Boolean surjective general-valued CSPs
по: Fulla, P, и др.
Опубликовано: (2018)

The complexity of finite-valued CSPs
по: Thapper, J, и др.
Опубликовано: (2016)

The complexity of conservative valued CSPs
по: Kolmogorov, V, и др.
Опубликовано: (2012)

The complexity of conservative valued CSPs
по: Kolmogorov, V, и др.
Опубликовано: (2011)

The complexity of conservative valued CSPs
по: Kolmogorov, V, и др.
Опубликовано: (2013)

The Complexity of Finite-Valued CSPs
по: Thapper, J, и др.
Опубликовано: (2013)

The complexity of finite-valued CSPs
по: Thapper, J, и др.
Опубликовано: (2013)

The Power of Linear Programming for Valued CSPs
по: Thapper, J, и др.
Опубликовано: (2012)

The power of linear programming for valued CSPs
по: Thapper, J, и др.
Опубликовано: (2015)

The power of linear programming for valued CSPs
по: Thapper, J, и др.
Опубликовано: (2012)

The complexity of conservative finite-valued CSPs
по: Kolmogorov, V, и др.
Опубликовано: (2010)

Sherali-Adams relaxations for valued CSPs
по: Thapper, J, и др.
Опубликовано: (2015)

Necessary conditions for tractability of valued CSPs
по: Thapper, J, и др.
Опубликовано: (2015)

PTAS for sparse general-valued CSPs
по: Mezei, BF, и др.
Опубликовано: (2021)

PTAS for sparse general-valued CSPs
по: Mezei, B, и др.
Опубликовано: (2023)

The limits of SDP relaxations for general-valued CSPs
по: Thapper, J, и др.
Опубликовано: (2018)

The limits of SDP relaxations for general-valued CSPs
по: Thapper, J, и др.
Опубликовано: (2017)

Sparsification of binary CSPs
по: Butti, S, и др.
Опубликовано: (2020)

Sparsification of Binary CSPs
по: Butti, S, и др.
Опубликовано: (2019)

The power of Sherali-Adams relaxations for general-valued CSPs
по: Thapper, J, и др.
Опубликовано: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
по: Thapper, J, и др.
Опубликовано: (2017)

Additive sparsification of CSPs
по: Pelleg, E, и др.
Опубликовано: (2021)

Additive sparsification of CSPs
по: Pelleg, E, и др.
Опубликовано: (2023)

The complexity of general-valued CSPs seen from the other side
по: Carbonnel, C, и др.
Опубликовано: (2018)

Point-width and max-CSPs
по: Carbonnel, C, и др.
Опубликовано: (2019)

Point-width and Max-CSPs
по: Carbonnel, C, и др.
Опубликовано: (2020)

Pliability and approximating max-CSPs
по: Romero, M, и др.
Опубликовано: (2023)

Treewidth-pliability and PTAS for Max-CSPs
по: Romero, M, и др.
Опубликовано: (2021)

CLAP: A new algorithm for promise CSPs
по: Ciardo, L, и др.
Опубликовано: (2023)

On singleton arc consistency for CSPs defined by monotone patterns
по: Carbonnel, C, и др.
Опубликовано: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
по: Carbonnel, C, и др.
Опубликовано: (2018)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
по: Cooper, M, и др.
Опубликовано: (2016)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
по: Cooper, M, и др.
Опубликовано: (2017)

Tractable classes of binary CSPs defined by excluded topological minors
по: Cohen, D, и др.
Опубликовано: (2015)

Small Promise CSPs that reduce to large CSPs
по: Alexandr Kazda, и др.
Опубликовано: (2022-08-01)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
по: Martin C. Cooper, и др.
Опубликовано: (2017-12-01)

A Galois connection for valued constraint languages of infinite size
по: Fulla, P, и др.
Опубликовано: (2015)