The dichotomy of minimum cost homomorphism problems for digraphs

DOI10.1137/100783856MaRDI QIDQ4915189zbMATH OpenOpenAlexFDO

Authors Arash Rafiey, Pavol Hell

Publication date 9 April 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.2908, https://semanticscholar.org/paper/08b0524f637b04d955247e61324923dbdad55a42

zbMATH Keywords

dichotomyMin-Max orderingsminimum cost homomorphisms

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: The Dichotomy Conjecture for constraint satisfaction problems has been verified for conservative problems (or, equivalently, for list homomorphism problems) by Andrei Bulatov. An earlier case of this dichotomy, for list homomorphisms to undirected graphs, came with an elegant structural distinction between the tractable and intractable cases. Such structural characterization is absent in Bulatov's classification, and Bulatov asked whether one can be found. We provide an answer in the case of digraphs; the technique will apply in a broader context. The key concept we introduce is that of a digraph asteroidal triple (DAT). The dichotomy then takes the following form. If a digraph H has a DAT, then the list homomorphism problem for H is NP-complete; and a DAT-free digraph H has a polynomial time solvable list homomorphism problem. DAT-free graphs can be recognized in polynomial time.

Recommendations

• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• Minimum cost homomorphism dichotomy for oriented cycles
• Minimum cost and list homomorphisms to semicomplete digraphs

Cited in

(21)

• The \(C_{k}\)-extended graft construction
• A dichotomy for minimum cost graph homomorphisms
• Minimum cost homomorphisms with constrained costs
• Approximation of minimum cost homomorphisms
• Computational complexity of the extended minimum cost homomorphism problem on three-element domains
• A dichotomy theorem for the general minimum cost homomorphism problem
• Between Colorings and Layouts - Minimum Morphism Cost Problems
• Extensions of the minimum cost homomorphism problem
• scientific article; zbMATH DE number 5531978 (Why is no real title available?)
• Monotone proper interval digraphs and Min-Max orderings
• The complexity of valued CSPs
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Minimum violation vertex maps and their applications to cut problems
• Binarisation for valued constraint satisfaction problems
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Algorithmic Applications in Management
• PTAS for Sparse General-valued CSPs
• Any-k algorithms for enumerating ranked answers to conjunctive queries
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• On the constant-factor approximability of minimum cost constraint satisfaction problems
• Minimum cost homomorphism dichotomy for oriented cycles

This page was built for publication: The dichotomy of minimum cost homomorphism problems for digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4915189)