Minimum Cost Homomorphisms to Reflexive Digraphs

DOI10.1007/978-3-540-78773-0_16zbMATH Open1136.68462arXiv0708.2514OpenAlexW1832761474MaRDI QIDQ5458527FDOQ5458527

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)

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.

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

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

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)

Cites Work

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

Cited In (13)

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

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)