Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights

DOI10.1016/j.jcss.2007.02.001zbMath1115.68143OpenAlexW2142884756MaRDI QIDQ881590

Peter Jonsson, Andrei A. Krokhin

Publication date: 30 May 2007

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

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.02.001

zbMATH Keywords

complexitydichotomymaximum constraint satisfaction problemdigraph \(H\)-colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Enumerating homomorphisms ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• The complexity of counting homomorphisms seen from the other side
• A dichotomy theorem for maximum generalized satisfiability problems.
• On the complexity of H-coloring
• Learnability of quantified formulas.
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• Conjunctive-query containment and constraint satisfaction
• On bounded occurrence constraint satisfaction
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• Supermodular functions and the complexity of MAX CSP
• The complexity of soft constraint satisfaction
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Maximum Constraint Satisfaction on Diamonds
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Numerical Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The complexity of satisfiability problems
• Some optimal inapproximability results
• Algorithmic Learning Theory
• The Approximability of Three-valued MAX CSP