On planar valued CSPs

On planar valued CSPs

Pokaż inne wersje (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....

Szczegółowa specyfikacja

Opis bibliograficzny
Główni autorzy:	Fulla, P, Zivny, S
Format:	Conference item
Wydane:	Dagstuhl Publishing 2016

Podobne zapisy

On planar valued CSPs
od: Fulla, P, i wsp.
Wydane: (2017)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, i wsp.
Wydane: (2017)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, i wsp.
Wydane: (2017)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, i wsp.
Wydane: (2018)

The complexity of finite-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2016)

The complexity of conservative valued CSPs
od: Kolmogorov, V, i wsp.
Wydane: (2012)

The complexity of conservative valued CSPs
od: Kolmogorov, V, i wsp.
Wydane: (2011)

The complexity of conservative valued CSPs
od: Kolmogorov, V, i wsp.
Wydane: (2013)

The Complexity of Finite-Valued CSPs
od: Thapper, J, i wsp.
Wydane: (2013)

The complexity of finite-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2013)

The Power of Linear Programming for Valued CSPs
od: Thapper, J, i wsp.
Wydane: (2012)

The power of linear programming for valued CSPs
od: Thapper, J, i wsp.
Wydane: (2015)

The power of linear programming for valued CSPs
od: Thapper, J, i wsp.
Wydane: (2012)

The complexity of conservative finite-valued CSPs
od: Kolmogorov, V, i wsp.
Wydane: (2010)

Sherali-Adams relaxations for valued CSPs
od: Thapper, J, i wsp.
Wydane: (2015)

Necessary conditions for tractability of valued CSPs
od: Thapper, J, i wsp.
Wydane: (2015)

PTAS for sparse general-valued CSPs
od: Mezei, BF, i wsp.
Wydane: (2021)

PTAS for sparse general-valued CSPs
od: Mezei, B, i wsp.
Wydane: (2023)

The limits of SDP relaxations for general-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2018)

The limits of SDP relaxations for general-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2017)

Sparsification of binary CSPs
od: Butti, S, i wsp.
Wydane: (2020)

Sparsification of Binary CSPs
od: Butti, S, i wsp.
Wydane: (2019)

The power of Sherali-Adams relaxations for general-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2017)

Additive sparsification of CSPs
od: Pelleg, E, i wsp.
Wydane: (2021)

Additive sparsification of CSPs
od: Pelleg, E, i wsp.
Wydane: (2023)

The complexity of general-valued CSPs seen from the other side
od: Carbonnel, C, i wsp.
Wydane: (2018)

Point-width and max-CSPs
od: Carbonnel, C, i wsp.
Wydane: (2019)

Point-width and Max-CSPs
od: Carbonnel, C, i wsp.
Wydane: (2020)

Pliability and approximating max-CSPs
od: Romero, M, i wsp.
Wydane: (2023)

Treewidth-pliability and PTAS for Max-CSPs
od: Romero, M, i wsp.
Wydane: (2021)

CLAP: A new algorithm for promise CSPs
od: Ciardo, L, i wsp.
Wydane: (2023)

On singleton arc consistency for CSPs defined by monotone patterns
od: Carbonnel, C, i wsp.
Wydane: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
od: Carbonnel, C, i wsp.
Wydane: (2018)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
od: Cooper, M, i wsp.
Wydane: (2016)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
od: Cooper, M, i wsp.
Wydane: (2017)

Tractable classes of binary CSPs defined by excluded topological minors
od: Cohen, D, i wsp.
Wydane: (2015)

Small Promise CSPs that reduce to large CSPs
od: Alexandr Kazda, i wsp.
Wydane: (2022-08-01)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
od: Martin C. Cooper, i wsp.
Wydane: (2017-12-01)

A Galois connection for valued constraint languages of infinite size
od: Fulla, P, i wsp.
Wydane: (2015)