On planar valued CSPs

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