On planar valued CSPs

DOI10.1016/J.JCSS.2017.03.005MaRDI QIDQ2396724zbMATH OpenOpenAlexFDO

Authors Peter Fulla, S. Zivny

Publication date 24 May 2017

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.06323

zbMATH Keywords

constraint satisfactionplanarityvalued constraint satisfactionmultimorphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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].

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 general-valued CSPs
• Necessary conditions for tractability of valued CSPs

Cites work

• scientific article; zbMATH DE number 4094812 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256750 (Why is no real title available?)
• A Galois connection for valued constraint languages of infinite size
• A dichotomy theorem for the general minimum cost homomorphism problem
• Algebraic properties of valued constraint satisfaction problem
• An algebraic theory of complexity for discrete optimization.
• Bounded Tree-Width and CSP-Related Problems
• Classifying the Complexity of Constraints Using Finite Algebras
• Colouring, constraint satisfaction, and complexity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of conservative constraint satisfaction problems
• Constraints, consistency and closure
• Effectiveness of structural restrictions for hybrid CSPs
• Efficient Planarity Testing
• Even delta-matroids and the complexity of planar Boolean CSPs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Handbook of constraint programming.
• Minimum-weight triangulation is NP-hard
• Necessary conditions for tractability of valued CSPs
• On Planar Boolean CSP
• On Planar Valued CSPs
• Sherali-Adams relaxations for valued CSPs
• Skew bisubmodularity and valued CSPs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The complexity of conservative valued CSPs
• The complexity of counting homomorphisms seen from the other side
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of soft constraint satisfaction
• The complexity of valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• The power of linear programming for general-valued CSPs
• Tractability in constraint satisfaction problems: a survey

Cited in

(2)

• On Planar Valued CSPs
• On Planar Boolean CSP

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)