On planar valued CSPs

On planar valued CSPs

Taispeáin leaganacha eile (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....

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Fulla, P, Zivny, S
Formáid:	Conference item
Foilsithe / Cruthaithe:	Dagstuhl Publishing 2016

Míreanna comhchosúla

On planar valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2018)

The complexity of finite-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2012)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2011)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2013)

The Complexity of Finite-Valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2013)

The complexity of finite-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2013)

The Power of Linear Programming for Valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2012)

The power of linear programming for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

The power of linear programming for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2012)

The complexity of conservative finite-valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2010)

Sherali-Adams relaxations for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

Necessary conditions for tractability of valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

PTAS for sparse general-valued CSPs
de réir: Mezei, BF, et al.
Foilsithe / Cruthaithe: (2021)

PTAS for sparse general-valued CSPs
de réir: Mezei, B, et al.
Foilsithe / Cruthaithe: (2023)

The limits of SDP relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2018)

The limits of SDP relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2017)

Sparsification of binary CSPs
de réir: Butti, S, et al.
Foilsithe / Cruthaithe: (2020)

Sparsification of Binary CSPs
de réir: Butti, S, et al.
Foilsithe / Cruthaithe: (2019)

The power of Sherali-Adams relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2017)

Additive sparsification of CSPs
de réir: Pelleg, E, et al.
Foilsithe / Cruthaithe: (2021)

Additive sparsification of CSPs
de réir: Pelleg, E, et al.
Foilsithe / Cruthaithe: (2023)

The complexity of general-valued CSPs seen from the other side
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)

Point-width and max-CSPs
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2019)

Point-width and Max-CSPs
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2020)

Pliability and approximating max-CSPs
de réir: Romero, M, et al.
Foilsithe / Cruthaithe: (2023)

Treewidth-pliability and PTAS for Max-CSPs
de réir: Romero, M, et al.
Foilsithe / Cruthaithe: (2021)

CLAP: A new algorithm for promise CSPs
de réir: Ciardo, L, et al.
Foilsithe / Cruthaithe: (2023)

On singleton arc consistency for CSPs defined by monotone patterns
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
de réir: Cooper, M, et al.
Foilsithe / Cruthaithe: (2016)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
de réir: Cooper, M, et al.
Foilsithe / Cruthaithe: (2017)

Tractable classes of binary CSPs defined by excluded topological minors
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2015)

Small Promise CSPs that reduce to large CSPs
de réir: Alexandr Kazda, et al.
Foilsithe / Cruthaithe: (2022-08-01)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
de réir: Martin C. Cooper, et al.
Foilsithe / Cruthaithe: (2017-12-01)

A Galois connection for valued constraint languages of infinite size
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2015)