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

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

Andrei A. Krokhin, Peter Jonsson

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

complexity; dichotomy; maximum constraint satisfaction problem; digraph \(H\)-colouring

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Enumerating homomorphisms, Hard constraint satisfaction problems have hard gaps at location 1

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