On planar valued CSPs
From MaRDI portal
Publication:2396724
DOI10.1016/J.JCSS.2017.03.005zbMATH Open1370.68125arXiv1602.06323OpenAlexW2280355158MaRDI QIDQ2396724FDOQ2396724
Authors: Peter Fulla, S. Zivny 
Publication date: 24 May 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Abstract: We study the computational complexity of planar valued constraint satisfaction problems (VCSPs), which require the incidence graph of the instance be planar. 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 Dvorak and Kupec [ICALP'15] from CSPs to VCSPs. Second, we give a complete complexity classification of conservative planar VCSPs on arbitrary finite domains. In this case planarity does not lead to any new tractable cases and thus our classification is a sharpening of the classification of conservative VCSPs by Kolmogorov and Zivny [JACM'13].
Full work available at URL: https://arxiv.org/abs/1602.06323
Recommendations
- On Planar Valued CSPs
- On Planar Boolean CSP
- The complexity of valued CSPs
- The complexity of valued constraint satisfaction problems
- The complexity of conservative valued CSPs
- The complexity of conservative valued CSPs
- The complexity of finite-valued CSPs
- The complexity of finite-valued CSPs
- The complexity of general-valued CSPs
- Necessary conditions for tractability of valued CSPs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Handbook of constraint programming.
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity classifications of Boolean constraint satisfaction problems
- Minimum-weight triangulation is NP-hard
- Efficient Planarity Testing
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Classifying the Complexity of Constraints Using Finite Algebras
- Constraints, consistency and closure
- The complexity of soft constraint satisfaction
- Tractability in constraint satisfaction problems: a survey
- Complexity of conservative constraint satisfaction problems
- The complexity of finite-valued CSPs
- Colouring, constraint satisfaction, and complexity
- The complexity of conservative valued CSPs
- An algebraic theory of complexity for discrete optimization.
- The complexity of counting homomorphisms seen from the other side
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Title not available (Why is that?)
- The complexity of planar Boolean \(\#\)CSP with complex weights
- Title not available (Why is that?)
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Bounded Tree-Width and CSP-Related Problems
- Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
- A dichotomy theorem for the general minimum cost homomorphism problem
- The power of linear programming for general-valued CSPs
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- A Galois connection for valued constraint languages of infinite size
- Algebraic properties of valued constraint satisfaction problem
- The power of Sherali-Adams relaxations for general-valued CSPs
- The Complexity of Valued CSPs
- Skew bisubmodularity and valued CSPs
- On Planar Boolean CSP
- Sherali-Adams relaxations for valued CSPs
- Necessary conditions for tractability of valued CSPs
- Effectiveness of structural restrictions for hybrid CSPs
- Even delta-matroids and the complexity of planar Boolean CSPs
- On Planar Valued CSPs
Cited In (2)
This page was built for publication: On planar valued CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396724)
