Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs

DOI10.1137/060668316MaRDI QIDQ3648516zbMATH OpenOpenAlexFDO

Authors G. Gutin, Arash Rafiey, A. Yeo

Publication date 27 November 2009

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

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

zbMATH Keywords

homomorphismsminimum cost homomorphismssemicomplete bipartite digraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Combinatorial optimization (90C27)

Abstract: For digraphs $D$ and $H$, a mapping $f:V(D)domV(H)$ is a homomorphism of $D$ to $H$ if $uvinA(D)$ implies $f(u)f(v)inA(H).$ If, moreover, each vertex $uinV(D)$ is associated with costs $c_i(u),iinV(H)$, then the cost of the homomorphism $f$ is $su{m}_{uinV(D)}{c}_{f(u)}(u)$. For each fixed digraph $H$, we have the {em minimum cost homomorphism problem for} $H$. The problem is to decide, for an input graph $D$ with costs $c_i(u),$ $uinV(D),iinV(H)$, whether there exists a homomorphism of $D$ to $H$ and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well studied optimization problems. We describe a dichotomy of the minimum cost homomorphism problem for semicomplete multipartite digraphs $H$. This solves an open problem from an earlier paper. To obtain the dichotomy of this paper, we introduce and study a new notion, a $k$-Min-Max ordering of digraphs.

Recommendations

• Minimum cost homomorphisms to semicomplete multipartite digraphs
• Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
• Minimum cost and list homomorphisms to semicomplete digraphs

Cited in

(15)

• The \(C_{k}\)-extended graft construction
• A dichotomy for minimum cost graph homomorphisms
• Minimum cost and list homomorphisms to semicomplete digraphs
• Minimum cost homomorphisms with constrained costs
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs
• scientific article; zbMATH DE number 5531978 (Why is no real title available?)
• Monotone proper interval digraphs and Min-Max orderings
• The dichotomy of minimum cost homomorphism problems for digraphs
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• Minimum cost homomorphism dichotomy for oriented cycles
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

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

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