Minimum Cost Homomorphisms to Reflexive Digraphs

DOI10.1007/978-3-540-78773-0_16MaRDI QIDQ5458527zbMATHOpenAlexFDO

Authors Arvind Kumar Gupta, Mehdi Karimi, Arash Rafiey, Pavol Hell

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenesshomomorphismdichotomypolynomial time algorithmreflexive digraphminimum cost homomorphism

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: For digraphs $G$ and $H$, a homomorphism of $G$ to $H$ is a mapping $f:V(G)domV(H)$ such that $uvinA(G)$ implies $f(u)f(v)inA(H)$. If moreover each vertex $uinV(G)$ is associated with costs $c_i(u),iinV(H)$, then the cost of a homomorphism $f$ is $su{m}_{uinV(G)}{c}_{f(u)}(u)$. For each fixed digraph $H$, the {em minimum cost homomorphism problem} for $H$, denoted MinHOM($H$), is the following problem. Given an input digraph $G$, together with costs $c_i(u)$, $uinV(G)$, $iinV(H)$, and an integer $k$, decide if $G$ admits a homomorphism to $H$ of cost not exceeding $k$. We focus on the minimum cost homomorphism problem for {em reflexive} digraphs $H$ (every vertex of $H$ has a loop). It is known that the problem MinHOM($H$) is polynomial time solvable if the digraph $H$ has a {em Min-Max ordering}, i.e., if its vertices can be linearly ordered by $<$ so that $i<j,s<r$ and $ir,jsinA(H)$ imply that $isinA(H)$ and $jrinA(H)$. We give a forbidden induced subgraph characterization of reflexive digraphs with a Min-Max ordering; our characterization implies a polynomial time test for the existence of a Min-Max ordering. Using this characterization, we show that for a reflexive digraph $H$ which does not admit a Min-Max ordering, the minimum cost homomorphism problem is NP-complete. Thus we obtain a full dichotomy classification of the complexity of minimum cost homomorphism problems for reflexive digraphs.

Recommendations

• The dichotomy of minimum cost homomorphism problems for digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• Minimum cost homomorphism dichotomy for oriented cycles

Cites work

• scientific article; zbMATH DE number 5531978 (Why is no real title available?)
• scientific article; zbMATH DE number 1996252 (Why is no real title available?)
• scientific article; zbMATH DE number 1833406 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 2243365 (Why is no real title available?)
• A dichotomy for minimum cost graph homomorphisms
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Bi‐arc graphs and the complexity of list homomorphisms
• Characterization of the Homomorphic Preimages of Certain Oriented Cycles
• Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
• Coloring of trees with minimum sum of colors
• Complexity of tree homomorphisms
• Digraph matrix partitions and trigraph homomorphisms
• Homomorphisms to powers of digraphs
• Independent sets of maximum weight in (\(p,q\))-colorable graphs.
• Interval bigraphs and circular arc graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Level of repair analysis and minimum cost homomorphisms of graphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• On the complexity of H-coloring
• The approximability of constraint satisfaction problems
• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
• Three short proofs in graph theory

Cited in

(13)

• Minimum cost homomorphisms with constrained costs
• Algorithmic Applications in Management
• The dichotomy of minimum cost homomorphism problems for digraphs
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• Adjusted interval digraphs
• Colouring, constraint satisfaction, and complexity
• Monotone proper interval digraphs and Min-Max orderings
• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
• Minimum cost homomorphism dichotomy for oriented cycles
• Approximation of minimum cost homomorphisms
• A dichotomy for minimum cost graph homomorphisms
• scientific article; zbMATH DE number 5531978 (Why is no real title available?)

This page was built for publication: Minimum Cost Homomorphisms to Reflexive Digraphs

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